Created
February 9, 2016 21:56
-
-
Save radcliff/f2cab48a9761d81c6b3d to your computer and use it in GitHub Desktop.
Javascript implementation of quicksort
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
/* | |
Quicksort! | |
Name your function quickSort. | |
Quicksort should grab a pivot from the end and then separate the list (not including the pivot) | |
into two lists, smaller than the pivot and larger than the pivot. Call quickSort on both of those | |
lists independently. Once those two lists come back sorted, concatenate the "left" (or smaller numbers) | |
list, the pivot, and the "right" (or larger numbers) list and return that. The base case is when quickSort | |
is called on a list with length less-than-or-equal-to 1. In the base case, just return the array given. | |
As always, you can change describe to xdescribe to prevent the unit tests from running while you're coding. | |
No visualization is provided so feel free to use your own debugging methods (like console.log). | |
*/ | |
function quickSort(array) { | |
var length = array.length | |
var pivot = array[length - 1] | |
if (length < 2) { | |
return array | |
} | |
var left = [] | |
var right = [] | |
for (var i = 0; i < length - 1; i++) { | |
if (array[i] < pivot) { | |
left.push(array[i]) | |
} else { | |
right.push(array[i]) | |
} | |
} | |
var leftSort = quickSort(left) | |
var rightSort = quickSort(right) | |
// return leftSort.concat(pivot, rightSort) | |
return [...leftSort, pivot, ...rightSort] | |
} | |
// unit tests | |
// do not modify the below code | |
describe('quick sort', function() { | |
it('quicksort an array', () => { | |
const input = [10, 8, 2, 1, 6, 3, 9, 4, 7, 5]; | |
const answer = quickSort(input); | |
expect(answer).toEqual([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); | |
}); | |
}); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment