はじめに
今回は基本情報技術者試験で出題されるソート (データの並び替え) について解説します！
【YouTube動画】 よくわかる基本情報技術者試験。ソート (並び替え) について解説！
バブルソート O(n^2)
まずは、遅いソートであるバブルソート、選択ソート、挿入ソートについて解説します。
バブルソートは先頭から2つずつ数値を比較して並び替える方法です。
例えば以下の数値があり、昇順に並び替えるとします。
6 8 4 2
先頭から比較し、小さい数を左に移します。
数値を入れ替えた回数は3回です。
(6 8) 4 2
-> 6 8 4 2
6 (8 4) 2
-> 6 4 8 2
6 4 (8 2)
-> 6 4 2 8
もう一度先頭から比較します。
数値を入れ替えた回数は2回です。
(6 4) 2 8
-> 4 6 2 8
4 (6 2) 8
-> 4 2 6 8
4 2 (6 8)
-> 4 2 6 8
最後にもう一度比較します。
数値は1回だけ入れ替えました。
(4 2) 6 8
-> 2 4 6 8
2 (4 6) 8
-> 2 4 6 8
2 4 (6 8)
-> 2 4 6 8
足し合わせていくと、入れ替えた回数は3 + 2 + 1 = 6になります。
(厳密な部分は省いて...) 一般化すると、(n-1) + (n-2) + (n-3) + ・・・ + 2 + 1ですね。
これを計算すると、
\sum_{k=1}^{n} (k-1) = \frac{n(n+1)}{2} - n = \frac{1}{2} n^2(1-\frac{1}{n}) \\
です。
nが大きくなると、1/nはゼロに近づくので、オーダーはn^2に比例して大きくなります。
選択ソート O(n^2)
選択ソートは一番小さい数値を見つけて、先頭に移動する方法です。
未整列の一番左の数値と未整列の一番小さな数値を入れ替えていきます。
6 8 4 2
未整列の一番左の数値を最小値に設定します。
min = 6
未整列の数値を比較して、最小値を決めていきます。
最小値が決まったら、最初に設定した最小値と入れ替えます。
min 6 | (6 < 8) 4 2
min 4 | 8 (6 > 4) 2
min 2 | 8 4 (4>2)
-> 2 8 4 6
同じ操作を繰り返します。
2は整列してるので、一番左の8を最初うちに設定します。
min = 8
先ほどと同じように、最小値が決まったら、最初に設定した最小値と入れ替えます。
min 8 | 2 (8 > 4) 6
min 4 | 2 4 (4 < 6)
-> 2 4 6 8
繰り返します。
min = 6
昇順に並び替えました。
min 6 | 2 4 (6 < 8)
-> 2 4 6 8
最小値を決める操作を4, 3, 2と繰り返したので、
4 + 3 + 2 = 9となります。
一般化すると、
\sum_{k=1}^{n} k-1 = \frac{n(n+1)}{2} - 1 = \frac{1}{2} n^2(1+\frac{1}{n}-\frac{2}{n^2}) \\
となり、nが大きくなるとオーダー n^2になります。
*数値を比較する回数で比べると、バブルソートと同じです。
ただ、nが大きくなると、どちらにせよ オーダー n^2になります。
挿入ソート O(n^2)
挿入ソートは未整列のデータを整列したデータに入れていく方法です。
一番左は整列しているとみなします。
8と6を比較して、8を整列させます。
(整列) 6 | (未整列) 8 4 2
6 < 8
(整列) 6 8 | (未整列) 4 2
次は4を比較します。
(整列) 6 8 | (未整列) 4 2
4 < 8
4 < 6
(整列) 4 6 8 | (未整列) 2
最後に2を比較します。
(整列) 4 6 8 | (未整列) 2
2 < 8
2 < 6
2 < 4
-> 2 4 6 8
整列するときに比較した回数は、1, 2, 3なので、
1 + 2 + 3 = 6です。
一般化すると、
\sum_{k=1}^{n-1} k = \frac{n(n-1)}{2} = \frac{1}{2} n^2(1-\frac{1}{n}) \\
となり、nが大きくなるとn^2で大きくなります。
シェルソート O(n^1.2)
挿入ソートはある程度整列していると、並び替えが早く終わります。
それを利用したのがシェルソートです。
シェルソートは、比較する要素の幅を小さくしていき、最後に挿入ソートをする方法です。
要素が4個しかないので、1個飛ばしで比較します。
6 8 4 2
6 4 | 8 2
6 > 4 | 8 > 2
4 6 | 2 8
元の位置に戻します。
これを挿入ソートします。
4 2 6 8
1度比較するだけで、並び替えができるので早いですね。
(整列) 4 | (未整列) 2 6 8
2 < 4 なので、
(整列) 2 4 | (未整列) 6 8
4 < 6 なので、
(整列) 2 4 6 | (未整列) 8
6 < 8 なので
2 4 6 8
シェルソートは1度比較する必要があるので、オーダーn^1以上なことは分かりますね。
しかし、具体的なオーダーについては、未解決でよくわかっていません。
経験的に、n^1.2ぐらいになるかなぁといった感じです。
もし解けたら教えてくださいね！
クイックソート O(nlogn)
クイックソートは基準値を決めて、大きいか小さいかで分けていく方法です。
6 8 4 2
基準値は一番左で、8, 4, 2をそれぞれ基準値と比較させます。
6 < 8
6 > 4
6 > 2
大きかったら右、小さかったら左に配置します。
4 2 6 8
4, 2に対してもう一度並び替えます。
2 < 4
まとめると、次のようになります。
2 4 6 8
全ての数値に対して1度ずつ比較しつつ、二分木のように要素を分けていくので、
オーダーはnlognになります。
二分木だと、どうしてlognになるのか... といった話は以下で確認してみてください。
【Qiita記事】データの探し方 探索アルゴリズム 基本情報技術者 用語解説 二分探索方
ヒープソート O(nlogn)
ヒープソートは木を作っていきながら、ソートする方法です。
ヒープソートを文章で表現するのは難しいので、ぜひ動画をご確認ください！
【YouTube】よくわかる基本情報技術者試験。ソート (並び替え) について解説！
まとめ
今回ソートについて解説しました！
基本情報技術者試験や応用情報技術者試験で解説して欲しいところなどあれば、コメントお願いします！！
今回の記事・動画で少しでもソートについて詳しくなっていただければと思います。
他にも
について解説しているので、興味のある方はご確認ください！