Last active
April 3, 2020 19:07
-
-
Save chasingmaxwell/3ec711c2b1f905d5d298185cfcb2181a to your computer and use it in GitHub Desktop.
An implementation of quicksort in TypeScript - warning: this is probably bad
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
const MIN = -1e3; | |
const MAX = 1e3; | |
const SIZE = 1e6; | |
/** | |
* Get a random number between min and max. | |
* | |
* @param min the minimum integer possible. | |
* @param max the maximum integer possible. | |
*/ | |
const getRandomNumber = (min: number, max: number): number => | |
Math.round((max - min) * Math.random() + min); | |
/** | |
* Sort an unsorted array of integers. | |
* | |
* @param unsorted an unsorted array of integers. | |
*/ | |
const quickSort = (unsorted: Array<number>): Array<number> => { | |
if (unsorted.length < 2) { | |
return unsorted; | |
} | |
const [pivot, ...rest] = unsorted; | |
const left = []; | |
const right = []; | |
const center = [pivot]; | |
for (const val of rest) { | |
if (val < pivot) { | |
left.push(val); | |
} else if (val === pivot) { | |
center.push(val); | |
} else { | |
right.push(val); | |
} | |
} | |
return [...quickSort(left), ...center, ...quickSort(right)]; | |
}; | |
const array = Array.from(Array(SIZE).keys()).map(() => | |
getRandomNumber(MIN, MAX) | |
); | |
const sorted = quickSort(array); | |
console.log('Unsorted:', array.length, array); | |
console.log('Sorted:', sorted.length, sorted); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment