バブルソート・選択ソート・挿入ソート
同じ配列を三つの方法で整列し、各段階で確定する部分と移動回数を学びます。
説明
整列は、値を大小などの規則に従って並べ直す処理です。バブルソートは隣同士を交換し、選択ソートは残りから最小値を選び、挿入ソートは整列済みの部分へ次の値を差し込みます。最終的な昇順が同じでも、途中の配列と必要な移動が違います。
4・2・3・1を三方式で処理します。各回の配列を残し、バブルソートでは右端、選択ソートでは左端、挿入ソートでは整列済みの先頭部分に注目します。回数はこの実装での比較・交換・右移動として数えます。
1隣り合う逆順を交換
最初に4と2、続いて4と3、4と1を交換します。左から右へ一巡すると最大値4が末尾へ到達します。
original = [4, 2, 3, 1]; a = original.copy()元の配列を保持; a[0], a[1] = a[1], a[0]; print(a)4と2; a[1], a[2] = a[2], a[1]; print(a)4と3; a[2], a[3] = a[3], a[2]; print(a)4と1最大値4が右端に確定しました。左側の2・3・1はまだ昇順ではありません。一巡で全体が整列するとは限らず、次は右端4を除いた範囲で続けます。
2バブルソートの残り
残り3要素では2と3は交換不要、3と1を交換します。次の一巡で2と1を交換すると整列が終わります。
a[1], a[2] = a[2], a[1]; print(a)3を右端手前へ; a[0], a[1] = a[1], a[0]; print(a)残る2要素を交換; comparisons = 3+2+1; swaps = 3+1+1比較と交換を集計; comparisons, swaps集計結果この配列では比較6回、交換5回です。要素数4の場合、固定した巡回範囲は3・2・1となります。既に整列済みでも同じ範囲を回す実装と、交換がなければ終了する実装では回数が変わります。
3残り全体から最小値を選ぶ
選択ソートを同じ初期配列で始めます。最小値1の位置を探し、先頭4と交換します。
b = original.copy()同じ初期配列; minimum = min(range(len(b)), key=b.__getitem__)最小値の添字; b[0], b[minimum] = b[minimum], b[0]先頭へ移す; minimum, b位置と交換後最小値は添字3で、交換後は1・2・3・4です。この入力では一度の交換で全体も整列しましたが、選択ソートの規則として確定したのは先頭1です。
4選択範囲を縮める
残りの最小値の位置を求めます。2と3は既に正しい場所なので、この例では追加の交換が要りません。
[(i, min(range(i, len(b)), key=b.__getitem__)) for i in [1, 2]]未確定部分の最小位置, 3+2+1最小値を選ぶ比較回数結果の(i, 最小位置)は(1,1)、(2,2)です。最小値を探す比較は最初3回、次2回、最後1回の計6回です。比較回数が同じでも、バブルソートの5交換に対して実際の交換は1回でした。
5整列済み部分へ2を挿入
挿入ソートを始めます。先頭4だけは整列済みとみなし、次の2を保存します。4を右へ移し、空いた位置へ2を置きます。
c = original.copy()同じ初期配列; value = c[1]挿入する2を退避; c[1] = c[0]4を右へ移動; c[0] = value2を挿入; c先頭2個が整列済み先頭2個が2・4となりました。残り3・1はまだ対象外です。値を一時保存することで、右への移動中に挿入したい値を失わずに済みます。
63の入る場所を空ける
次の3より大きい4だけを右へ移します。2は3以下なので、それ以上左へ進む必要はありません。
value = c[2]3を退避; c[2] = c[1]4を右へ移動; c[1] = value2の後ろへ3を挿入; c先頭3個が整列済み先頭3個が2・3・4になりました。挿入ソートでは、処理済みの先頭部分が常に整列済みです。右端に最大値を確定させるバブルソートとは進み方が異なります。
71のために3個を移動
最後の1は先頭へ入ります。4・3・2を後ろから順にずらし、1を入れます。
value = c[3]1を退避; c[3] = c[2]; c[2] = c[1]; c[1] = c[0]3個を後ろから移動; c[0] = value先頭へ1を挿入; c, 1+1+3結果と右移動数配列は1・2・3・4です。右へ移した要素は合計5個でした。交換1回と右移動1回では書き込みの内容が違うため、回数だけを同じ単位の費用として比較しないようにします。
8結果と保存した入力
三方式の結果が同じ昇順か、元の配列も保持されているかを調べます。途中配列は上の履歴に残っています。
a == b == c == sorted(original)三方式の結果を照合, original, a入力と整列後全て一致し、originalは4・2・3・1のままです。この小例は各方式の作業を比較するためのものです。一般に三方式とも二乗の回数になる入力があり、大きなデータでは別方式も検討します。
まとめ
バブルソートは隣同士の交換で右端を、選択ソートは最小値選択で左端を確定します。
挿入ソートは整列済みの先頭部分へ次の値を入れ、大きい値を右へ移します。
比較・交換・移動は別の操作です。同じ入力と数え方をそろえて途中経過を比較します。
操作履歴と解説を振り返れます。
Python 3
original = [4, 2, 3, 1]; a = original.copy(); a[0], a[1] = a[1], a[0]; print(a); a[1], a[2] = a[2], a[1]; print(a); a[2], a[3] = a[3], a[2]; print(a)[2, 4, 3, 1] [2, 3, 4, 1] [2, 3, 1, 4]
a[1], a[2] = a[2], a[1]; print(a); a[0], a[1] = a[1], a[0]; print(a); comparisons = 3+2+1; swaps = 3+1+1; comparisons, swaps[2, 1, 3, 4] [1, 2, 3, 4] (6, 5)
b = original.copy(); minimum = min(range(len(b)), key=b.__getitem__); b[0], b[minimum] = b[minimum], b[0]; minimum, b(3, [1, 2, 3, 4])
[(i, min(range(i, len(b)), key=b.__getitem__)) for i in [1, 2]], 3+2+1([(1, 1), (2, 2)], 6)
c = original.copy(); value = c[1]; c[1] = c[0]; c[0] = value; c[2, 4, 3, 1]
value = c[2]; c[2] = c[1]; c[1] = value; c[2, 3, 4, 1]
value = c[3]; c[3] = c[2]; c[2] = c[1]; c[1] = c[0]; c[0] = value; c, 1+1+3([1, 2, 3, 4], 5)
a == b == c == sorted(original), original, a(True, [4, 2, 3, 1], [1, 2, 3, 4])
演習完了