Quicksort in Excruciating Detail
13 Nov 2017
Let's take this slice of ints:
6, 63, 58, 24, 54, 28, 33, 80, 100
and try to qsort them.
func QSort(v []int, left int, right int) {
last := 0
if left >= right {
return
}
v[left], v[(left+right)/2] = v[(left+right)/2], v[left]
last = left
for i := left + 1; i <= right; i++ {
if v[i] < v[left] {
last++
v[last], v[i] = v[i], v[last]
}
}
v[left], v[last] = v[last], v[left]
QSort(v, left, last-1)
QSort(v, last+1, right)
}
It's interesting to note that the function needs to be called with the first and last index of our slice in addition to the slice itself! You'd think you could just call QSort(mySlice) and be done with it.
When we think about it, that makes sense, because for QSort to be able to work recursively, we need to be able to tell it to work on smaller and smaller ranges of the underlying slice, and to do that, we need to be able to call it with the starting and ending indices.
So if our above slice of ints is assigned to a varable v, we call QSort like so:
QSort(v, 0, len(v)-1)
QSort first call:
v: [6, 63, 58, 24, 54, 28, 33, 80, 100] left: 0 right: 8 last: 0
So we definitely get past this:
if left >= right {
return
}
Now we chose the pivot from the middle and swap it to the start of the slice:
v[left], v[(left+right)/2] = v[(left+right)/2], v[left]
As near as I can tell, this is in case the list is sorted; we then take the pivot that would be the best pivot to use for a sorted slice. It's interesting that we pick the pivot and then put it at the start of the array. I *think* this might make other implementation details easier, because then you have the pivot out of the way while you walk the remaining array looking for (and swapping) values that are less than the pivot. But I'm not sure.
So now our slice looks like this:
v: [54, 63, 58, 24, 6, 28, 33, 80, 100]
6 and 54 have swapped places.
Now we assign the left index to last:
left: 0 right: 8 last: 0
last will be the last index of the slice on our left. It will increment every time we swap a value smaller than the pivot into a new slice index, and we will feed it to a recursive call to QSort later.
Note that our for loop does not start at left, it starts at left + 1, so that we don't disturb the pivot that's all the way left.
Now we read the slice from left +1 to right, and whenever an item is larger than our pivot (located in v[left] we put it in the next available slot in the left part of the slice (which is why we increment last when the swap needs to happen):
if v[i] < v[left] {
last++
v[last], v[i] = v[i], v[last]
}
So the iteration looks like this:
left: 0
right: 8
last: 0
i: 1
v: [54, 63, 58, 24, 6, 28, 33, 80, 100]
i right
63 is not less than 54, so next loop, increment i.
left: 0
right: 8
last: 0
i: 2
v: [54, 63, 58, 24, 6, 28, 33, 80, 100]
i right
58 is not less than 54, so next loop, increment i.
left: 0
right: 8
last: 0
i: 3
v: [54, 63, 58, 24, 6, 28, 33, 80, 100]
i right
24 is less than 54, so increment last and swap v[i] with v[last] (swap v[3] with v[1])
left: 0
right: 8
last: 1
i: 3
v: [54, 24, 58, 63, 6, 28, 33, 80, 100]
last i right
next loop, increment i.
left: 0
right: 8
last: 1
i: 4
v: [54, 24, 58, 63, 6, 28, 33, 80, 100]
last i right
6 is less than 54, so increment last and swap v[i] with v[last] (swap v[4] with v[2])
left: 0
right: 8
last: 2
i: 4
v: [54, 24, 6, 63, 58, 28, 33, 80, 100]
last i right
next loop, increment i.
left: 0
right: 8
last: 2
i: 5
v: [54, 24, 6, 63, 58, 28, 33, 80, 100]
last i right
28 is less than 54, so increment last and swap v[i] with v[last] (swap v[5] with v[3])
left: 0
right: 8
last: 3
i: 5
v: [54, 24, 6, 28, 58, 63, 33, 80, 100]
last i right
next loop, increment i.
left: 0
right: 8
last: 3
i: 6
v: [54, 24, 6, 28, 58, 63, 33, 80, 100]
last i right
33 is less than 54, so increment last and swap v[i] with v[last] (swap v[5] with v[3])
left: 0
right: 8
last: 4
i: 6
v: [54, 24, 6, 28, 33, 63, 58, 80, 100]
last i right
next loop, increment i.
left: 0
right: 8
last: 4
i: 7
v: [54, 24, 6, 28, 33, 63, 58, 80, 100]
last i
right
80 is not less than 54, so next loop, increment i.
left: 0
right: 8
last: 4
i: 8
v: [54, 24, 6, 28, 33, 63, 58, 80, 100]
last i
right
100 is not less than 54, so next loop, increment i.
left: 0
right: 8
last: 4
i: 9
v: [54, 24, 6, 28, 33, 63, 58, 80, 100]
last i
right
Break out of loop because i, 9, is greater than right, 8.
Now, put the pivot in its correct location at last, and put last back at left, which is fine, because the value at last is definitely less than the pivot.
v[left], v[last] = v[last], v[left] v[0], v[4] = v[4], v[0]
left: 0 right: 8 last: 4 v: [33, 24, 6, 28, 54, 63, 58, 80, 100] left last right
With the pivot, 54, at its correct final index in the slice, the correctly sorted slice would look like
qsorted[33, 24, 6, 28] + [54] + qsorted[63, 58, 80, 100]
So that looks like
QSort(v, left, last-1) QSort(v, last+1, right)
Notice last-1 and last+1 to leave last out of it, because last is pointing to our pivot at its correct place in the sorted slice.
In other words:
QSort(v, 0, 3) // let's call this QSort L1 QSort(v, 5, 8) // Let's call this QSort R1
Continuing on with the call, L1, to QSort(v, 0, 3):
left: 0 right: 3 last: 0 v: [33, 24, 6, 28, 54, 63, 58, 80, 100]
left is not greater than or equal to right, so we pass this:
if left >= right {
return
}
We swap the middle index, our pivot, with the left-most index:
v[left], v[(left+right)/2] = v[(left+right)/2], v[left] v[0], v[1] = v[1], v[0]
left: 0
right: 3
last: 0
v: [24, 33, 6, 28, 54, 63, 58, 80, 100]
right
We make last equal to left:
left: 0
right: 3
last: 0
v: [24, 33, 6, 28, 54, 63, 58, 80, 100]
right
Now we enter our loop, with i starting at left + 1:
left: 0
right: 3
last: 0
i: 1
v: [24, 33, 6, 28, 54, 63, 58, 80, 100]
i right
33 is not less than 24, so next loop, increment i.
left: 0
right: 3
last: 0
i: 2
v: [24, 33, 6, 28, 54, 63, 58, 80, 100]
right
i
6 is less than 24, so increment last and swap v[i] with v[last] (swap v[2] with v[1])
left: 0
right: 3
last: 1
i: 2
v: [24, 6, 33, 28, 54, 63, 58, 80, 100]
right
i
last
next loop, increment i.
left: 0
right: 3
last: 1
i: 3
v: [24, 6, 33, 28, 54, 63, 58, 80, 100]
right
i
last
28 is not less than 24, so next loop, increment i.
left: 0
right: 3
last: 1
i: 4
v: [24, 6, 33, 28, 54, 63, 58, 80, 100]
right
i
last
Break out of loop because i, 4, is greater than right, 3.
Now, put the pivot in its correct location at last, and put last back at left, which is fine, because the value at last is definitely less than the pivot.
v[left], v[last] = v[last], v[left] v[0], v[1] = v[1], v[0]
left: 0
right: 3
last: 1
v: [6, 24, 33, 28, 54, 63, 58, 80, 100]
left right
last
With the pivot, 24, at its correct final index in the slice, the correctly sorted sub slice would look like
qsorted[6] + [24] + qsorted[33, 28]
So that looks like
QSort(v, left, last-1) QSort(v, last+1, right)
Notice last-1 and last+1 to leave last out of it, because last is pointing to our pivot at its correct place in the sorted slice.
In other words:
QSort(v, 0, 0) // let's call this QSort L2 QSort(v, 2, 3) // Let's call this QSort R2
Continuing on with the call, L2, to QSort(v, 0, 0):
left is equal to right, so we return from this:
if left >= right {
return
}
Continuing on with the call, R2, to QSort(v, 2, 3):
left is not greater than or equal to right, so we pass this:
if left >= right {
return
}
We swap the middle index, our pivot, with the left-most index:
v[left], v[(left+right)/2] = v[(left+right)/2], v[left] v[2], v[2] = v[2], v[2]
The interesting thing being our numbers are now so close together that we just swapped the first value with itself!
left: 2
right: 3
last: 0
v: [6, 24, 33, 28, 54, 63, 58, 80, 100]
left
right
We make last equal to left:
left: 2
right: 3
last: 2
v: [6, 24, 33, 28, 54, 63, 58, 80, 100]
left
right
last
Now we enter our loop, with i starting at left + 1:
left: 2
right: 3
last: 2
i: 3
v: [6, 24, 33, 28, 54, 63, 58, 80, 100]
left
right
last
i
28 is less than 33, so increment last and swap v[i] with v[last] (swap v[3] with v[2])
left: 2
right: 3
last: 2
i: 3
v: [6, 24, 28, 33, 54, 63, 58, 80, 100]
left
right
last
i
next loop, increment i.
left: 2
right: 3
last: 2
i: 4
v: [6, 24, 28, 33, 54, 63, 58, 80, 100]
left
right
last
i
Break out of loop because i, 4, is greater than right, 3.
Now, put the pivot in its correct location at last, and put last back at left, which is fine, because the value at last is definitely less than the pivot.
v[left], v[last] = v[last], v[left] v[3], v[3] = v[3], v[3]
Again, because our numbers are so close together, we swap the pivot with itself!
left: 2
right: 3
last: 2
v: [6, 24, 28, 33, 54, 63, 58, 80, 100]
left
right
last
With the pivot, 24, at its correct final index in the slice, the correctly sorted sub sub slice would look like
qsorted[] + [24] + qsorted[28]
So that looks like
QSort(v, left, last-1) QSort(v, last+1, right)
Notice last-1 and last+1 to leave last out of it, because last is pointing to our pivot at its correct place in the sorted slice.
In other words:
QSort(v, left, last-1) QSort(v, last+1, right)
Continuing on with the call, L3, to QSort(v, 2, 1):
left is greater than right, so we return from this:
if left >= right {
return
}
Continuing on with the call, R3, to QSort(v, 3, 3):
left is equal to right, so we return from this:
if left >= right {
return
}
Continuing on with the call, R1, to QSort(v, 5, 8):
left: 5 right: 8 last: 0 v: [6, 24, 28, 33, 54, 63, 58, 80, 100]
left is not greater than or equal to right, so we pass this:
if left >= right {
return
}
We swap the middle index, our pivot, with the left-most index:
v[left], v[(left+right)/2] = v[(left+right)/2], v[left] v[5], v[6] = v[6], v[5]
left: 5
right: 8
last: 0
v: [6, 24, 28, 33, 54, 58, 63, 80, 100]
left
right
We make last equal to left:
left: 5
right: 8
last: 5
v: [6, 24, 28, 33, 54, 58, 63, 80, 100]
left
right
last
Now we enter our loop, with i starting at left + 1:
left: 5
right: 8
last: 5
i: 6
v: [6, 24, 28, 33, 54, 58, 63, 80, 100]
left
right
last
i
63 is not less than 58, so next loop, increment i.
left: 5
right: 8
last: 5
i: 7
v: [6, 24, 28, 33, 54, 58, 63, 80, 100]
left
right
last
i
80 is not less than 58, so next loop, increment i.
left: 5
right: 8
last: 5
i: 8
v: [6, 24, 28, 33, 54, 58, 63, 80, 100]
left
right
last
i
100 is not less than 58, so next loop, increment i.
left: 5
right: 8
last: 5
i: 9
v: [6, 24, 28, 33, 54, 58, 63, 80, 100]
left
right
last
i
Break out of loop because i, 9, is greater than right, 8.
Now, put the pivot in its correct location at last, and put last back at left, which is fine, because the value at last is definitely less than the pivot.
v[left], v[last] = v[last], v[left] v[5], v[5] = v[5], v[5]
Here, because everything was larger than the pivot, we end up swapping the pivot with itself, leaving it where it was!
left: 5
right: 8
last: 5
v: [6, 24, 28, 33, 54, 58, 63, 80, 100]
left
right
last
With the pivot, 58, at its correct final index in the slice, the correctly sorted sub slice would look like
qsorted[] + [58] + qsorted[63, 80, 100]
So that looks like
QSort(v, left, last-1) QSort(v, last+1, right)
Notice last-1 and last+1 to leave last out of it, because last is pointing to our pivot at its correct place in the sorted slice.
In other words:
QSort(v, 5, 4) // let's call this QSort L4 QSort(v, 6, 8) // Let's call this QSort R4
Continuing on with the call, L4, to QSort(v, 5, 4):
left is greater than right, so we return from this:
if left >= right {
return
}
Continuing on with the call, R1, to QSort(v, 6, 8):
left: 6
right: 8
last: 0
v: [6, 24, 28, 33, 54, 58, 63, 80, 100]
left
right
left is not greater than or equal to right, so we pass this:
if left >= right {
return
}
We swap the middle index, our pivot, with the left-most index:
v[left], v[(left+right)/2] = v[(left+right)/2], v[left] v[6], v[7] = v[7], v[6]
left: 6
right: 8
last: 0
v: [6, 24, 28, 33, 54, 58, 80, 63, 100]
left
right
We make last equal to left:
left: 6
right: 8
last: 6
v: [6, 24, 28, 33, 54, 58, 80, 63, 100]
left
right
last
Now we enter our loop, with i starting at left + 1:
left: 6
right: 8
last: 6
i: 7
v: [6, 24, 28, 33, 54, 58, 80, 63, 100]
left
right
last
i
63 is less than 80, so increment last and swap v[i] with v[last] (swap v[7] with v[7])
left: 6
right: 8
last: 6
i: 7
v: [6, 24, 28, 33, 54, 58, 80, 63, 100]
left
right
last
i
next loop, increment i.
left: 6
right: 8
last: 6
i: 8
v: [6, 24, 28, 33, 54, 58, 80, 63, 100]
left
right
last
i
100 is not less than 80, so next loop, increment i.
left: 6
right: 8
last: 6
i: 9
v: [6, 24, 28, 33, 54, 58, 80, 63, 100]
left
right
last
i
Break out of loop because i, 9, is greater than right, 8.
Now, put the pivot in its correct location at last, and put last back at left, which is fine, because the value at last is definitely less than the pivot.
v[left], v[last] = v[last], v[left] v[6], v[7] = v[7], v[8]
left: 6
right: 8
last: 6
v: [6, 24, 28, 33, 54, 58, 63, 80, 100]
left
right
last
With the pivot, 80, at its correct final index in the slice, the correctly sorted sub slice would look like
qsorted[63] + [80] + qsorted[100]
So that looks like
QSort(v, left, last-1) QSort(v, last+1, right)
Notice last-1 and last+1 to leave last out of it, because last is pointing to our pivot at its correct place in the sorted slice.
In other words:
QSort(v, 6, 6) // let's call this QSort L5 QSort(v, 8, 8) // Let's call this QSort R5
Continuing on with the call, L5, to QSort(v, 6, 6):
left is equal to right, so we return from this:
if left >= right {
return
}
Continuing on with the call, R5, to QSort(v, 8, 8):
left is equal to right, so we return from this:
if left >= right {
return
}
DONE!