Quicksort

source.coffee

quickSort = (array) ->
  if array.length <= 1
    array
  else
    p = pickPivot array
    values = splitArray p, array
    lesser = quickSort values.lesser
    greater = quickSort values.greater
    (lesser.concat array[p]).concat greater

pickPivot = (array) ->
  array.length / 2 | 0
  
splitArray = (p, array) ->
  lesser = []
  greater = []
  for x, i in array
    if x <= array[p] and i != p
      lesser.push x
    else if i != p
      greater.push x
  lesser: lesser, greater: greater

spec.coffee

describe "quicksort", ->
  describe "pickPivot", ->
    it "can choose a pivot", ->
      expect(pickPivot([1,2,3])).toEqual 1
    it "can choose a pivot on an even length list", ->
      expect(pickPivot([1,2,3,4])).toEqual 2
    it "can handle an empty array", ->
      expect(pickPivot([])).toEqual 0
      
  describe "sorting", ->
    it "can sort an array of 1", ->
      expect(quickSort([1])).toEqual [1]
    it "can sort a sorted array of 2", ->
      expect(quickSort([1,2])).toEqual [1,2]
    it "can sort an unsorted array of 2", ->
      expect(quickSort([2,1])).toEqual [1,2]
    it "can sort an unsorted array of length 10", ->
      expect(quickSort([2, 5, 78, 4, 12, 33, 65, 74, 88, 3])).toEqual [2, 3, 4, 5, 12, 33, 65, 74, 78, 88] 
    it "can sort an array of the same value", ->
      expect(quickSort([4, 4, 4, 4, 4])).toEqual [4, 4, 4, 4, 4]
  
  describe "split array", ->
    it "should split an array", ->
      expect(splitArray(1, [1, 2, 3])).toEqual
        lesser: [1]
        greater: [3]