ソートアルゴリズムは効率良くできるか
前回基本ソートアルゴリズムの解説をした。
その時の計算量はO(n ^ 2)であり、基本的には効率は良くない。
ではもっと効率の良いアルゴリズムはあるか。
実際ある。
しかし少し難しくなるのでこの記事で理解を深めてほしい。
再帰
ソートアルゴリズムの解説に入る前に再帰の説明をさせてほしい。
この後に紹介するアルゴリズムではこの再帰を用いて効率性を上げている。
さて、再帰とは「あるプロシージャの処理の中でそのプロシージャ自身を呼ぶこと」を指します。
これによって特定の問題をより小さなサブ問題に分割して解決するための手法となる。
再帰はループを使用する代わりに、特定のタスクを繰り返し実行するためによく使用される。
再帰の基本的なパターンは次のようになる。
基本ケース：再帰の終了条件。これがないと、関数は無限に自分自身を呼び出し続け、スタックオーバーフローを引き起こします。
再帰ケース：関数が自分自身を呼び出すケース。ここでは、問題をより小さなサブ問題に分割します。
例えば再帰を使用して階乗を計算するGoのコードを見てみよう。
このコードでは、factorial関数は自分自身を呼び出している。
基本ケースはn == 0で、このときは1を返し、再帰ケースではn * factorial(n-1)を返す。
nの階乗を計算します。
package main
import "fmt"
func factorial(n int) int {
// 基本ケース
if n == 0 {
return 1
}
// 再帰ケース
return n * factorial(n-1)
}
func main() {
fmt.Println(factorial(5)) // Output: 120
}
上記ケースでは計算量削減のメリットは特にないが、ソートアルゴリズムの効率化には有効になります。
O(n ^ 2)よりも効率の良いソートアルゴリズム
ここからアルゴリズムを２つ紹介する。
過去にこちらの記事で紹介したアルゴリズムは要素数がnの場合の時間計算量は**O(n ^ 2)**だった。
これよりも効率を良くしたアルゴリズムがいくつかある。
今回はクイックソートとマージソートを紹介する。
（ただ２つのアルゴリズムの説明をするとめちゃ長くなるので詳細説明は割愛する。筆者がしっかり理解していないわけではない）
クイックソート
クイックソートは基準を一つ決め、その基準よりも小さい値を左に、大きい値を右に移動させるアルゴリズムです。
基準で分割された2つの領域内で更に基準を決めて分割をする動作をする。
コードで示すと以下のようになる。
func quickSort(numbers []int) {
var _quickSort func(numbers []int, low, high int)
_quickSort = func(numbers []int, low, high int) {
if low < high {
partitionIndex := partition(numbers, low, high)
_quickSort(numbers, low, partitionIndex-1)
_quickSort(numbers, partitionIndex+1, high)
}
}
_quickSort(numbers, 0, len(numbers)-1)
}
func partition(numbers []int, low, high int) int {
i := low - 1
pivot := numbers[high]
for j := low; j < high; j++ {
if numbers[j] <= pivot {
i++
numbers[i], numbers[j] = numbers[j], numbers[i]
}
}
numbers[i+1], numbers[high] = numbers[high], numbers[i+1]
return i + 1
}
ここで再帰を使っている。
配列を半分に分割する（log nのステップ）と、各ステップで全ての要素を見る（nの操作）ことから平均計算量は**O(nlog(n))**となり一般的にはバブルソートなどよりは効率は良くなる。
またin-placeな処理であるため追加のメモリをほとんど必要としない。
マージソート
マージソートは
- 対象の配列に対してデータを2分割を繰り返し要素数を1にする
- 要素同士を大小比較をしながら戻す（マージする）
を繰り返すアルゴリズムです。
こちらもコードを見てみよう。
func mergeSort(numbers []int) []int {
result := make([]int, 0)
if len(numbers) <= 1 {
return numbers
}
center := len(numbers) / 2
left := numbers[:center]
right := numbers[center:]
r := mergeSort(left)
l := mergeSort(right)
i, j := 0, 0
for i < len(l) && j < len(r) {
if l[i] <= r[j] {
result = append(result, l[i])
i++
} else {
result = append(result, r[j])
j++
}
}
for i < len(l) {
result = append(result, l[i])
i++
}
for j < len(r) {
result = append(result, r[j])
j++
}
return result
}
クイックソートと同様に再帰を使っている。
配列を半分に分割する（log nのステップ）と、各ステップで全ての要素を見る（nの操作）という操作からマージソートも時間計算量は**O(n log n)**となる。
ただし新しい配列を作成するため、空間計算量はO(n)となる。
まとめ
機械学習、AIで大量データのやり取りに効率的なアルゴリズムの価値がまた上がっているように思う。
基本的なアルゴリズムを学習して皆さんのサービスを爆速にしてみてください！