関連youtube
ソートとはデータ列を大きさの順に並べ替えることをいいます。ここでは、小さいものから大きいものへ
並べるとします。バラバラであったデータ列がきれいに並ぶことで、そのデータ列の処理が非常に効率的になってきます。
ソート方法はいくつも工夫されてきました。それらの中でよく使われ、かつ、アルゴリズムが面白いものを
６つとりあげます。
（1） 選択法 （2）シェルソート （3）ヒープソート （4）クイックソート （5）マージソート
（6） ２ウエイマージソート
説明内容：
ソート手順：アルゴリズム
特徴および効率
使用するデータはランダムに発生させたものです。
それでは、個々の方法について概要を説明します。データ数は、nとします。
1. 選択法 全体の中から一番小さいデータを見つける。それを一番前に移動。
残ったものから同じことを繰り返す。
この方法は全体を探して1個しか処理しないので効率は悪く、O(n2)でnの増加とともに急に時間が
かかるようになります。
2. シェルソート法 位置的に離れたデータどうしを部分的に並べ、その離れを次第に小さくして終には全
体をソートする方法です。ソートに至る過程は、自然的な拡散の逆のプロセスであるかのような様
子が特徴です。
効率は実用的で速く、n1.2に近いものです。
3. ヒープソート データを整列2分木に組み立てます。これは2分木の一種で、親はこのいずれよりも大き
いという緩い制約の２分木です。整列２分木のトップは最大のデータなので、この最大のデータを一
番大きいデータとして確定しこれを除きます。そして残りで整列２分木を再構築しまた最大を見つけ
ます。この手順を繰り返して並べていく方法です。
手順の形は再帰構造になっています。効率は初期データの性質によらずO(nlog(n))と安定していま
す。
4. クイックソート データの中からあるデータpを適切に選び、それを区切りとして、全体をぴょり小さいも
のと大きいものの2つのグループに分けます。そして、この双方のグループに対し同じことを繰り返
します。この手順を繰り返して並べていく方法です。
手順の形式は、再帰構造になっています。効率は、データがランダムであれば一番効率が良いが
データが最初から構造を持つ場合効率が落ちます。O(nlog(n))
5. マージソート データを2つのグループに分け、両方をソートしてマージする手順です。実際の手順の
進行は再帰的に行われるので、一番端の２つのデータの並べ替えから徐々に中央に進んでいくよ
うに見えます。O(nlog(n))
6. ２ウエイマージソート マージソートとほぼ同じですが、最初２分したブロックの右と左で途中のデータ
の並べ方を変えます。左は昇順、右は降順です。マージは左右のデータを使います。
内容(contents)に戻る