JavaScript Quick Sort

Posted on: 2017-07-10

Quick sort divide the array in multiple sequence, hence is a very good candidate for recursivity. The asymptotic analysis gives a O(log(n^2)) in average and a worse time of O(n^2). The algorithm can be implemented in different flavor depending of where you start the initial pivot. Then, there is a second way to customize the quick sort and it's by defining how we partition.

function swap(array, left, right) {
  var temp = array[left];
  array[left] = array[right];
  array[right] = temp;
}

function partition(arrayToSort, left, right) {
  var i = left;
  var j = right;
  var pivot = arrayToSort[Math.floor((left + right) / 2)]; // Middle

  while (i <= j) {
    while (arrayToSort[i] < pivot) {
      i++;
    }
    while (arrayToSort[j] > pivot) {
      j--;
    }
    if (i <= j) {
      swap(arrayToSort, i, j);
      i++;
      j--;
    }
  }

  return i;
}

function quickSort(arrayToSort, left, right) {
  var index = partition(arrayToSort, left, right);
  if (left < index - 1) {
    quickSort(arrayToSort, left, index - 1);
  }
  if (right > index) {
    quickSort(arrayToSort, index, right);
  }
}

The algorithm divide the array in two (pivot) and go to each extremity of a partition which is between left to right where left or right is determined by the pivot. Most of the heavy-lifting is done by the partition function that will swap element if this one found that a number at the right of the pivot is bigger than one of the left side of the pivot. The algorithm goes from swap until the two extremity touch and then move back to the other side of the partition. Every call to quickSort function bring a new partition which divide the array in smaller and smaller array to partition.

The choice of the pivot will change the way the algorithm performs. The most in the middle, the best it is. This is something that we cannot know since this would require to traverse the whole array. This is why we can randomly choose a value, or in that case, taking the element in the middle.

The partition goal is to ensure that everything before the pivot is smaller than the pivot. By going recursively, at some point everything is sorted.