QuickSelect is a known and simple algorithm for finding the k*th* 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 k

*th*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 k`

*th* 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 k

*th*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