QuickSelect in CoffeeScript

QuickSelect is a known and simple algorithm for finding the kth smallest element in an array. The advantages of this algorithm are its linear average performance and the constant memory it requires, in addition to simple implementation.

The simplest solution is of course sorting the array using a built-in method of any language and then accessing the kth element in the sorted array. But, it may become an issue when working with large sets – O(n*log n) vs. O(n).

Implementation

class QuickSelect
constructor: (@arr) ->

kth: (k) ->
@_select(0, @arr.length - 1, k)

median: ->
@kth Math.floor(@arr.length / 2)

_swap: (i, j) ->
tmp = @arr[i]
@arr[i] = @arr[j]
@arr[j] = tmp

_partition: (left, right, pivotIndex) ->
pivotValue = @arr[pivotIndex]
@_swap pivotIndex, right
storeIndex = left
for i in [left..right]
if @arr[i] < pivotValue
@_swap storeIndex, i
storeIndex++
@_swap right, storeIndex
return storeIndex

_choose_random_pivot: (left, right) ->
left + Math.floor(Math.random() * (right - left + 1))

_select: (left, right, k) ->
if left == right
return @arr[left]

while true
pivotIndex = @_choose_random_pivot left, right
pivotIndex = @_partition(left, right, pivotIndex)
if k == pivotIndex
return @arr[k]
else if k < pivotIndex
right = pivotIndex - 1
else
left = pivotIndex + 1

Usage examples

describe "QuickSelect", ->
describe "1 item", ->
selector = new QuickSelect [1]
it "Should return the item", -> selector.kth(0).should.equal(1)

describe "2 items", ->
selector = new QuickSelect [2,1]
it "Min should be 1", -> selector.kth(0).should.equal(1)
it "Max should be 2", -> selector.kth(1).should.equal(2)

describe "3 items", ->
selector = new QuickSelect [2,1,3]
it "Min should be 1", -> selector.kth(0).should.equal(1)
it "Second should be 2", -> selector.kth(1).should.equal(2)
it "Max should be 3", -> selector.kth(2).should.equal(3)

These simple tests explains how the access to kth element is done. The tests are written also in CoffeeScript.

Performance comparison

Measuring time for 10,000 arrays, each accessed once at random location:
Array size 5,000 10,000 20,000
QuickSelect 1758ms 3393ms 6912ms
Sort 14302ms 32136ms 70566ms
As can be easily seen, the access to the kth smallest element is much faster. In cases where large arrays are used and repeated accesses are performed, this could be a bottleneck which can be easily solved.
Advertisements