Skip to content

Instantly share code, notes, and snippets.

@FrazzIe
Created February 15, 2022 03:47
Show Gist options
  • Select an option

  • Save FrazzIe/e4dd30498ada7357ff97fb7db8b1961b to your computer and use it in GitHub Desktop.

Select an option

Save FrazzIe/e4dd30498ada7357ff97fb7db8b1961b to your computer and use it in GitHub Desktop.
Basic JavaScript quick sort for my own understanding
// 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