整列のアルゴリズム

0. どういうまとまりか

データを大きさの順に並べ替えるのが整列（ソート）です。小さい順を昇順、大きい順を降順といいます。
どのやり方も「比べる」と「動かす（交換する）」の組み合わせで、何を選んでどこへ動かすかが違います。

分かれ目は次の 3 つ。

• 選択ソートは「最小値を選んで先頭へ」、バブルソートは「隣どうしを比べて交換」。
• 選択・バブル・挿入の比較の回数は、n の 2 乗に比例して増える。
• 同じ値どうしの並び順が、整列の前後で変わらないものを安定なソートという。

1. 選択ソート

根拠: 学習指導要領 情報Ⅰ-(3)-ア-(イ)

選択ソートは、まだ整列していない部分から最小値を探し、その部分の先頭と入れ替えます。
1 回ごとに先頭から 1 つずつ確定していきます。

2. バブルソート

根拠: 学習指導要領 情報Ⅰ-(3)-ア-(イ)

バブルソート（交換ソート）は、隣り合う 2 つを比べ、順が逆なら交換する、を端から端まで繰り返します。
1 回通すごとに、いちばん大きい値が末尾へ移ります（泡が浮かぶように動くのが名前の由来）。

3. 挿入ソートとクイックソート

根拠: 学習指導要領 情報Ⅰ-(3)-ア-(イ)

挿入ソートは、手持ちのトランプを並べるときのように、1 枚ずつ正しい位置に差し込むやり方です。
クイックソートは、基準値で「小さいグループ」と「大きいグループ」に分け、それぞれを同じ方法で整列します。

4. 比較の回数と安定なソート

根拠: 学習指導要領 情報Ⅰ-(3)-ア-(イ)

選択ソートでは、1 回目に n−1 回、2 回目に n−2 回……と比べるので、比較は全部で
$(n-1)+(n-2)+\cdots +1$ 回、すなわち $\frac{n(n-1)}{2}$ 回になります。

練習問題

a = [5, 3, 8, 1]
swaps = 0
for i in range(len(a) - 1):
    for j in range(len(a) - 1 - i):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
            swaps = swaps + 1
print(a, swaps)

a = [29, 10, 14, 37, 13]
for i in range(len(a) - 1):
    m = i
    for j in range(i + 1, len(a)):
        if a[j] < a[m]:
            m = j
    a[i], a[m] = a[m], a[i]

a = [7, 3, 5, 2]
for i in range(1, len(a)):
    x = a[i]
    j = i - 1
    while j >= 0 and a[j] > x:
        a[j + 1] = a[j]
        j = j - 1
    a[j + 1] = x