Question about Quick Sort

[liberty4all]

Hello all.

I'm sure you all are familiar with the quick sort algoritem, but I'm still gonna post it in short:

IF left < right THEN
   BEGIN
       pivot := partition (list, left, right);
       Quicksort (list, left, pivot-1);
       Quicksort (list, pivot + 1, right);
END

In the partition function, the norm is to usually pick the first number in the array as the pivot, right? But if you choose the last one as the pivot, the loop can become endless. How does that happen?

Thanks in advance

 

[Zyrenthian]

It has been a while since I actually wrote this algorithm, i usually just use the built in qsort function. However, if I remember correctly, the pivot was the middle value and not the first.

Matt

 

[Zyrenthian]

Just to clarify, middle value should be the middle "INDEX"

 

[liberty4all]

Thanks for replying! My main question isn't about what index is best to use though, but rather that if you choose the pivot as the last index, how can that cause the partition loop to become endless?

 

[Zyrenthian]

You are going off the end of the buffer

Quicksort (list, left, pivot-1);
Quicksort (list, pivot + 1, right);

if pivot equals n where n is the last index, then pivot +1 is reading into memory that you dont control. I would assume this could be a problem. There should be a check in the code to verify that pivot is less then or equal to right (i think). As I said, it has been a while since I wrote this algorithm. You could also put a conditional at the beginning of the algorthim, something like

if(left>right)
return


Matt