はじめに
最近はソートアルゴリズムについて興味を持っていて、Kotlinでクイックソートを書いていました。書き方がいろいろあって、いくつか試してみたのでその内容を記事に起こしてみたいと思います。
クイックソートの概要
クイックソートは名前の通り高速なソートアルゴリズムで、多くの言語の標準ライブラリで採用されています。平均計算量が$O(n log n)$で、定数倍も軽くてマージシートやヒープソートより速いとされます。一方、素朴な実装だと最悪計算量が$O(n^2)$になってしまうという欠点もあります。実用性を追求するなら、ある程度工夫してそれを避ける必要があります。
また、不安定ソートとして知られています。標準ライブラリとしては、クイックソートの実装以外にも安定ソートの実装も別途提供されているのが一般的だと思います。
クイックソートの手順
クイックソートはソート対象の中から一つ軸となる値（ピボット）を選んで、配列内の値をピボットより小さいか大きいかで振り分ける操作を実行します。振り分けたら、それぞれに対して再帰的に同じ操作をします。これを繰り返していくと小さくなった部分がソート済みの状態になります。具体的には、空の配列や要素が1つしかない配列は何もしなくてもソート済みといえます。要素数が2つまで減った部分についてこの操作をすると、空配列と要素が1つの配列に分解されます。それらはいずれもソート済であり、ピボットを真ん中にしれそれらを並べた全体もソート済になります。そのようにしてソート済になった部分をつなぎ合わせていくと全体がソートされた状態になる、みたいなイメージです。
（厳密な説明ではありませんが…）
小分けした部分に対して再帰的に処理を実行する方法
そのまま再帰を使って実装するのが一般的だと思います。
ピボットの選び方と計算量
ピボットを選ぶ方法はいろいろ考えられます。固定で先頭の値を選ぶみたいな方法なら楽ちんですね。ただ、このような選び方だと問題が生じることもあります。最悪計算量が$O(n^2)$になる場合があると書きましたが、それはピボットの選び方に深く関わります。
ピボットより小さい値と大きい値に振り分けるわけですが、ピボットが非常に小さい値または大きい値だと、均等に分かれず偏りが発生します。操作を再帰的に実行していくわけですが、偏りがあるとそれだけ再帰の階層が深くなります。毎回偏る場合は再帰の階層が配列の要素数とほぼ同じになってしまいます。各階層ごとの振り分ける操作の計算量が$O(n)$ですので、階層が最も深いケースだと$n$のかけあわせで計算量が$O(n^2)$になってしまいます。
逆にピボットの値がちょうど真ん中だと均等に分かれます。毎回均等に分かれると、要素数を$n$とすると階層の深さは$log n$になります。二分木の高さが$log n$なのと同じような話ですね。その場合は計算量が$O(n log n)$となり、これが最良のケースです。
ということで、毎回均等に分かれるようなピボットを選びたいところです。つまり中央値です。しかし、どうやってその処理をさせるかを考えると意外と簡単でないことがわかります。中央値を選ぶためには素朴に考えると大小関係を調べる必要がありますが、完全な中央値を求めるのであれば計算量が$O(n)$となり、ちょっと遅いです。平均的には、時間をかけて完全な中央値を求めるよりは、時間をかけずに中央値かもしれない値を選んで処理していくほうが速そうです。
具体的な方法としてはいくつかあり、たとえば全部ではなく3個くらい調べてからその中の中央値を選ぶ、ランダムで選ぶ、などの方法は考えられます。今回は、ランダムで選ぶ方法にて実装してみたいと思います。そんな方法でいいのかといえば、実のところそれで十分高速になることが一般的に知られています。個別に見ると偏ってしまうような値が選ばれてしまうこともありますが、理想的な値が選ばれることもあり、平均的には高速になります。ちょっと不思議ですね。
振り分けた値の持ち方
ピボットより小さい値を持つ可変長配列、ピボットより大きい値を持つ可変長配列、をそれぞれ定義して追加していくのが楽です。ただ、その場合は多少メモリを消費します。与えられた配列内で要素をスワップする処理とすることで追加のメモリを（ほとんど）消費せずに実装することも可能です。
実装のテスト方法
今回実装するクイックソートが正しく動くかどうかをテストする方法についてです。自分でテストデータを用意してテストするのは少々大変です。比較的楽で、かつ一定の正しさを担保できる方法として、既存のプログラミング問題の解答コードとして提出するという方法があります。今回はその方法でテストしてみたいと思います。
今回は以下の2つの問題を使います。問題の詳細には触れませんが、いずれの問題も素直に解くのであればソートが必要になります。普通に解くなら標準ライブラリを使えばいいのですが、今回はそのかわりに自分で実装したクイックソートを使ってみるわけです。
上を問題C、下を問題Dとしましょうか。これらの違いですが、まあ全然違う問題なのですが、今回の用途における違いは、問題Cはソート対象に重複要素がない、問題Dは重複要素があり得る（全要素同じの場合もある）という点です。これはピボットと同じ値の扱い方で結果に差が出ます。
また両問題に共通するポイントとして、計算量が$O(n^2)$とかだと遅すぎて不正解になります。$O(n log n)$なら正解になりますが、ピボットでの振り分けが偏って最悪計算量の$O(n^2)$になってしまうと不正解になります。クイックソートの実装をテストするのにちょうどいいですね。
実装
それは実装していきます。今回はいくつかの種類の実装をしています。可変長配列を定義して振り分けていく方法のほうが実装はわかりやすいので、まずはそちらで実装してみます。
可変長配列を使った実装
fun quickSort(list: List<Int>): List<Int> {
// 要素数が1以下ならソート済とみなせる
if(list.size <= 1) {
return list
}
// ピボットを選ぶ
val pivotIndex = Random.nextInt(0, list.size)
val pivot = list[pivotIndex]
// ピボットの前後に分割
val smaller = mutableListOf<Int>()
val greaterOrEqual = mutableListOf<Int>()
for(i in list.indices) {
if(i == pivotIndex) {
continue
}
if(list[i] < pivot) {
smaller.add(list[i])
} else {
greaterOrEqual.add(list[i])
}
}
// 前後それぞれで再帰
return quickSort(smaller) + listOf(pivot) + quickSort(greaterOrEqual)
}
そんなに複雑ではない実装になりました。正しく動作するのかテストしてみます。
まずは問題Cですが、以下の解答のリンクです。
テスト結果は以下のようになっています。これは27件のテストを実行し、全ての結果がAC（正解）となったことを示します。つまり正解です。
実行時間ですが、最も実行が遅かったケースで以下の通りです。
正解できる程度には速いですが、なんか微妙ですね。そもそもKotlinだとオートボクシング/アンボクシングが発生してしまうというのもありますが、可変長配列を生成するコストの分もあると思います。
続いて問題Dです。
結果はこちら。TLE（実行制限時間超過）で不正解となりました。つまり実行が遅すぎるということですね。
6件のテストケースで失敗していますが、この6件はどうやらいずれもほとんど（あるいは全て）の要素が同じ値となっている配列が入力されるケースのようです。1
全て同じだとすると、先ほどのコードだと
if(list[i] < pivot) {
smaller.add(list[i])
} else {
greaterOrEqual.add(list[i])
}
全ての要素がgreaterOrEqualのほうに振り分けられます。なにしろ全部同じ要素なので、ランダムに選んだピボットがどれであろうと必ずそうなります。これだと再帰の呼び出し階層が最も深いパターンになり、計算量$O(n^2)$になってしまうわけですね。
これを回避するには、いくつか方法があります。たとえば、ピボットと同じ値は小さい方のリストと大きい方のリストのうちどちらに割り振るかをランダムで決める方法や、ピボットと同じ値を持つリストを作ってそこに割り振る方法、などが考えられます。
可変長配列を使った実装（ピボットと同じ値の考慮あり版）
ランダムに割り振る実装
まずはランダムに割り振る実装です。こんな感じで、ピボットと同じなら2値の乱数を使ってどちらかに割り振ります。どちらに割り振られるかはランダムですが、ほぼ均等になるはず。
fun quickSort(list: List<Int>): List<Int> {
// 要素数が1以下ならソート済とみなせる
if(list.size <= 1) {
return list
}
// ピボットを選ぶ
val pivotIndex = Random.nextInt(0, list.size)
val pivot = list[pivotIndex]
// ピボットの前後に分割
val smaller = mutableListOf<Int>()
val greater = mutableListOf<Int>()
for(i in list.indices) {
if(i == pivotIndex) {
continue
}
if(list[i] < pivot) {
// ピボットより小さい値の場合
smaller.add(list[i])
} else if(list[i] > pivot) {
// ピボットより大きい値の場合
greater.add(list[i])
} else {
// ピボットと同じ値の場合はランダムにどちらに割り振る
if(Random.nextInt(2) == 0) {
smaller.add(list[i])
} else {
greater.add(list[i])
}
}
}
// 前後それぞれで再帰
return quickSort(smaller) + listOf(pivot) + quickSort(greater)
}
テスト結果はこちら。
無事、どちらの問題も正解となりました。
（提出リンク先のコメントがちょっとおかしいのはこっそり直しました）
ピボットと同じ値を持つリストを作る実装
ピボットと同じ値はそれ専用のリストに詰める方法です。その場合、そのリストについては再帰する必要はありません。
fun quickSort(list: List<Int>): List<Int> {
// 要素数が1以下ならソート済とみなせる
if(list.size <= 1) {
return list
}
// ピボットを選ぶ
val pivotIndex = Random.nextInt(0, list.size)
val pivot = list[pivotIndex]
// ピボットの前後に分割
val smaller = mutableListOf<Int>()
val greater = mutableListOf<Int>()
val same = mutableListOf<Int>()
for(i in list.indices) {
if(list[i] < pivot) {
// ピボットより小さい値の場合
smaller.add(list[i])
} else if(list[i] > pivot) {
// ピボットより大きい値の場合
greater.add(list[i])
} else {
// ピボットと同じ値の場合
same.add(list[i])
}
}
// 前後それぞれで再帰
return quickSort(smaller) + same + quickSort(greater)
}
テスト結果です。
いずれの問題でも正解となりました。
可変長配列を使わない実装
上記の実装はわりとシンプルでわかりやすいのですが、可変長配列を使うためある程度メモリを食うという問題があります。現代ではそれが問題になることはあまりないかとは思います。ただ、クイックソートは一般的に追加的なメモリを（ほとんど）使わないことが期待されるアルゴリズムです。なので可変長配列を使わない実装についても触れておきたいところです。
その場合もピボットの前後に分けて再帰するというのは同じです。ピボット前後の振り分けは配列内でスワップすることにより実現します。ピボットより小さい値にだけ、または大きい値にだけ再帰呼び出しを適用するには配列全体ではなく一部だけ扱う必要がありますが、それは開始インデックスと終了インデックスを扱うことで実現します。
なお、配列内でのスワップで実装することにより追加的なメモリを使用しないソートを内部ソートといいます。つまりクイックソートは、一般的には内部ソートであることが期待されます。
ピボットと同じ値を考慮しない実装
まずはピボットと同じ値を考慮しない、つまり問題Dは通らない実装です。まずはシンプルなケースからということで。
こんな感じになります。
// ピボットの前後に振り分ける処理
fun partition(list: MutableList<Int>, start: Int, end: Int): Int {
// ピボットの選択
val pivotIndex = Random.nextInt(start, end + 1)
val pivot = list[pivotIndex]
// ピボットが処理されないように末尾に退避
swap(list, pivotIndex, end)
// 振り分けに使うインデックス
var storedIndex = start
// 末尾にピボットがあるのでそれは処理しないようにend - 1まで処理
for(i in start until end) {
// ピボットより小さい値を左に移動する
if(list[i] < pivot) {
swap(list, storedIndex, i)
storedIndex++
}
}
// 退避しておいたピボットを戻す
swap(list, storedIndex, end)
// ピボットの位置を返す（初期位置ではなく更新後の位置）
return storedIndex
}
fun quickSort(list: MutableList<Int>, start: Int = 0, end: Int = list.size - 1) {
// 要素数が1以下ならソート済とみなせる
if(start >= end) {
return
}
// ピボットの前後に振り分ける
val pivotIndex = partition(list, start, end)
// ピボットより小さい部分配列の再帰
quickSort(list, start, pivotIndex - 1)
// ピボットより大きい部分配列の再帰
quickSort(list, pivotIndex + 1, end)
}
private fun swap(list: MutableList<Int>, i: Int, j: Int) {
val tmp = list[i]
list[i] = list[j]
list[j] = tmp
}
storedIndexの管理がポイントですね。storedIndexは必ずi以下で、storedIndexとiのそれぞれの指す値を入れ替えることが値を左（ピボットより小さいほう）へ振り分けることに相当します。逆に、入れ替えないことは右（ピボットより大きいほう）へ振り分けることに相当します。storedIndexは常にピボットより小さい値の末尾の1つ右を指しており、最終的にstoredIndexの位置がピボットの位置になります。
末尾に退避しておいたピボットをstoredIndexの位置に移動する際の入れ替えでstoredIndexが指していた位置にもともとあった値が右に移動します。それが問題ないかというと、storedIndexが指す位置にあった値とは左に移動しなかった値であることから、必ずピボット以上の値といえるので問題ありません。
テスト結果はこちら。
問題Cは通ります。メモリ使用量が減っており、実行速度もかなり速くなっているようです。
問題Dは通りません。こちらの実装ですと、ピボットより小さい値のみを左に移動するのでピボットと同じ値は全て右に振り分けられるため、全て同じ値のテストケースで偏って遅くなります。
ピボットと同じ値をランダムで振り分ける実装
ピボットと同じ値をどう考慮するかですが、基本的な考え方としては可変長配列を使う場合と同じです。まずは、左右にランダムで振り分ける実装を考えてみます。
// ピボットの前後に振り分ける処理
fun partition(list: MutableList<Int>, start: Int, end: Int): Int {
// ピボットの選択
val pivotIndex = Random.nextInt(start, end + 1)
val pivot = list[pivotIndex]
// ピボットが処理されないように末尾に退避
swap(list, pivotIndex, end)
// 振り分けに使うインデックス
var storedIndex = start
// 末尾にピボットがあるのでそれは処理しないようにend - 1まで処理
for(i in start until end) {
// ピボットより小さい値を左に移動する
// ピボットと同じ値も二分の一の確率で左に移動する
if(list[i] < pivot || (list[i] == pivot && Random.nextInt(2) == 0)) {
swap(list, storedIndex, i)
storedIndex++
}
}
// 退避しておいたピボットを戻す
swap(list, storedIndex, end)
// ピボットの位置を返す（初期位置ではなく更新後の位置）
return storedIndex
}
fun quickSort(list: MutableList<Int>, start: Int = 0, end: Int = list.size - 1) {
// 要素数が1以下ならソート済とみなせる
if(start >= end) {
return
}
// ピボットの前後に振り分ける
val pivotIndex = partition(list, start, end)
// ピボットより小さい部分配列の再帰
quickSort(list, start, pivotIndex - 1)
// ピボットより大きい部分配列の再帰
quickSort(list, pivotIndex + 1, end)
}
private fun swap(list: MutableList<Int>, i: Int, j: Int) {
val tmp = list[i]
list[i] = list[j]
list[j] = tmp
}
ここでOR条件を付け足したところが差分です。ピボットと同じ値だった場合も、概ね二分の一の確率で左に割り振ります。
// ピボットより小さい値を左に移動する
// ピボットと同じ値も二分の一の確率で左に移動する
if(list[i] < pivot || (list[i] == pivot && Random.nextInt(2) == 0)) {
swap(list, storedIndex, i)
storedIndex++
}
テスト結果がこちらです。
無事問題Dも解けました。こちらもメモリ使用量が減り、実行速度も速くなっています。
ピボットと同じ値をまとめる実装
続いて、ピボットと同じ値はそれでまとめて再帰呼び出ししない実装です。可変長配列を使う場合はシンプルでしたが、使わない実装だとちょっとややこしくなります。
ピボットと同じ値（複数）をまとめるためには、その「左端の位置」と「右端の位置」という2つの情報が必要です。ピボットより小さい値があった場合に左の値と入れ替える操作を実行するのは同じですが、ピボットより大きい値があった場合に右の値と入れ替えるという操作も必要となります。
実装としてはこんな感じ。
fun partition(list: MutableList<Int>, start: Int, end: Int): Pair<Int, Int> {
val pivotIndex = Random.nextInt(start, end + 1)
val pivot = list[pivotIndex]
// ピボットと同じ値の左端（含む）
var lt = start
// ピボットと同じ値の右端（含む）
var gt = end
var i = start
// gtより右は調査済みの値なので、gtを超えない間繰り返す
while (i <= gt) {
if(list[i] < pivot) {
// ピボットより小さい値
swap(list, i, lt)
i++
lt++
} else if(list[i] > pivot) {
// ピボットより大きい値
swap(list, i, gt)
// swapで左に来た値は未調査なのでiはインクリメントしない
gt--
} else {
// ピボットと同じ値
i++
}
}
return lt to gt
}
fun quickSort(list: MutableList<Int>, start: Int = 0, end: Int = list.size - 1) {
if(start >= end) {
return
}
val (lt, gt) = partition(list, start, end)
// ピボットと同じ値の位置はlt以上gt以下なので、その左側と右側で再帰
quickSort(list, start, lt - 1)
quickSort(list, gt + 1, end)
}
fun swap(list: MutableList<Int>, i: Int, j: Int) {
val tmp = list[i]
list[i] = list[j]
list[j] = tmp
}
コアの部分はここです。コメントの通り、ピボットより大きい値を入れ替えた後はループカウンタを更新しません。左から調べているため、右から移動してきた値はその時点だと未調査です。ループカウンタを更新しないことで、ループの次の回で調べられるようにします。この制御のために、ループはfor文ではなくwhile文で実装しています。
// gtより右は調査済みの値なので、gtを超えない間繰り返す
while (i <= gt) {
if(list[i] < pivot) {
// ピボットより小さい値
swap(list, i, lt)
i++
lt++
} else if(list[i] > pivot) {
// ピボットより大きい値
swap(list, i, gt)
// swapで左に来た値は未調査なのでiはインクリメントしない
gt--
} else {
// ピボットと同じ値
i++
}
}
テスト結果はこちら。
無事正解しました。
ヒープソートとの併用（イントロソート）
それなりにいい感じの実装になってきたかと思いますが、それでも乱数の引きが非常に悪い場合は遅くなる可能性があります。現実的には最悪計算量が$O(n^2)$に近くなることはほぼ起こらないと思われますが、確実とは言い切れません。それもあり、標準ライブラリなどで採用される実用的なクイックソートの実装では、さらに他の方法で最悪計算量が確実に$O(n log n)$になる工夫をしていることが多いようです。具体的には、再帰の階層が深くなった場合はヒープソートに切り替えるという方法です。
ヒープソートは平均計算量、最悪計算量ともに$O(n log n)$のアルゴリズムです。最悪計算量も$O(n log n)$なので、最悪計算量が$O(n^2)$に近くなることを確実に避けられます。内部ソートでもあり、クイックソートとの併用に向いています。
ヒープソートの詳細は以下の記事に書きました。
最悪計算量が$O(n^2)$に近くなることを確実に避けるだけならわざわざ併用せずに素のヒープソートを使えばいいのですが、クイックソートのほうがヒープソートより定数倍が軽くて高速なため、併用したほうが平均的に高速になります。ほとんどのケースはクイックソートで処理させて、ヒープソートはまさかの場合のための安全装置という考え方です。
このクイックソートとヒープソートを併用するアルゴリズムはイントロソートと呼ばれます。
イントロソートは以下のような実装になります。ピボット前後に振り分けるpartition関数と、ヒープソートを実行するheapSort関数が別途実装されているものとすると以下のようになります。
fun introSort(list: MutableList<Int>, depth: Int = 0, start: Int = 0, end: Int = list.size - 1, maxDepth: Int = 32) {
// 要素数が1以下ならソート済とみなせる
if(start >= end) {
return
}
// 再帰の階層が深くなったのでヒープソートに切り替える
if(depth == maxDepth) {
heapSort(list, start, end)
return
}
// ピボットの前後に振り分ける
val pivotIndex = partition(list, start, end)
// ピボットより小さい部分配列の再帰
introSort(list, depth + 1, start, pivotIndex - 1, maxDepth)
// ピボットより大きい部分配列の再帰
introSort(list, depth + 1, pivotIndex + 1, end, maxDepth)
}
こんな感じで再帰呼び出しの深さをカウントしていって、一定の数値に達したらヒープソートで処理して抜けるというだけのシンプルな実装になります。ヒープソートで処理するのは全体ではなくその時に処理したい範囲だけにします。
しきい値は配列の大きさをもとに計算するのが一般的っぽいのですが、ここでは単純化するために固定値で書いています。
それではこれをテストしてみます。以下ではヒープソートに切り替わっても動くことを確認するため、partition関数はピボットと同じ値を考慮しないバージョンを使っています。
いい感じです。クイックソート部分の実装は同じなので問題Cのほうは全部クイックソートで処理されているはず、問題Dのほうは全部ピボットと同じ値のテストケースについてはヒープソートに切り替わっているはず、ですね。
その他
他にもピボットを乱択ではなくもっと賢い方法で選んだり、対象の長さが小さくなった場合は挿入ソートに切り替えたり、ピボットを2つ使ったり、など多くの高速化手法があるようですが、けっこう難しそうなのでこの記事ではここまでにしておきます。
あと言語依存の話ですが、MutableList<Int>はIntArrayにしたほうが速そうではあります。
感想
一口にクイックソートといっても多様な方法があって面白いと思いました。ピボットの選び方を工夫したり、他のソートアルゴリズムと組み合わせたり、高速化のための手法がたくさんあります。実用的なアルゴリズムであるだけでなく、アルゴリズムを勉強するための題材としても興味深いですね！
-
テストケース内容を知るには以下から辿る必要があります。（2024/12現在は非公開ですがそのうち復活するらしい）
https://www.dropbox.com/scl/fo/5lkjmn5ptusaecxvjsnua/AAGZbbac5gFO4U9ulvRPRxI?rlkey=62xyo3nwqqm6rk8bkjr6c4npk&e=1&dl=0 ↩