JavaScript Sorting Algorithms: Quick Sort

Similarly to merge sort, quick sort utilizes recursion in order to sort elements. Similarly to merge sort it is based on partitioning the array into smaller arrays. But the mechanism of sorting elements is different. Quick sorted introduces a new concept in sorting called the ‘pivot’.

Introduction to Quick Sort

Wow, quite a name, right? Quick sort. Based on the name itself it must be fast, right? Quick sort works by selecting any element (there are optimization techniques that can select the best option, but in our case, we will just take the first element) which will be called the pivot. 🚀 🚀

Then, we will move all the numbers smaller than that number to the left of that number, and all the numbers greater than that number to the right of that number. We are NOT sorting those numbers, we are only moving them. After each sorting session, there is one thing clear - the pivot is always in the right spot!

Visualization

The Inputs for this algorithm are: [12, 3, 44, 38, 5, 47, 15, 9]. 📊

Quick sort visualization using visualgo. Please visit https://visualgo.net/ for more visual algorithms.

First iteration, we selected the pivot. In our case the first number. Then the algorithm moves all the elements smaller than the pivot to the left of the pivot, and all the elements greater to the right. Elements moved to the left or right of the pivot are not sorted. Only the pivot is sorted after each iteration.

In the vizualization above 12 is the first pivot. After going through the whole array, 12 (yellow) is in the correct spot, and elements to the left of it (green) and right of it (purple) are still to be properly sorted. In our next iteration we select the left partition of the array, and we continue the process. Keep in mind that 12 is now at the correct spot, and is marked orange.

Selecting 12 as the pivot, everything else apart from the pivot is still to be sorted!

Sorting the left partition, the past pivot (12) is now in the correct spot.

Pivot Implementation

Now is not the time for sorting, that comes later!

We will instead first write a function that will be responsible for selecting the pivot and properly arranging the elements to either left or right of the pivot, while the correct order of the elements is still not that important. 'Pivoting' the array should not involve creating a new array. ✈️ ✈️

Pseudocode:

1. The method should accept three arguments: an array to 'pivot' on, the starting index and the ending index
2. For simplicity's sake, the pivot will be picked from the beginning of the array
3. The current pivot index will be stored in a variable
4. The algorithm will loop through the array1. If the pivot is greater than the current element, the pivot index is increased and the pivot index element is swapped with the current element
5. At the end the starting element is swapped with the pivot index
6. The algorithm returns the pivot index

function pivot(arr, start = 0, end = arr.length + 1) {
  let pivot = arr[start];
  let swapIndex = start;
  for (let i = start + 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      swapIndex++;
      swap(arr, i, swapIndex);
    }
  }

  swap(arr, start, swapIndex);
  return swapIndex;

  function swap(arr, firstIndex, secondIndex) {
    [arr[firstIndex], arr[secondIndex]] = [arr[secondIndex], arr[firstIndex]];
  }
}

The code above accepts three arguments, the array, the starting index (defaulting at 0), and the ending index (defaulting at the length of the array minus 1, or the last element). The pivot is the starting element, and the swapIndex starts at the beginning of the array. The algorithm then iterates, going through every element in the array, checking if the pivot is greater than the current element in the loop. If it is the swapIndex increases and the elements at those two indices are swapped. After the loop has finished we do one last swap - swapping the pivot element with the element at the swap index, thus setting the pivot at the appropriate place in the array.

Quick Sort Implementation

Again - quick sort is a recursive function. Please check the link to understand the concept more if you've never dealt with recursive code before!

Quick sort pseudocode:

1. The pivot method is called, saving the return value in a pivot Index variable
2. Quick sort is recursively called on the left and right sides of the array using the pivot index as the parameter.

function quickSort(arr, left = 0, right = arr.length - 1) {
  if(left < right) {
    let pivotIndex = pivot(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }

  return arr;
}

If the leftmost element is smaller than the rightmost (basically, if there is more than one element in the array) we do the following - call the pivot method, returning the pivot index, and then recursively call the quickSort on the left sub-portion of the array (from the start to the pivotIndex - 1) and the right sub-portion (from the pivotIndex + 1 to the end of the array). Recursion takes care of the rest :). 🎆 🎆

Big O Complexity

Quick sort uses recursion - so it isn't surprising that the best and average case are again all the same - O(nlog(n)). There are O(log(n)) decompositions, and O(n) comparisons inside each decomposition. But wait, there is the worst case complexity. What is going out there? There is a rare case in which the pivot is repeatedly the smallest element in the array. In that case we would need to decompose the array O(n) times, and make O(n) comparisons, thus making the algorithm O(n2).

Conclusion

Quick Sort is an effective algorithm due to its divide and conquer methodology. Compared to Merge Sort it is more effective when the data set is smaller (and vice versa - Merge Sort is more effective on a larger data set). Hope you learned something new today! If you liked this one please check the whole series or visit my blog for more tech articles. 🤘