【超基本】初心者に贈るアルゴリズム論 ～ソート・前編～
スポンサーリンク
はじめに
こんにちは。talosです。
今回はソートのアルゴリズムを説明します。
前編では「バブルソート」、「セレクションソート」、「インサーションソート」、「シェルソート」を、後編では「ヒープソート」、「クイックソート」、「マージソート」を説明します。
後編はこちら
talosta.hatenablog.com
バブルソート
バブルソートは、隣り合う要素の大小が逆順なら交換するということを繰り返す方法です。
※ オレンジの箇所はソート済み
ソートするときに要素が泡のように昇っていくことから、バブルソートと名付けられました。
ソートのアルゴリズムとしてはもっとも効率が悪い方法で、データの比較回数はO(n^2)です。
実装例を下に示します。
def bubble_sort(array): for k in range(len(array) - 1): for i in range(0, len(array) - k - 1): # 隣り合う要素の大小が逆順なら if array[i] > array[i + 1]: # 交換 array[i], array[i + 1] = array[i + 1], array[i] print(array) # ソート対象のリスト array = [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3] print(array) bubble_sort(array) print('\n--result--') print(array)
出力
[10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3] [10, 43, 54, 69, 11, 9, 23, 29, 6, 88, 19, 92, 3, 94] [10, 43, 54, 11, 9, 23, 29, 6, 69, 19, 88, 3, 92, 94] [10, 43, 11, 9, 23, 29, 6, 54, 19, 69, 3, 88, 92, 94] [10, 11, 9, 23, 29, 6, 43, 19, 54, 3, 69, 88, 92, 94] [10, 9, 11, 23, 6, 29, 19, 43, 3, 54, 69, 88, 92, 94] [9, 10, 11, 6, 23, 19, 29, 3, 43, 54, 69, 88, 92, 94] [9, 10, 6, 11, 19, 23, 3, 29, 43, 54, 69, 88, 92, 94] [9, 6, 10, 11, 19, 3, 23, 29, 43, 54, 69, 88, 92, 94] [6, 9, 10, 11, 3, 19, 23, 29, 43, 54, 69, 88, 92, 94] [6, 9, 10, 3, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94] [6, 9, 3, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94] [6, 3, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94] [3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94] --result-- [3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94]
1回目の走査で最大値が配列の末尾に移動、2回目の走査で2番目に大きい要素が末尾から2番目に移動します。
したがって、1回走査するたびに末尾から大きい値が埋まっていくので、2つ目のfor文は範囲がどんどん狭まっています。
セレクションソート
セレクションソートは、列の中の最大要素を探し、右端の要素と交換することを繰り返す方法です。
※ オレンジの箇所はソート済み
データの比較回数はバブルソートと同じO(n^2)ですが、データを交換する回数は1回の走査につき1回なので、基本的にはバブルソートよりも短い時間で終わります。
実装例を下に示します。
def selection_sort(array): for k in reversed(range(len(array))): # 最大値を取り出し max_index = array.index(max(array[0:k+1])) # 右端の要素と交換 array[max_index], array[k] = array[k], array[max_index] print(array) # ソート対象のリスト array = [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3] print(array) selection_sort(array) print('\n--result--') print(array)
出力
[10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3] [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 3, 94] [10, 43, 54, 3, 69, 11, 9, 23, 29, 6, 88, 19, 92, 94] [10, 43, 54, 3, 69, 11, 9, 23, 29, 6, 19, 88, 92, 94] [10, 43, 54, 3, 19, 11, 9, 23, 29, 6, 69, 88, 92, 94] [10, 43, 6, 3, 19, 11, 9, 23, 29, 54, 69, 88, 92, 94] [10, 29, 6, 3, 19, 11, 9, 23, 43, 54, 69, 88, 92, 94] [10, 23, 6, 3, 19, 11, 9, 29, 43, 54, 69, 88, 92, 94] [10, 9, 6, 3, 19, 11, 23, 29, 43, 54, 69, 88, 92, 94] [10, 9, 6, 3, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94] [10, 9, 6, 3, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94] [3, 9, 6, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94] [3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94] [3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94] [3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94] --result-- [3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94]
インサーションソート
インサーションソートは、ソート済みの列に1つずつデータを挿入していく方法です。
※ オレンジの箇所はソート済み
逆順にソートされた配列をソートする場合、比較回数とデータを移動する回数はともにO(n^2)です。
逆に、だいたいソートされた配列をソートする場合、比較回数とデータ移動回数はともにほぼO(n)になります。
実装例を下に示します。
def insertion_sort(array): for i in range(1, len(array)): x = array[i] j = i # ソート済みの列を右から走査 while j > 0 and array[j - 1] > x: array[j] = array[j - 1] j -= 1 array[j] = x print(array) # ソート対象のリスト array = [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3] print(array) insertion_sort(array) print('\n--result--') print(array)
出力
[10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3] [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3] [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3] [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3] [10, 43, 54, 69, 92, 11, 9, 23, 29, 6, 88, 19, 94, 3] [10, 11, 43, 54, 69, 92, 9, 23, 29, 6, 88, 19, 94, 3] [9, 10, 11, 43, 54, 69, 92, 23, 29, 6, 88, 19, 94, 3] [9, 10, 11, 23, 43, 54, 69, 92, 29, 6, 88, 19, 94, 3] [9, 10, 11, 23, 29, 43, 54, 69, 92, 6, 88, 19, 94, 3] [6, 9, 10, 11, 23, 29, 43, 54, 69, 92, 88, 19, 94, 3] [6, 9, 10, 11, 23, 29, 43, 54, 69, 88, 92, 19, 94, 3] [6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94, 3] [6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94, 3] [3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94] --result-- [3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94]
シェルソート
シェルソートは数個離れた場所にあるデータと比較してデータを交換し、徐々に間隔を狭めていく方法です。
シェルソートのオーダーを正確に求めるのは難しいようですが、Wikipediaによると
最悪計算時間：O(nlog^2n)
最良計算時間：O(n)
平均計算時間：O(n^1.25)
だそうです。
実装例を下に示します。
def shell_sort(array): # 間隔を徐々に狭めていく gap = int(len(array) / 2) while gap > 0: print('\ngap=' + str(gap)) for i in range(gap, len(array)): j = i - gap # gap個離れた要素と比較 while j >= 0 and array[j] > array[j + gap]: array[j], array[j + gap] = array[j + gap], array[j] j -= gap print(array) gap = int(gap / 2) # ソート対象のリスト array = [10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3] print(array) shell_sort(array) print('\n--result--') print(array)
出力
[10, 43, 54, 92, 69, 11, 9, 23, 29, 6, 88, 19, 94, 3] gap=7 [10, 29, 6, 88, 19, 11, 3, 23, 43, 54, 92, 69, 94, 9] gap=3 [3, 9, 6, 10, 19, 11, 54, 23, 43, 88, 29, 69, 94, 92] gap=1 [3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94] --result-- [3, 6, 9, 10, 11, 19, 23, 29, 43, 54, 69, 88, 92, 94]
参考
