Quick Sort

As the name, it sounds better than merge sort, But I have to admit personally this is the bane of my existance as far as sorting algorithms. not because it's bad, it's useful as we'll see later on it's efficient. it is indeed quick. But for some reason my brain just is not like the way that quicksort works.

. Like merge sort, exploits the fact that arrays of 0 or 1 element are always sorted

. Works by selecting one element (called the "pivot") and finding the index where the pivot should end up in the sorted array

. Once the pivot is positioned appropriately, quick sort can be applied on either side of the pivot.

for example we have this array => [5, 2, 1, 8, 4, 7, 6, 3]

we select some element as the pivot for this example we select the first element which is 5. and we move all the numbers that are less than 5 to the left of it and all the numbers which are greater than 5 to the right of it.

Pivot Helper

. in order to implement quick sort, it's useful to first implement a function responsible arranging elements in an array on either side a pivot

. Given an array, this helper function should designate an element as the pivot

. It should then rearrange elements in the array so that all values less than the pivot are moved to the right of the pivot

. The order of elements on either side of the pivot doesn't matter!

. The helper should do this in place, that is, it should not create a new array

. when complete, the helper should return the index of the pivot

picking a pivot

. The runtime of quick sort depends in part on how one selects the pivot

. Ideally, the pivot should be chosen so that it's roughly the median value in the data set you're sorting

. For simplicity, we'll always choose the pivot to be the first element

Pivot Pseudocode

. It will help to accept three arguments: an array, a start index, and an end index (these can default to 0 and the array length - 1, respectively)

. Grab the pivot from the start of the array

. Store the current pivot index in a variable (this will keep track of where the pivot should end up)

. Loop through the array from start to the end => If the pivot is greater than the current element, increment the pivot index varible and then swap the current element with element at the pivot index

. Swap the starting element with the pivot index.

. return the pivot index

Pivot Helper Implementation

function pivot(arr, start = 0, end = arr.length - 1) {
    function swap(array, i, j) {
      var temp = array[i];
      array[i] = array[j];
      array[j] = temp;
    }

    let pivotIndex = start;
    let pivot = arr[pivotIndex];
    for (var i = pivotIndex + 1; i < arr.length; i++) {
      if (arr[i] < pivot) {
        pivotIndex++;
        swap(arr, pivotIndex, i);
      }
    }

    swap(arr, pivotIndex, start);
    return pivotIndex;
  }

Quicksort Pseudocode

. Call the pivot helper on the array

. When the helper returns to you the updated pivot index, recursively call the pivot helper on the subarray to the left of that index, and the subarray to the right of that index

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

   return arr;
}

Big O of Quicksort

Time Complexity (Best) => O(n log n)

Time Complexity (Average) => O(n log n)

Time Complexity (Worst) => O(n^2)

Space Complexity => O(log n)