Swiftで乱択クイックソートを実装してみた

はじめに

僕の好きな本の一つに「数学ガール」があります。 高校生のとき帰りに寄り道した本屋でたまたま出会って以来数学の楽しさを知り、 今情報系の道に進んでいる一つの理由だったりする思い出深い本です。

今回、勉強がてらアルゴリズムを実装したいなーと思ったので数学ガールの中からネタを探すことにしました。 そこで選ばれたのがこちら↓

数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)

この中から特にクイックソートに焦点をあて、最近勉強中のSwiftで実装してみました。

(ちなみにSwiftではary.sort { $0 < $1 }と書くことで簡単にソートできます。)

クイックソートとは

ソートとは、配列の要素をある規則にしたがって並べなおす操作です。

クイックソートはそのソートをおこなうアルゴリズムの一つなのですが、名前の通り比較的速い(少ないステップ数でソートできる)アルゴリズムです。 詳しくは述べませんが、計算量は平均で、最悪の場合はになります(nはデータサイズ)。

クイックソートは分割統治法と呼ばれるアイデアを利用しています。 分割統治法とは、大きな問題を小さな問題に分けその小さな問題ごとに解くという手法のことです。 クイックソートでは、ある要素(ピボット)を基準とし、それより大きい数字のグループと小さな数字のグループに分け、それぞれのグループでソートをします(下図参照)。

クイックソートはピボットの選び方を変えることでソートの過程が変化します。 ピボットの選び方は単に配列の最初(最後)の要素を選ぶ方法や、数字からなる配列をソートする場合には平均値や中央値を用いることもあります。

今回は単に配列の最初の要素を選ぶ方法と、数学ガールの中で紹介されているピボットをランダムに選ぶ方法の2種類の方法で実装しました。 ランダムにピボットを選択する方法は乱択クイックソートと呼ばれ、最悪計算量をに抑えられる方法ということで本の中で紹介されていました。

(計算量の数学的な議論に興味のある方はぜひ数学ガールを読んでみてください！)

(引用: Wikipedia)

実装

クイックソートは大きく以下のステップに分かれます。

1. pivotの選択。
2. 配列を「pivotより小さい数字、pivot、pivotより大きな数字」の順に並び替える。
3. pivotの左側(右側)で同様の操作を繰り返す。

クイックソートではSTEP3で再帰処理をするので、そのために関数を

func quicksort (ary: inout [Int], l: Int = 0, r: Int = ary.count - 1)

として実装を進めました。 aryはソートする配列、l, rはそれぞれソートする範囲を示す値(left, right)です。

僕が再帰処理をするときにいつも持っている悩みが、外部から呼び出す関数と内部で再帰的に呼び出す関数で引数を合わせることができず、それぞれ別の関数で実装しなければならないということです。 外部から呼び出すときはシンプルに保ちたいのですが、再帰的に呼び出す際には様々引数が必要になることが多く、一つの関数で実現できないという問題です。 Swiftではデフォルト引数を設定できるので、デフォルト引数を使うことで一つの関数として実現できました。

ここからはSwiftならではの引っかかった点を備忘録的に書いていきます。

関数内で配列を操作する(値渡しと参照渡し)

ソートでは配列の要素を入れ替える操作が必要になります。 しかし、Swiftの場合関数の引数は値渡しになります。 このままでは元の配列の要素を入れ替えることができないので、値渡しではなく参照渡しにする必要があります。

このためには関数定義の際にinoutを用います。 また関数を呼ぶ際にinoutで指定された引数は&argのように&マークを付けて渡します。

クイックソートの実装の際には具体的に以下のように書きました。

func quicksort (ary: inout [Int], l: Int = 0, r: Int = ary.count - 1) {
    // クイックソートの実装
}

// main function
var ary = [5, 6, 2, 3, 8, 1, 9, 7, 4]
quicksort(ary: &ary)

ちなみに、元の配列を維持したまま、ソートされた新しい配列が欲しい時もあると思います。 そのような場合、

func quicksort(ary: [Int]) -> [Int] {
    // ソートする
    return ary
}

のように書きたくなると思います。 しかし、Swiftでは引数はletで渡されるため配列を操作することができません。 このような場合には、

func quicksort(ary: [Int]) -> [Int] {
    var ary = ary
    // ソートする
    return ary
}

と書くことで実現可能になります。

(Swift 3から関数定義の際にvarをつけて変更可能にすることはできなくなりました。)

配列の要素の入れ替え (swap関数)

配列の要素を入れ替える際、Swiftで用意されているswap関数を利用すると簡単に実現できます。 前述の通りSwiftは値渡しなのでswap関数を呼ぶ際には&をつけて参照渡しにする必要があります。

swap関数での注意点は、同じ変数を渡すとエラーを吐き出すことです。 エラーはswapping a location with itself is not supportedと表示されていました。 今回の実装方法ではswapするときに用いる2変数が配列の同じindexを指す可能性があるので、swap関数を使うたびにif文でチェックしています。

(ここらへんをシンプルに書ける方法を模索中です。。)

乱数の生成

乱択クイックソートを実装する際に乱数を生成する必要があります。 乱数を生成する関数は何種類かあるのですが、arc4random_uniform()を用いると良いらしいです。 この関数は「0から引数で与えられた値の間から乱数を生成して返す」関数で、UInt32で値を与える必要があります。 また、戻り値もUInt32で返ってきます。 そのためにUInt32<->Intの型に注意して利用する必要がありました。

乱択クイックソートでピボットを選択する際には以下のように書きました。 arc4random_uniformに渡す際はUInt32にキャストし、戻ってきた値はIntにキャストして使っています。

let ran = Int(arc4random_uniform(UInt32(r - l))) + l

(ここの実装に関しては、配列のindexを示すl, r, ranなどをUInt32で実装すれば、いちいちキャストする必要が無くシンプルに書けたのかなと今思ってます。。)

コマンドラインからの実行

Playgroundを用いてもよかったのですが、興味があったこともありSwiftをコマンドラインから実行するようにして開発を進めました。 gccのようにswiftcを用いてコンパイル→実行というのも可能なのですが、正直面倒です。 そこで調べているとスクリプトのように実行できる方法を見つけたのでその方法を用いました。

そのために必要なことはファイルのはじめに#!/usr/bin/swiftと書くだけです。 これを書いておくとコマンドラインで$ ./FILENAME.swiftと実行することができます。

コード

実際のコードを以下に貼っておきます。 一応動作確認しましたが、間違いなど見つけた際にはコメントしていただけると幸いです。

クイックソート

#!/usr/bin/swift

func quicksort (ary: inout [Int], l: Int = 0, r: Int = ary.count - 1)
{
    guard l < r else {
        return
    }
    
    // 配列の左端の値をピポットに選択
    let pivot = ary[l]
    var p = l
    for i in (l+1 ... r) {
        if(ary[i] < pivot) {
            p += 1
            // NOTE: swapping a location with itself is not supported
            if(p != i) {
                 swap(&ary[p], &ary[i])
            }
        }
    }
    // NOTE: swapping a location with itself is not supported
    if(p != l) {
        swap(&ary[l], &ary[p])
    }
    
    quicksort(ary: &ary, l: l, r: p-1)
    quicksort(ary: &ary, l: p+1, r: r)
}

var ary = [5, 6, 2, 3, 8, 1, 9, 7, 4]
quicksort(ary: &ary)
print(ary)

乱択クイックソート

#!/usr/bin/swift

// arc4random_uniform()を使うために必要
import Foundation

func random_quicksort (ary: inout [Int], l: Int = 0, r: Int = ary.count - 1)
{
    guard l < r else {
        return
    }
    
    // 乱数でピボットを選択->ピボットを左に持ってくる
    let ran = Int(arc4random_uniform(UInt32(r - l))) + l
    if(ran != l) {
        swap(&ary[l], &ary[ran])
    }
    
    // あとは通常のquicksortと同じ
    let pivot = ary[l]
    var p = l
    for i in (l+1 ... r) {
        if(ary[i] < pivot) {
            p += 1
            // NOTE: swapping a location with itself is not supported
            if(p != i) {
                swap(&ary[p], &ary[i])
            }
        }
    }
    // NOTE: swapping a location with itself is not supported
    if(p != l) {
        swap(&ary[l], &ary[p])
    }
    
    random_quicksort(ary: &ary, l: l, r: p-1)
    random_quicksort(ary: &ary, l: p+1, r: r)
}

var ary = [5, 6, 2, 3, 8, 1, 9, 7, 4]
random_quicksort(ary: &ary)
print(ary)