[Oberon] Hoare's original partition algorithm.

[Srinivas Nayak]

Dear All,

I started a check of different variants of quicksort
Thought of trying to program and understand myself, what is common among
all.

1. First "index of array" is pivot
2. Last "index of array"is pivot
3. Random "index of array"is pivot
4. Average of any two "elements of array"is pivot

I was able to understand and derive first two versions myself.
However, got stuck with third one.

So problem is "3. Random "index of array"is pivot".

Tried to take help of Hoare's original partition algorithm.
[Algorithm 63: Partition, C. A. R. Hoare, CACM]

Found that, it is written in Algol.
All my attempts to convert this algorithm into C failed. :-(

Everywhere in the net, I see the partition algorithms, where pivot is
first index of array! Otherwise, after collecting random index of array
as pivot, it has been exchanged with first index!

I would like to see the original algorithm in a C like language,
because, I am not able to understand the semantics of the Algol
constructs that are used in the original version. Probably that is the
reason why all my attempts to capture it in C failed.

Another thing, is that Hoare used I and J as the output variable for
partition algorithm. I will try to make a version with only one output
variable so that the next recursive calls to quicksorts shall look like...


void quicksort(int *a, int lb, int ub)
{
int p;
if(lb >= ub) //here > is for array boundary check
      return;
p=partition(a, lb, ub);

quicksort(a, lb, p-1);
quicksort(a, p+1, ub);
}

This is just for my understanding. Not trying to make an efficient
version as given by Hoare.

Can you please help me?
My successful and unsuccessful attempts attached.


~#gcc -Wall -g quicksort1.c
~#./a.out
Unsorted numbers:
   6 5 5 6 8 8 6 3 8 1
Sorted numbers:
   1 3 5 5 6 6 6 8 8 8

~#gcc -Wall -g quicksort2.c
~#./a.out
Unsorted numbers:
   7 8 5 9 6 3 9 0 0 4
Sorted numbers:
   0 0 3 4 5 6 7 8 9 9

~#gcc -Wall -g quicksort3.c
~#./a.out
Unsorted numbers:
   4 9 1 2 7 7 2 6 6 1
Sorted numbers:
   1 2 1 2 4 6 6 7 7 9


With thanks and best regards,

Yours sincerely,
Srinivas Nayak

Home: http://www.mathmeth.com/sn/
Blog: http://srinivas-nayak.blogspot.in/




-------------- next part --------------
A non-text attachment was scrubbed...
Name: quicksort1.c
Type: text/x-c
Size: 1408 bytes
Desc: not available
Url : https://lists.inf.ethz.ch/pipermail/oberon/attachments/20130214/fc1f4f85/attachment.bin 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: quicksort2.c
Type: text/x-c
Size: 1408 bytes
Desc: not available
Url : https://lists.inf.ethz.ch/pipermail/oberon/attachments/20130214/fc1f4f85/attachment-0001.bin 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: quicksort3.c
Type: text/x-c
Size: 1530 bytes
Desc: not available
Url : https://lists.inf.ethz.ch/pipermail/oberon/attachments/20130214/fc1f4f85/attachment-0002.bin