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);
One thought on “Quicksort”
Comments are closed.