Sorting Algorithms: Quick Sort
This is part of an ongoing series of blog posts where I cover sorting algorithms. This week I’m looking at Quick Sort.
It works on the same assertion that merge sort does because it is solved through recursion where we keep splitting the array until we have arrays that are the length of 1 or 0, which means that they are individually sorted. Introducing the pivot — and here is how it is different from merge sort — it works by selecting one element(the pivot) and finding the index where the pivot should end up in the sorted array. For all the elements whose value is greater than that of the pivot, we will move them to the right of the pivot. For all the elements whose value is less than that of the pivot we will move to the left. Once the pivot is positioned appropriately, quick sort can be applied on either side of the pivot.
Example.
Let’s say we have the following array:
[5,3,4,1,8,7,2,6]
When we call quick sort on this array, the first step will be to select our pivot. In this example we will use 5 at index 0. In our first iteration through the array, we should expect to place 5 in the position where it will stay until the rest of the array is sorted. But first we have to iterate through the array and see where to place it. Before we move 5, we want to see what values in the array are less than 5 and move them to the index of the first value that is higher than our pivot, in this case, the number 8 is our first number greater than 5. So since there is a lesser value that comes after 8 in our array (2), we will first swap 2 and 8.
[5,3,4,1,2,7,8,6]
and then we swap 5 with 2
[2,3,4,1,5,7,8,6]
Then we recursively work with the sub arrays containing the lesser values and greater values.
[2,3,4,1] [7,8,6]
and we go left to right,
[2,1,4,3] => [1,2,4,3] => [1,2,3,4] // [7,6,8] => [6,7,8]
so we swap and lastly…
[1,2,3,4,5,7,6,8]
The conditions of a pivot:
- The pivot’s index is in the correct position in the final sorted array
- All items to the left are less than the value of the pivot
- All of the items to the right are greater than the value of the pivot
To begin writing out the code for the quick sort we need what is called a Partition or Pivot Helper. Given an array, this helper function will pin point an element as a pivot. It will also rearrange the elements in the array so the lesser values are moved to the left and greater values moved to the right of the pivot. And it will do this without creating a new array. The expected output of this helper should be the index of the pivot. So for our example above, the first pivot should return the value of 4, because 5 (at index 0) will be swapped to the 5th index which is index 4. The Partition or Pivot Helper will accept three arguments: an array, the pivot (which we will default to 0), and the end of the array or array.length -1. Next we will store the current pivot index in a variable we’ll call a, which will be the return value of this helper function. Looping through the array, we are looking for the values that are less than the pivot. For each value that is less than the pivot, we will increment the a variable by one and then swap the starting index of the pivot, with the a variable. And then we return variable a.
function pivot(array, start=0, end=array.length) {
function swap(arr, a, b){
[arr[a], arr[b]] = [arr[b], arr[a]]
}
let pivot = array[start]
let swapIndex = start; for(let i = start+1; i < array.length; i++) {
if (pivot > array[i]) {
swapIndex++;
swap(array, swapIndex, i)
}
}
swap(array, start, swapIndex)
return swapIndex
In the code above, we are creating a swap helper inside of our pivot helper. The pivot helper takes in three arguments. We set start and end with default values for the sake of simplicity, there are other cases where it might be better to set the value of the pivot to another indexed value; for instance if you were working with a nearly sorted array it would be best to set the pivot to the median of the array. This code here will compare the pivotIndex with the array[i] index two see which is greater, if the pivot is greater, we will increment the swapIndex by one. Now to implement the actual quick sort.
function quickSort(array, start=0, end=array.length -1){
if(start < end) {
//Call the pivot helper on the array
let pivotIndex = pivot(array, start, end)
//left
quickSort(array, start, pivotIndex-1)
//right
quickSort(array, pivotIndex +1, end)
}
return array
}In the actual quickSort code, we are first implementing our edge case, where if the end of our array is less than or equal to the start of our array, than we can no longer split our array into a sub-array. Next we are declaring a variable called pivotIndex, which calls on our pivot helper function and returns the new index of our current pivot. Below that line we are recursively calling quickSort on the left side of the array from the point of the pivotIndex, as well as recursively calling quickSort on the right side of the array starting from the index after the pivotIndex. Finally, once our sub-arrays have all been quickly sorted we return the sub-array and begin merging them into a sorted array. I hope this was helpful. And if you were lost during this process, that’s great too. I’ll drop a link to the other guides I’ve written up on sorting algorithms. Happy Coding.
