Hi guys,
I'm writing this to point out a problem in the partition method proposed in your tutorial about quicksort:
Quicksort - Cprogramming.com
I already wrote a message to axon, the author of the tutorial, but I didn't get any response, so in case my message got lost in the hyperspace or in a bloated inbox...
There is a problem with the partition method you propose, and there is another problem with making the two recursive calls. Combined, these two problems provoke a very bad behaviour:
When all (or most) of the input data in the array are equal to a specific value, chances are that this value is chosen as the pivot all the time.
The partition method puts all those values equal to the pivot in one part. Therefore, this part is much larger than the other.
This triggers the worst-case behaviour of quicksort. The sorting takes O(N*N) time.
But it gets worse... If you use ordinary recursion, you will make up to O(N) nested calls, taking O(N) space in the heap. This means that you will get a stack overflow sooner or later.
The first problem can be solved by distributing the elements equal to the pivot between the two parts. The original partition method, by Hoare, did it this way. Knuth cites Sedgewick as the author of a similar method that, in addition, excludes the pivot itself from being sorted again. I recommend that method.
The second problem can be solved using tail recursion:
Initialize variables to refer the whole array
While number of elements > 1
... Partition
... Sort small part (recursive call)
... Adapt variables to refer the large part
I supose that maybe you chose that partition method following the trend of the great "Introduction to Algorithms" (3rd ed.) by Cormen, Leiserson, Rivest and Stein. In this case, please see exercises 7.1-2 and 7.2-2, which cover this issue.
Best regards,
comocomocomo
