QuickSort algorithm in Javascript

QuickSort is the most asked sorting technique question in interviews - for a good reason.

QuickSort is tricky to remember (let alone implement) but it is the fastest and sometimes "the best" option to choose in most situations. Knowing how quicksort works will clear your technical screening round as many interviewers will probably ask you to explain it.

Sometimes, all they want to know is whether you are familiar with the algorithm to perform quicksort. But sometimes you may be asked to write code.

When you think about quicksort, think about a "pivot".



Algorithm

Step 1: Pick a "pivot".

Step 2. Pivot [P] = median(first + mid + last);

Step 3. Move Pivot to the end of the array.

Step 4. Find the below items compared to the pivot.
  - largerItemFromLeft -> A[l] //first item
  - smallerItemFromRight -> A[s] //first item

Step 5. swap (l, s) IFF (l < s) // Remember this trick {indices}

Step 6. Repeat steps 4, 5 until l > s

Step 7. swap (p, l)

Step 7. Recrusively do this for larger and smaller partitions

Step 8. Exit recursion when partition has only 1 element.

Javascript Program

function swap(a, index1, index2) {
  let temp = a[index1];
  a[index1] = a[index2];
  a[index2] = temp;
}


function partition(A, start, end) {
  let p = end;
  let l = -1;
  let s = -1;


  do {
    // Find Larger index from left
    for (let i = start; i < end; i++) {
      if (A[i] > A[p]) {
        l = i;
        break;
      }
    }


    if (l === -1) {
      break;
    }


    // Find smaller index from right
    for (let j = end - 1; j >= start; j--) {
      if (A[j] < A[p]) {
        s = j;
        break;
      }
    }


    if (s === -1) {
      break;
    }


    // The trick is here
    if (l < s) {
      swap(A, l, s)
    }


  } while (l < s);


  if (l !== -1) {
    swap(A, p, l);
    p = l;
  }
  return p;
}


function quickSort(array, start, end) {


  if (start < end) {
    let p = partition(array, start, end); 
    quickSort(array, start, p - 1);
    quickSort(array, p + 1, end);
  }


  return array;
}



const result = quickSort([6, 3, 9, 4, 0, 1, 4, 456, 11], 0, 11);


console.log(result);

Time Complexity

O(N*2) => worst case

O(NlogN) => Avg case ( almost all the time this is the case )

Space Complexity

O(logN)

Points to be noted

1. This is the most efficient algorithm 
(.sort() function of most languages is quick sort)

2. Recursive method

3. The algorithm uses Divide and conquer method 
(But original array is altered)