Sort

様々なソートプログラムについて、ソートの手順が分かり易いように可視化しました。
推奨ブラウザは、PCでは Firefox と Google Chrome です。 IEでは (たぶん) 動きません。
スマートフォンにも対応しています。iPhoneの Safari で動作を確認しています。

バブルソートは (まともなソートの中では) 最も簡単な安定ソートのアルゴリズムです。
データの先頭から順に、そのデータと1つ先のデータとを比較し、 もし自分の方が大きければ2つのデータを入れ替えます。 それをデータの終端 正確にはデータの終端の1つ手前。 まで繰り返すことを何度も繰り返してソートするのがバブルソートです。

一度データの終端まで走査し終われば、最後のデータは必ず最大値になります。 つまり、一番最後のデータはソート済となるので、 ソートすべきデータが1つ減る事になります。 これを使って効率を上げたものもバブルソートと呼ばれます。 以下のページのバブルソートは、 この効率を上げたバブルソートのアルゴリズムを採用しています。

バブルソートのデモページへ
スペースキーを押すか、データの領域をクリックするとソートが始まります。 端まで走査すると一時停止し、スペースキーかクリックで再びソートが始まります。

カクテルソートは、 バブルソートを改良して効率を上げた安定ソートのアルゴリズムです。 シェーカーソートとも呼ばれます。
バブルソートでは、一方向にデータの走査を行っていましたが、 これを双方向にすることで、若干の効率化を図っています。

カクテルソートのデモページへ
スペースキーを押すか、データの領域をクリックするとソートが始まります。 1往復の走査をすると一時停止し、スペースキーかクリックで再びソートが始まります。

コムソートは、バブルソートを改良した非安定ソートのアルゴリズムです。
2つのデータを比較し、必要なら交換するところはバブルソートと同じですが、 バブルソートでは隣り合った2つのデータを比較・交換したのに対し、 コムソートでは適当な間隔のデータを比較・交換します。 この間隔ははじめはデータ数を 1.3 で割ったもの (小数点切り捨て) で、 繰り返す毎にさらに 1.3 で割っていきます。 間隔はそのうち1になるので、最後の方はバブルソートと同じ動きになります。

コムソートのデモページへ
スペースキーを押すか、データの領域をクリックするとソートが始まります。 1往復の走査をすると一時停止し、スペースキーかクリックで再びソートが始まります。

ノームソートは、バブルソートと似た安定ソートのアルゴリズムです。
2つのデータを比較し、必要なら交換するところはバブルソートと同じですが、 始めは先頭の2つの要素のみをソートし、次に先頭の3つの要素をソートし、 という具合にソートする領域を徐々に広げていきます。 また、走査する方向がバブルソートとは逆で、 ソート領域の最後から先頭に向かって走査して行きます。 バブルソートは先頭要素からデータ末端のソート済要素の手前まで 順に入れ替えを行うため、 i回目の走査範囲が「0 から N-(i+1)」 番目のデータとなるのに対し、 ノームソートではi回目の走査範囲が「i+1 から 1」 番目のデータになります。

ノームソートのデモページへ
スペースキーを押すか、データの領域をクリックするとソートが始まります。 1往復の走査をすると一時停止し、スペースキーかクリックで再びソートが始まります。

選択ソートは、 最大値を探索してそれを配列最後の要素と入れ替える、 簡単な非安定ソートのアルゴリズムです。
一番大きなものを見付けて右から詰めていく、という普通のソートです。

選択ソートのデモページへ
スペースキーを押すか、データの領域をクリックするとソートが始まります。 1つ入れ替える毎に一時停止し、スペースキーかクリックで再びソートが始まります。

挿入ソートは、 整列済のデータ列に適切に新データを挿入していくようにソートを行う、 安定ソートのアルゴリズムです。
始めに1番目と2番目のデータを調べ、順番が逆なら入れ替えます。 その後、3番目のデータを2番目までのデータの中の適切な箇所に挿入します。 これを1サイクルとして、 1つずつ走査する箇所をずらして行くことでソートを行います。

挿入ソートのデモページへ
スペースキーを押すか、データの領域をクリックするとソートが始まります。 1往復の走査をすると一時停止し、スペースキーかクリックで再びソートが始まります。

クイックソートは、一般的に最速 データの並びや数によってはあまり速くないこともあります。 な非安定ソートのアルゴリズムです。
適当に選ばれたデータをピボットとし、 データの先頭から順にそれより大きなデータを、 終端から順にそれより小さなデータを探します。 その両方が見つかった時点で、2つのデータを入れ替え、 再び同じピボットより大きなデータと小さなデータを探します。 先頭からの走査で見つかったデータが、 終端からの走査で見つかったデータより後ろにある場合に走査を中断し、 ピボットの選択から再び繰り返していくことで、ソートを行います。

クイックソートのデモページへ
スペースキーを押すか、データを選択することでソートが始まります。 データを選択した場合はそれをピボットに、 スペースキーを押した場合は最左の未ソートのデータをピボットにし、 ソートします。そのピボットに対するソートが終わると一時停止し、 再びスペースキーかクリックでピボットを選択することでソートを再開します。

ソート前とソート後で、 同じ値の順序が維持されるソートを安定ソートと言います。
例えば、[4, 1, 1, 2, 3] というデータをソートすると [1, 1, 2, 3, 4] になりますが、このとき元のデータの2つの 1 の順番が、 ソート後も同じであれば安定ソート、そうでなければ非安定ソートです。
バブルソートやカクテルソートは安定ソートで、 コムソートやクイックソートは非安定ソートです。

このページのQRコードです。 スマートフォンでアクセスするのにお使いください。