分割統治法とクイックソートについて。

分割統治法


問題を分割して解決する方法。雑な絵で書くと下記のような感じ。

クイックソートはこの分割統治法を用いたアルゴリズムの一つです。

クイックソート


前述のとおり、クイックソートはこの分割統治法を用いたアルゴリズムです。具体的には配列の中から基準となる値(ピボットという)を選んでそれを基にピボットより大きい値群と小さい値群に分割します。配列を分割できなくなるまで繰り返して分割します。これを繰り返し、最終的にそれらをくっつけることで全体のソートを行ないます。

※すみません、下記の図はソートの部分が抜けているので正確性に欠けます(あとホワイトボード撮影アプリで撮影したときに、補正で最後の10が0になってしまいました)

計算量


クイックソートの計算量は基準となる値(ピボット)をどれで選ぶかによって変わります。

平均計算量

平均計算量は $O(n log n) = O(n) × O(log n)$ です。例えば、下記のように常に2分割したようなケースだと…

$O(8) × O(log_{2} 8)$ なので $O(8 log_{2} 8)$ となります。

最悪計算量

最悪の計算量は常に配列が分割できなかったケースなので $O(n^2)$となります。

Scalaで実装


クイックソートでピボットをランダムで選ぶ方法をScalaで実装すると下記のような感じなります。filter使ってるのは許してほしい…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import scala.util.Random

object QuickSort extends App {

val random = new Random()

println(quicksort(Seq(1,5,8,4,16,2,10)))

def quicksort(nums: Seq[Int]): Seq[Int] = {

if (nums.length < 2) {
return nums
}

val pivot: Int = nums(random.nextInt(nums.length))
val less: Seq[Int] = nums.filter(x => x < pivot)
val greater: Seq[Int] = nums.filter(x => x > pivot)

println(Seq.concat(less, Seq(pivot), greater))
Seq.concat(quicksort(less), Seq(pivot), quicksort(greater))
}

}

/*
出力サンプル
List(1, 5, 4, 2, 8, 16, 10)
List(1, 5, 4, 2)
List(2, 4, 5)
List(10, 16)
List(1, 2, 4, 5, 8, 10, 16)
*/

おわり。

参考書籍


なっとく! アルゴリズム