Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
CoffeeScript quicksort with tests
# Non-destructive quicksort.
# DOESN'T WORK WITH DUPLICATES. Too lazy.
# [1, 5, 8, 12].quickSort()
Array::quickSort = ->
# Is the array already sorted by nature of its length?
return this if @length <= 1
# Pick a pivot as a random element.
# This is probably not the best pivot we could choose.
pivot = this[Math.floor(Math.random() * @length)]
# Set up two pointers.
i = 0
j = @length - 1
# Move inward towards the middle.
while i isnt j
# Find an element that's larger than or equal to the pivot.
while (this[i] < pivot) and (i isnt j)
i++
# Find an element that's smaller than or equal to the pivot.
while (this[j] > pivot) and (i isnt j)
j--
# Switch the two elements.
[this[i], this[j]] = [this[j], this[i]]
# Recurse with the two halves on either side of the pivot.
firstHalf = @slice(0, i)
secondHalf = @slice(i + 1)
# Sort the halves.
firstHalf = firstHalf.quickSort()
secondHalf = secondHalf.quickSort()
# Concatenate them.
return firstHalf.concat(pivot, secondHalf)
########################################################################
# Test setup
assert = console.assert
eq = (a, b) ->
return false if a.length isnt b.length
for num, i in a
return false if num != b[i]
return true
# Tests
assert eq([].quickSort(), [])
assert eq([0].quickSort(), [0])
assert eq([1].quickSort(), [1])
assert eq([1, 2].quickSort(), [1, 2])
assert eq([2, 1].quickSort(), [1, 2])
assert eq([1, 2, 3].quickSort(), [1, 2, 3])
assert eq([2, 1, 3].quickSort(), [1, 2, 3])
assert eq([3, 1, 2].quickSort(), [1, 2, 3])
assert eq([3, 2, 1].quickSort(), [1, 2, 3])
assert eq([0, 2, 3].quickSort(), [0, 2, 3])
assert eq([2, 0, 3].quickSort(), [0, 2, 3])
assert eq([3, 0, 2].quickSort(), [0, 2, 3])
assert eq([3, 2, 0].quickSort(), [0, 2, 3])
assert eq([4,3,9,25,0,-19,55,43].quickSort(), [-19,0,3,4,9,25,43,55])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment