いろんなソート

ソートとは

タイトルにある「ソート」を聞いたことがあるでしょうか？Excelを触ったことのある人ならご存知かもしれません。 英語の動詞であるソート(sort)は「分類する」「区分する」という意味を持ち、「並び替える」という意味で使われることが多いです。ここではプログラム上でこのソートを実行する方法について述べていきます。

用語確認など

昇順でソートする、降順でソートする、という表現がありますが、昇順は小さい順、降順は大きい順、と読み替えてください。

また、ここでは計算量、というものを使って説明をしていきます。よく用いられるのは「ランダウの記号」や「オーダー記法」と呼ばれる記法で、 \( O\left( N \right) \) や \( O\left( N^2 \right) \) と表します。

ここで右上についている数字は累乗を表すもので、 \( N^3 = N \times N \times N \) (\( N \)の\( 3 \)乗 ) 、 \( N^4 = N \times N \times N \) (\(N\)の\(4\)乗)といったようにその数字の分だけ \(N\)というなんらかの数字を掛け合わせる、というものです ( 冪 ( べき ) 乗の場合もあります)。

また\( \log \)(ログ)という対数関数を用いますが、これは先程の累乗の逆で、 \( \log_{2} N \) は「\( 2 \)の何乗が\( N \)になるのか」を表し、 \( \log_{2} 8 = 3 \) (ログ2の8)、 \( \log_{3} 243 = 5 \)(ログ2の243)となります。ざっくりと言うのであれば、桁数だと考えればよいです。 \( \log_{10} 100 = 2 \)、\( \log_{10} 152 = 2.18184 \ldots \)というように整数部分が(右下の数字の位取り記数法では)\(\left(桁数\right)-1\)と一致します。オーダー記法では \( O \left( \log N \right) \) と右下の数字を省略することが多いです。 要するにオーダー記法というのはある値(ここでは \( N \)の増加に対してどの程度増加するか、という度合いを表すもので、 \( O \left( N^2 \right) \)は\( N \)が\(2\)倍になると\(4\)倍、\(100\)倍になると\(10000\)倍になる、というものを表します。また \( N - 2 \times N + 5 \) などは \( O \left( N^2 \right) \) と、より大きく変化する部分のみ表記します。 前置きが長くなりましたが、本題に入っていきます。

総当り

すべての組み合わせを試し、昇順や降順になっていたらそれを選ぶ、という確実な方法です。

計算するのに要する時間、つまり時間計算量は \( O \left( N \times N! \right) \) です。ここで \( N! \)(\(N\)の階乗)とは \( 1 \times 2 \times 3 \times 4 \times \cdots \times \left( N - 1 \right) \times N \) のことで、 \( 10! = 3628800 \) , \( 15! = 1307674368000 \) と爆発的に増えていきます。

それぞれの並びについて、小さい順に並んでいるかどうか\( N \)個見て確かめるので \( N \times N! \) になっています。この場合、15個程度のデータを並び替えるだけでも膨大な時間がかかります。

3個の場合で少しやってみましょう。\( \{ 3, 1, 2 \} \)という3つの数字を並び替えてみます。並べ方をすべて挙げると \( \{ 3, 1, 2 \}, \{ 3, 2, 1,\}, \{ 1, 3, 2 \}, \{ 1, 2, 3 \}, \{ 2, 3, 1 \}, \{ 2, 1, 3 \} \) となり、昇順となっているのは \( \{ 1, 2, 3 \} \)、降順となっているのは\( \{ 3, 2, 1 \} \)でソートできました。

次は4個、と行きたいですが \( 4! = 24 \) 個も書きたくないので省略します。とにかく総当りでは時間がかかります。

バブルソート

総当たりよりはマシなソート方法がこれで、単純なルールなのでよく紹介される方法です。 昇順でソートする前提で進めます。まず \( 1 \)番目の数と\( 2 \)番目の数を比べて、\( 1 \)番目の数の方が大きければ2つの数を入れ替えます。次に\( 2 \)番目の数と\( 3 \)番目の数を比べて、\( 2 \)番目の数のほうが大きければ入れ替えます。―というように一番目から順番に2つずつ大小を比較し大きいものを\( N \)番目の 方へ持っていきます。

これで最大値が最後に来ることになります。これを次は\( 1 \)番目～\( \left( N-1 \right) \)番目に対して実行します。

すると二番目に大きい下図が\( N-1 \)番目に現れます。

このように最大値を最後の方に寄せていけば、最終的に昇順に並ぶことになります。 \( N \)個分最大値を最後の方へ寄せるので、時間計算量は \( O \left( N^2 \right) \) です。 \( O \left( N! \right) \) に比べれば小さいですが、それでも \( N \)が\( 1000 \)倍になれば\( N^2 \)は\( 1000000 \)倍になってしまうのでたくさんのデータになると何時間も時間がかかるようになってしまいます(このバブルソートを改良したシェーカーソートというものもあります)。

選択ソート

バブルソートと似た方針で、最小値または最大値を端に寄せていくソートです。今回は最小の要素と最初の要素を入れ替えていく方法を紹介します。

これも\( N \)個のうちから最小値を探すことを\( N \)回繰り返すので時間計算量は \( O \left( N^2 \right) \) となります。

挿入ソート

目的の要素以前がソートされている状態にしてあるとして、その要素を正しい位置に挿入していくソートです。図で見たほうがわかりやすいかもしれません。

\( \left( N - 1 \right) \) 回の挿入操作それぞれに \( O \left( N \right) \) を要するので計算量は \( O \left( N^2 \right) \) となります。(二分探索と呼ばれる手法を用いると比較回数を減らすことができます。詳細は各自で調べてみると良いでしょう。)

クイックソート

これまで \( O \left( N^2 \right) \) のアルゴリズムを紹介してきましたがここからは高速になってきます。このクイックソートは平均 \( O \left( N \log N \right) \) で計算できます。まず、ピボット(pivot)と呼ばれる、基準の値を一つ取ります。ここでは最初の値を取ることにします。そして、ピボットより小さい値を最初の方へ、ピボット以上の値を最後の方へ寄せます。

そしてピボット未満の部分、ピボット以上の部分をそれぞれクイックソートします。

このように、クイックソートの中でクイックソートを利用する、というようなものを再帰的呼び出しと言います。ただし、要素の数が1以下の場合は「ソートされている」と言えるので改めてなにか操作をすることなく打ち切る必要があります。そうでないと無限にソートしようとしてしまいます。

クイックソートはピボットの選び方によって所要時間が変化し、最悪時間計算量は \( O \left( N^2 \right) \) です。しかし、多くの場合においてこれは \( O \left( N \log N \right) \) で動作し、そのため高速なソートとして知られています。

コラム：再帰

さて、クイックソートの説明の中で再帰という単語が現れましたが、これについて例を挙げて補足しておきます。

「総当り」で登場した階乗の定義を見てみましょう。

\[ N! = 1 \times 2 \times 3 \times \cdots \times \left( N - 1 \right) \times N \]

これを再帰的に定義し直してみます。

\( N != 1 \times 2 \times 3 \times \cdots \times \left( N - 1 \right) \) の部分は \( \left( N - 1 \right) ! \) と表せるので、先程の式に当てはめると \( N != \left( N - 1 \right)! \times N \) となり、 \( N = 1 \) のとき \( N! = 1 \) なので \( N ! \) の再帰的定義は下記のようになります。

\[ \begin{eqnarray} N! = \begin{cases} 1 & \left( N = 1 \right) \\ N \times \left( N - 1 \right) & \left( N > 1 \right) \end{cases} \end{eqnarray} \]

これは「自然数\( N \)について、\( N = 1 \)のとき\( N != 1 \)、\( N > 1 \)のとき \( N! = N \times \left( N - 1 \right) ! \) 」を表すものです。階乗の定義の中に階乗が含まれていますが、この場合 \( N ! \)の定義の中に\( N ! \)自身、もしくは\( M ! \left( M > N \right) \)が現れない限り問題はありません。再帰という概念はそのうち数学でも出てくると思うので、覚えておいて損はないでしょう。

マージソート

今まで紹介したソートは「与えられたデータの領域の中だけで完結する」もの、つまり「\( a \)番目の要素と\( b \)番目の要素を比較、または交換する」のみでソートが可能でした。しかしこのマージソートでは、新しく別の領域を利用しなければなりません。

まずはデータを半分に分け、片方ずつマージソートをします。

そしてこの2つを「マージ」していくのですが、この時に新しい別の領域が必要になります。説明のためもともとの領域を\(A\)、用意する別の領域を\(B\)とします。

ここでのマージとは「ソートされた2つのデータを合成すること」なのですが、合成した後もソートされた状態になっているように合成します。実際に上の2つをマージしてみましょう。それぞれ先頭の要素を比較し、小さい方を領域Bに後ろから詰めていきます。

このようにしてマージした後、領域\(A\)を領域\(B\)で上書きすればマージ完了です。

時間計算量は \( O \left( N \log N \right) \) と高速ですが、領域\(B\)を用意する必要があり、このような「計算時に必要となる記憶領域の容量」を空間計算量と呼び、このマージソートでは空間計算量が \( O \left( N \right) \) です。

インプレースマージソート

マージソートでネックとなる空間計算量を \( O \left( 1 \right) \) 、つまり外部領域を使わずにできるようにしたのがこのインプレースマージソートです。ただし時間計算量が \( O \left( N \left( \log N \right)^2 \right) \) と少し遅くなります。

別の領域を使わないインプレースマージでは、クイックソートのような工夫をします。2つに分割した領域をそれぞれ領域 \( L, R \) とし、ピボットを \( p \)とすると、それぞれの領域について\( p \)を基準に\( p \)未満の要素を最初の方へ、\( p \)以上の要素を最後の方へ寄せます。ここでそれらの領域を \( L_{L}, L_{R}, R_{L}, R_{R} \) とすると、 \( L_{R} \) と \( R_{L} \) を入れ替えます。

そして領域 \( L_{L} \) と領域 \( R_{L} \) 、領域 \( L_{R} \) と領域 \( R_{R} \) をそれぞれインプレースマージします。

このようにすることで新たに領域を用意せずともマージが可能となります。

基数ソート

基数ソートは内部でバケットソートを使うのが一般的なので、バケットソートを先に紹介します。バケットソートは決まった範囲の値しか存在しないとわかっている時に可能なソートです。例えば1 ~ 5の値しかないものをソートするとき、「バケツ」と呼ぶ新たな領域を値の種類数分、ここでは5個用意します。そして元のデータを順番に見ていき、1なら「1のバケツ」に、2なら「2のバケツ」に、といったように順番に入れていきます。全て入れ終わったら、「1のバケツ」から順に入っている値を並べていきます。

バケットソートの時間計算量は、値の種類数をKとすると \( O \left( N + K \right) \) となります。多くの場合においてKは有限の値を取るため、時間計算量を \( O \left( N \right) \) とする場合もあります。また、最悪空間計算量も \( O \left( N + K \right) \) となります。

そして基数ソートとは、位取り記数法ができるもの(つまり普通の整数や小数)や文字数の決まったアルファベットのみの文字列などを要素とするデータである場合に適用できます。10進法における3桁以下の整数を例に取ってみましょう。下の位から順番に、種類数が10のバケットソートをしていきます。

各桁について値の種類数が有限なバケットソートをするので、桁数\( D \)とすると、時間計算量は \( O \left( D \left( N + 10 \right) \right) = O \left( DN \right) \) となります。10進数に限らず、各桁について \( K \)種類の値を取る場合、時間計算量は \( O \left( D \left( N + K \right) \right) \) です。

終わりに

以上有名なソートアルゴリズムをいくつか紹介しましたが、いかがでしたでしょうか。実際にソートをしてみたい人は、トランプを適当な枚数取って自分で並び替えてみると良いでしょう。ちなみに個人的に好きなソートは基数ソートです。ここで紹介したソートアルゴリズムを筆者がC++で実装をしたので、下にそのソースコードを添えておきたいと思います。もし不備や間違いなどが合った場合は GitHubのissueに投げるなどしてください。