[Oberon] Hoare's original partition algorithm.
joerg.straube at iaeth.ch
Fri Feb 15 18:54:31 CET 2013
The tricky thing with the procedure "partition" is to get the operators "<",
"<=", ">" and ">=" right.
If you get them right, you can reuse exactly the same "partition" procedure
for all three cases you were asking. The correct "partition" can be found in
the document Chris Burrows pointed out (page 58). You then only have to
change the first statement:
v=a[lb]; //pivot is at lb
v=a[ub]; //pivot is at ub
x := a[R];
int m = random_num_between(lb, ub); // m is a random position between lb
v=a[m]; //pivot is at m
or the "standard" approach
v=a[(lb+ub)/2]; //take center element as pivot
From: Srinivas Nayak [mailto:sinu.nayak2001 at gmail.com]
Sent: Donnerstag, 14. Februar 2013 16:13
To: ETH Oberon and related systems
Subject: [Oberon] Hoare's original partition algorithm.
I started a check of different variants of quicksort
Thought of trying to program and understand myself, what is common among
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)
if(lb >= ub) //here > is for array boundary check
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
6 5 5 6 8 8 6 3 8 1
1 3 5 5 6 6 6 8 8 8
~#gcc -Wall -g quicksort2.c
7 8 5 9 6 3 9 0 0 4
0 0 3 4 5 6 7 8 9 9
~#gcc -Wall -g quicksort3.c
4 9 1 2 7 7 2 6 6 1
1 2 1 2 4 6 6 7 7 9
With thanks and best regards,
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 4939 bytes
Desc: not available
Url : https://lists.inf.ethz.ch/pipermail/oberon/attachments/20130215/7c610128/attachment.bin
More information about the Oberon