ソートアルゴリズム

「ソートアルゴリズム」とは

ソート（sort）とは、複数のデータを、決められた基準に従って一定の順序に並べ替えることである。
数値を小さい順に並べる昇順、大きい順に並べる降順のほか、文字列を文字コード順に並べることなどもソートに含まれる。この並べ替えを実現する具体的な手順をソートアルゴリズム（整列アルゴリズム）という。

例えば、

[2, 4, 1, 3]

を昇順にすると、

[1, 2, 3, 4]

となる。同じ結果を得る場合でも、どの要素をどの順番で比較し、どのように移動させるかによって、さまざまなソートアルゴリズムがある。

バブルソート

代表的な方法の一つがバブルソートである。隣り合う二つの要素を比較し、並べたい順序と逆になっていれば交換する。この比較・交換を端まで繰り返す。

例えば、[2, 4, 1, 3]を昇順にするため左から比較すると、

• 2と4：そのまま

• 4と1：交換 → [2, 1, 4, 3]

• 4と3：交換 → [2, 1, 3, 4]

となり、1回の走査によって大きな値である4が末尾まで移動する。
最大値である4が末尾に移動する。
[2, 1, 3, 4] の [2, 1, 3] の部分について、さらに同じ処理を未整列の部分に繰り返すと、

• 2と1：交換→ [1, 2, 3, 4]

• 2と3：そのまま

となり、[1, 2, 3, 4] となる。

このように、「隣り合う要素を比較し、逆なら交換する」のがバブルソートの重要な特徴である。

要素数をNとし、途中で整列済みかどうかを判定せず、毎回すべての比較を行う基本的なバブルソートでは、比較回数は

(N−1) + (N−2) + … + 1

となる。これは1からN−1までの和なので、

N(N−1) / 2

回である。そのため、要素数が増えると比較回数はおおよそN²に比例して増える。

選択ソート

もう一つの代表例が選択ソートである。選択ソートでは、未整列の部分から最小値を探し、それを未整列部分の先頭に移す操作を繰り返す。

例えば、

[3, 5, 1, 2, 4]

を昇順にすると、

1. 全体から最小値1を選ぶ → [1, 5, 3, 2, 4]

2. 残りから最小値2を選ぶ → [1, 2, 3, 5, 4]

3. 残りから最小値3を選ぶ → [1, 2, 3, 5, 4]

となる。

複数の条件によるソート

表形式のデータでは、複数の項目を使って並べ替えることもある。
このとき、最も優先する項目を第1キー、その値が同じ場合に使う項目を第2キーなどという。

例えば、得点表を

1. 得点の高い順

2. 得点が同じなら氏名の文字コード順

に並べたい場合、

• 第1キー：得点の降順

• 第2キー：氏名の昇順

と指定する。

第2キーは、第1キーの値が同じデータ同士の順番を決めるために使われる。