Category Archives: QuickSelect

QuickSelect in CoffeeScript

Posted by Eli Shalom on

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.