How to perform divide step of in-place Quicksort?

Question

I have an example of quicksort, it says like this: The divide step of in-place quicksort works by showing how the following list would look after performing the division with the first element as pivot element. Smaller values end up to the left, and larger to the right.

The example {17,13,5,19,22,18,3,20,16,12,2,9} ends up to in {16,13,5,9,2,12,3,17,20,18,22,19}. I took 17 in the middle and than put all smaller values to the left and bigger to the right but us you can understand it is not ending up as the answer of the example. How should it be done? What am I missing to do?

Answer 1

There are many different implementations of in-place quicksort. It seems that the one you are using involves something like:

pivotIndex := first index of array
pivot := array[pivotIndex]
left := second index of array
right := last index of array
while left ≤ right
    while array[left] < pivot
        left := left + 1
    while array[right] > pivot
        right := right - 1
    if left ≤ right
        swap array[left] with array[right]
        left := left + 1
        right := right - 1

// Swap the pivot to the end of the lower subarray.
swap array[pivotIndex] with array[right] 

I'll use red for the lower subarray and green for the upper subarray: $$ (17,13,5,19,22,18,3,20,16,12,2,9) \\ (17,\color{red}{13},5,19,22,18,3,20,16,12,2,9) \\ (17,\color{red}{13,5},19,22,18,3,20,16,12,2,9) \\ (17,\color{red}{13,5,9},22,18,3,20,16,12,2,\color{green}{19}) \\ (17,\color{red}{13,5,9,2},18,3,20,16,12,\color{green}{22,19}) \\ (17,\color{red}{13,5,9,2,12},3,20,16,\color{green}{18,22,19}) \\ (17,\color{red}{13,5,9,2,12,3},20,16,\color{green}{18,22,19}) \\ (17,\color{red}{13,5,9,2,12,3,16},\color{green}{20,18,22,19}) \\ (\color{red}{16,13,5,9,2,12,3},17,\color{green}{20,18,22,19}) \\ $$