Quicksort algorithm tutorial

[QuestionBot]

Article: Quicksort algorithm tutorial
Question (James Ten Eyck): Your java algorithm for Quicksort does not seem to work.  At the end of the first partition, on sorting the following numbers, you have an incorrection partition:

1 1 5 5 1 4 8

The first 5 becomes left, and the 4 becomes right.  After swapping you have:

1 1 4 5 1 5 8

The first 5 (fourth index) is now left, and the right-most 1 is now right.  Those get swapped, and i increases and j decreases.

1 1 4 1 5 5 8

now 1 is right, and 5 is left (4th and 5th elements, respectively).  Returning right leaves 1 as the partition.  That does not work because 4 is to the left of the partition but is greater than 1.  Am I missing something here?

[Denis]

I checked the code. After the first partition (pivot = 5) source array becomes:

1 1 4 1 5 5 8

and partition function returns 4. It's ok, because then algorithm sorts 0..3 and 4..6 subarrays, which leads to the correct result.

[jtphenom]

I thought that, with quicksort, the array index that is returned should be an index to a number that is already sorted and does not need to be sorted in the recursive calls to quicksort. You're saying that, after the first partition, 0-3 and 4-6 are each sublists, but I learned that quicksort makes it so, when 4 is returned, your partions are 0-3 and 5-6.
 
In any case when I go through the algorithm, I'm getting a different result. Can you show me the steps, please? I'm very confused.

[Denis]

The returned value is an index of the first element of the right part. Let's see it on example:

Source array: 1 1 5 5 1 4 8
Pivot value: 5
After first call to partition(...): 1 1 4 1 5 5 8
partition(...) returns: 4

4 means, that

arr[0..3] < 5 <= arr[4..6]

Therefore, if we sort both left (0..3) and right (4..6) parts separately, then the whole array will become sorted. Tell, if it is clear or you need more explanations.