[Oberon] Hoare's original partition algorithm.

[Jörg]

Hi Srinivas

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
and ub
 v=a[m]; //pivot is at m

or the "standard" approach
  v=a[(lb+ub)/2]; //take center element as pivot

br
Jörg

-----Original Message-----
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.

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: smime.p7s
Type: application/x-pkcs7-signature
Size: 4939 bytes
Desc: not available
Url : https://lists.inf.ethz.ch/pipermail/oberon/attachments/20130215/7c610128/attachment.bin