Skip to content

Instantly share code, notes, and snippets.

@chasingmaxwell
Last active April 3, 2020 19:07
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 chasingmaxwell/3ec711c2b1f905d5d298185cfcb2181a to your computer and use it in GitHub Desktop.
Save chasingmaxwell/3ec711c2b1f905d5d298185cfcb2181a to your computer and use it in GitHub Desktop.
An implementation of quicksort in TypeScript - warning: this is probably bad
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