Created
February 15, 2022 03:47
-
-
Save FrazzIe/e4dd30498ada7357ff97fb7db8b1961b to your computer and use it in GitHub Desktop.
Basic JavaScript quick sort for my own understanding
This file contains hidden or 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
| // original: https://stackabuse.com/quicksort-in-javascript/ | |
| /* | |
| NOTE: | |
| - This algorithm can be implemented iteratively making use of a simple stack | |
| - This algorithm doesn't take up any additional space (mutates original array) | |
| - Worst case O(n^2), Average (Onlogn); Comes down to the selected pivot | |
| */ | |
| /** | |
| * Moves every element < the chosen pivot to left of the array | |
| * and then moves the pivot to the midpoint of the array | |
| * | |
| * In doing so it sorts the array and returns the index of the pivot | |
| * | |
| * @param {any[]} arr array to be sorted | |
| * @param {number} start start index | |
| * @param {number} end end index | |
| * @returns {number} pivot index | |
| */ | |
| function partition(arr, start, end) | |
| { | |
| // target element used in partitioning | |
| // pivot defaults are the first & last array element ( can be any ) | |
| // the speed of quicksort usually comes down to the pivot chosen | |
| const pivot = arr[end]; | |
| // keep track of the midpoint of the partition | |
| // where the pivot will be relocated to afterwards | |
| let pivotIdx = start; | |
| for (let i = start; i < end; i++) | |
| { | |
| // check if the current element is less than the pivot | |
| if (arr[i] < pivot) | |
| { | |
| // perform a swap of the elements | |
| // using es6 destucturing assignment | |
| // normal e.g. | |
| // const temp = arr[pivotIdx]; | |
| // arr[pivotIdx] = arr[i]; | |
| // arr[i] = temp; | |
| [ arr[i], arr[pivotIdx] ] = [ arr[pivotIdx], arr[i] ]; | |
| // increment midpoint | |
| // this ensures when we swap next the value is > pivot | |
| pivotIdx++; | |
| } | |
| } | |
| // perform a final element swap | |
| // moving the pivot to the midpoint | |
| [ arr[end], arr[pivotIdx] ] = [ arr[pivotIdx], arr[end] ]; | |
| // return the new pivot index | |
| // to be used as a base offset for | |
| // recursion | |
| return pivotIdx; | |
| } | |
| /** | |
| * Sort an array using the QuickSort algorithm | |
| * | |
| * Recursivly partitions an array until it's sorted | |
| * | |
| * @param {any[]} arr array to be sorted | |
| * @param {number} start start index | |
| * @param {number} end end index | |
| */ | |
| function sort(arr, start, end) | |
| { | |
| // block running with < 2 elements | |
| if (start >= end) | |
| { | |
| return; | |
| } | |
| // get pivot offset | |
| const index = partition(arr, start, end); | |
| // recursion | |
| sort(arr, start, index - 1); // left of pivot | |
| sort(arr, index + 1, end); // right of pivot | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment