No Programming, No Life

プログラミング関連の話題や雑記

GroovyでQuickSortラムダ式版

おださん(id:odashinsuke)のところでGinAに載っているQuickSortについて書かれていたので
ラムダ式版にさらに改変してみた。

ダックタイピングの恩恵 - お だ のスペース

2010-10-10追記

クイックソートのお題だったので、#g100pon No.47 として下記コードを提出致しました。

QuickSort.groovy

// g100pon #47 QuickSort

def quickSort(lambda, list) {
    if (!list || list.size() < 2) return list
    def pivot  = list[0] // とりあえず先頭のものを基準にする
    def middle = list.findAll{ it == pivot }
    def left   = list.findAll{  lambda(it, pivot) } - middle
    def right  = list.findAll{ !lambda(it, pivot) } - middle
    quickSort(lambda, left) + middle + quickSort(lambda, right)
}

// 昇順
def quickAsc = this.&quickSort.curry(){ a, b -> a < b }
// 降順
def quickDesc = this.&quickSort.curry(){ a, b -> a > b }

def list = null
assert quickAsc(list)  == null
assert quickDesc(list) == null

list = []
assert quickAsc(list)  == []
assert quickDesc(list) == []

list = [1]
assert quickAsc(list)  == [1]
assert quickDesc(list) == [1]

list = [2, 1]
assert quickAsc(list)  == [1, 2]
assert quickDesc(list) == [2, 1]

list = [2, 1, 3]
assert quickAsc(list)  == [1, 2, 3]
assert quickDesc(list) == [3, 2, 1]

list = (1..100).toList().sort{ Math.random() }
assert quickAsc(list)  == (1..100).toList()
assert quickDesc(list) == (100..1).toList()

list = ('a'..'z').toList().sort{ Math.random() }
assert quickAsc(list)  == ('a'..'z').toList()
assert quickDesc(list) == ('z'..'a').toList()

list = [1.0f, 'a', 100, null]
assert quickAsc(list)  == [null, 1.0f, 'a', 100]
assert quickDesc(list) == [100, 'a', 1.0f, null]

list = 'Karin and Dierk'
assert quickAsc(list)  == '  DKaadeiiknnrr'.toList()
assert quickDesc(list) == 'rrnnkiiedaaKD  '.toList()

I'm trying to write Quick Sort in Groovy. /update 2010-10-10 (using #g100pon No.47) · GitHub

解説

ラムダ式をカリー化して埋め込むことですっきりした使い心地になります。
素敵ですね。