Skip to content

Instantly share code, notes, and snippets.

@schadokar
Last active March 3, 2020 05:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save schadokar/bd991d73d4579da7540227a9ada7f066 to your computer and use it in GitHub Desktop.
Save schadokar/bd991d73d4579da7540227a9ada7f066 to your computer and use it in GitHub Desktop.
Quicksort implementation in js
/**
* ********************************** Quick Sort ***********************************************
* UNSORTED ARRAY [3, 7, 8, 5, 2, 1, 9, 6, 4]
* pivot ^
* pivot: 3 arr: [ 2, 1, 3, 5, 8, 7, 9, 6, 4 ]
* [2, 1] [5, 8, 7, 9, 6, 4 ]
* pivot ^ ^
* pivot: 2 arr: [ 1, 2 ]
* pivot: 5 arr: [ 4, 5, 7, 9, 6, 8 ]
* [ 4] [7, 9, 6, 8 ] --> Array with single element is sorted
* pivot ^
* pivot: 7 arr: [ 6, 7, 9, 8 ]
* [ 6] [9, 8 ]
* pivot ^
* pivot: 9 arr: [ 8, 9 ]
*
* SORTED ARRAY [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
* *********************************************************************************************
*
* Worst-case Performance: O(n^2)
* Best-cae Performance: O(n log n)
* Average Performance: O(n log n)
*
* ********************************** Quick Sort ***********************************************
*/
/**
* quicksort - Sort the array using quicksort method
* @param {Array} arr
*/
const quicksort = arr => {
// return the array if array length is 1 or less than 1
if (arr.length <= 1) {
return arr;
}
// make the first element as pivot
const pivot = arr[0];
// i will move in right direction (away from pivot) from index position 1
let i = 1;
// j will move in left direction (towards pivot) from the last element of the array
let j = arr.length - 1;
// iterate till i and j are not passed each other
while (i < j) {
// find the value which is larger than pivot
while (arr[i] < pivot && i < arr.length) {
i++;
}
// find the value which is lesser than pivot
while (arr[j] > pivot && j > 0) {
j--;
}
// if i is less than j
// swap the value at i and j index
// swap the larger value at i with lesser value at j
if (i < j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap the value at j with pivot
// j index is the sorted position of the pivot
// everything to its left is lesser and larger to its right.
let temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
console.log("pivot: ", pivot, "arr: ", arr);
// left side of the pivot will be a new subarray
let left = arr.slice(0, j);
// if the length of the subarray is greater than 1
// then quicksort the subarray
if (left.length > 1) {
left = quicksort(left);
}
// right side of the pivot will be a new subarray
let right = arr.slice(j + 1, arr.length);
// if the length of the subarray is greater than 1
// then quicksort the subarray
if (right.length > 1) {
right = quicksort(right);
}
// console.log(left.concat(pivot, right));
// concat all the elements of the array
// left pivot and right
// return the sorted array
return left.concat(pivot, right);
};
console.log(quicksort([3, 7, 8, 5, 2, 1, 9, 6, 4]));
/**
* OUTPUT
*
* pivot: 3 arr: [ 2, 1, 3, 5, 8, 7, 9, 6, 4 ]
* pivot: 2 arr: [ 1, 2 ]
* pivot: 5 arr: [ 4, 5, 7, 9, 6, 8 ]
* pivot: 7 arr: [ 6, 7, 9, 8 ]
* pivot: 9 arr: [ 8, 9 ]
*
* SORTED ARRAY - [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment