Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
An implementation of quicksort
'use strict'
const nums = [3, 0, 2, 5, 1, 3, 0]
quicksort(nums, 0, nums.length - 1)
console.log(nums)
const chars = ['z', 'a', 'u', 'f', 'f', 'A']
quicksort(chars, 0, chars.length - 1)
console.log(chars)
// quicksort is at worst O(n^2), on averago O(n log n)
//
// TODO implement a better way of choosing pivot point in order to
// reduce the chance that the pivot will be the highest or lowest
// value in the element, which would cause it to run be O(n^2)
function quicksort (arr, lo, hi) {
if (lo < hi) {
const pivotIndex = partition(arr, lo, hi)
quicksort(arr, lo, pivotIndex - 1) // sort the low partition
quicksort(arr, pivotIndex + 1, hi) // sort the high partition
}
}
function partition (arr, lo, hi) {
const pivot = arr[hi] // the element to compare against
let wall = lo // the index to swap at
for (let i = lo; i < hi; i++) {
// if the current element is less than the pivot, swap it with the
// index at wall and move the wall over by one
if (arr[i] < pivot) {
swap(arr, i, wall)
wall++
}
}
swap(arr, hi, wall)
return wall
}
function swap (arr, i, j) {
const tmp = arr[i] // swap in-place O(1)
arr[i] = arr[j]
arr[j] = tmp
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment