Last active
March 3, 2020 05:31
-
-
Save schadokar/bd991d73d4579da7540227a9ada7f066 to your computer and use it in GitHub Desktop.
Quicksort implementation in js
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* ********************************** 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