swiftでクイックソート

qsort.swift

class Rand{
    var x: UInt = 1
    func next() -> UInt{
        x ^= x >> 12;
        x ^= x << 25;
        x ^= x >> 27;
        return x &* 2685821657736338717
    }
}

func qsort<T: Comparable>(inout a: [T], left: Int, right: Int) {
    if left < right {
        var i = left
        var j = right

        let pivot = a[left]
        while true {
            while a[i] < pivot { i+=1 }
            while pivot < a[j] { j-=1 }
            if i >= j { break }
            (a[i], a[j]) = (a[j], a[i])
            i+=1
            j-=1
        }
        qsort(&a, left, i-1)
        qsort(&a, j+1, right)
    }
}

let rand = Rand()
let size = 10000000
var list = [UInt]()

for i in 0..<size {
    list.append(rand.next())
}

qsort(&list, 0, size-1)

for i in 0..<10 {
    println(list[i*size/100])
}

Wikipediaのをみて移植。
Comparableプロトコルで汎用的に、inoutで参照渡し、swapにタプルが便利、乱数生成はxorshift、辺りがポイントです。