Quicksort

How it works

Quicksort starts iteration by Picking a Pivot element,
Pivot can be chosen from the:
The first element of an array or
Last element of an array or
The middle element of an array or
Any random element of an array,
It follows the principle of divide and conquers methodology,
Means breaking array into a group of smaller array called a partition process,

Process

Placing all smaller element than pivot element into the left side of pivot element,
Placing all greater element than pivot element into the right side of pivot element,
Recursively applies same for separately on subarray of the left side of pivot element and subarray of the right side of pivot element

Performance

Best case perfoarmace: Time complexity O(n),
Averagecase performance: Time complexity O(n log n),
Worstcase performace: Time complexity O(n log n),

Implement QuickSort

Let’s implement the QuickSort in Javascript

function swap(array, leftPointer, rightPointer) {
  var temp = array[leftPointer];
  array[leftPointer] = array[rightPointer];
  array[rightPointer] = temp;
}
function subArrayPartition(array, left, right) {
  var pivot = array[Math.floor((right + left) / 2)],
    i = left, //left pointer
    j = right; //right pointer
  while (i <= j) {
    while (array[i] < pivot) {
      i++;
    }
    while (array[j] > pivot) {
      j--;
    }
    if (i <= j) {
      swap(array, i, j); //sawpping two elements
      i++;
      j--;
    }
  }
  return i;
}
function quickSort(array, lowerBound, upperBound) {
  var index;
  if (array.length > 1) {
    index = subArrayPartition(array, lowerBound, upperBound); //index returned from subArrayPartition
    if (lowerBound < index - 1) { //more elements on the lowerBound side of the pivot
      quickSort(array, lowerBound, index - 1);
    }
    if (index < upperBound) { //more elements on the upperBound side of the pivot
      quickSort(array, index, upperBound);
    }
  }
  return array;
}
// first call to quick sort
var array = [5, 3, 7, 6, 2, 9];
var sortedArray = quickSort(array, 0, array.length - 1);
console.log(sortedArray);

Quicksort

Quicksort

One thought on “Quicksort”