【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら
6‐3 単純選択ソート
最小要素を先頭に移動し、2番目に小さい要素を先頭から2番目に移動するといった作業を繰り返すアルゴリズムです。
交換の手順は次の通りです。
- 未ソート部から最小のキーをもつ要素a[min]を選択する。
- a[min]と未ソート部の先頭要素を交換する。
def selection_sort(a: MutableSequence) -> None:
"""単純選択ソート"""
n = len(a)
for i in range(n - 1):
min = i #未ソート部の最小要素の添字
for j in range(i + 1, n):
if a[j] < a[min]:
min = j
a[j], a[min] = a[min], a[i] #未ソート部の先頭要素と最小要素を交換
要素の値を比較する回数は(n ** 2 - 2) / 2です。
このソートアルゴリズムは離れた要素を交換するため、安定ではありません。
6-4単純挿入ソート
着目要素をそれより先頭側の適切な位置に挿入する作業を繰り返してソートを行うアルゴリズムです。
パスの終了条件は、
1.目的列の左端に達した。
2.tmpと等しいか小さいキーをもった左端の要素a[j - 1]が見つかった。
継続条件は
1.jが0より大きい
2.a[j - 1]の値がtmpより大きい
です。
# 単純挿入ソート
from typing import MutableSequence
def insertion_sort(a: MutableSequence) -> None:
"""単純ソート"""
n = len(a)
for i in range(1, n):
j = 1
tmp = a[j]
while j > 0 and a[j - 1] > tmp:
a[j] = a[j - 1]
j -= 1
a[j] = tmp
if __name__ == '__main__':
print('単純挿入ソート')
num = int(input())
x = [None] * num #要素数numの配列を生成
for i in range(num):
x[i] = int(input(f'x[{i}]：'))
insertion_sort(x) #配列xを単純挿入ソート
print('昇順にソートしました。')
for i in range(num):
print(f'x[{i}] = {x[i]}')
このソートアルゴリズムは安定です。比較回数と交換回数はn**2/2です。
単純ソートの時間計算量
ここまで学習してきた三つの単純ソートの時間計算量はいずれもO(n**2)で非常に効率が悪いです。
| コラム6-2 2分挿入ソート |
|---|
単純挿入ソートは、配列の要素が多くなると要素の挿入に要する比較・代入のコストが大きくなってしまいます。
目的列はソート済みなため、2分探索法によって調べられます。
#2分挿入ソート
from typing import MutableSequence
def binary_insertion_sort(a: MutableSequence) -> None:
"""2分挿入ソート"""
n = len(a)
for i in range(1, n):
key = a[i]
pl = 0 #探索範囲の先頭要素の添字
pr = i - 1 #探索範囲の末尾要素の添字
while True:
pc = (pl + pr) // 2 #探索範囲の中央要素の添字
if a[pc] == key:
break
elif a[pc] < key:
pl = pc + 1
else:
pr = pc - 1
if pl > pr:
break
#挿入すべき位置の添字
pd = pc + 1 if pl <= pr else pr + 1
for j in range(i, pd, -1):
a[j] = a[j - 1]
a[pd] = key
if __name__ == '__main__':
print('2分ソート')
num = int(input('要素数：'))
x = [None] * num #要素numの配列を生成
for i in range(num):
x[i] = int(input(f'x[{i}]：'))
binary_insertion_sort(x) #配列xを2分挿入ソート
print('昇順にソートしました。')
for i in range(num):
print(f'x[{i}]={x[i]}')
適切な位置への挿入アルゴリズムはpythonの標準ライブラリで提供されており、bisectモジュールのinsort関数で、ソートされた配列に並びを崩すことなく要素が挿入可能です。
def binary_insertion_sort(a: MutableSequence) -> None:
"""2分挿入ソート(bisect.insortを利用)"""
for i in range(1, len(a)):
bisect.insort(a, a.pop(i), 0 ,1)
`bisect.insort(a, x, lo ,hi)`と呼び出すとaがソートされた状態を保ったままa[lo]からa[hi]の間にxが挿入されます。(もしaの中にxと同じ要素が複数含まれていれば、最も右側の位置に挿入されます)
6-5 シェルソート
とある例において、単純ソートは
・ソート済み、あるいはそれに近い状態では高速である(長所)
・挿入先が遠く離れている場合は、移動(代入)回数が多くなる(短所)
という特徴があります。
シェルソート
先ほどの長所を活かしながら、短所を補うのが、シェルソートという優れたアルゴリズムです。
まず最初に離れた要素をグループ化して大まかなソートを行い、そのグループを縮小しながらソートを繰り返すことによって移動回数を減らそうというアイデアです。
[8, 1, 4, 2, 7, 6, 3, 5]があったとしたら、4個離れた要素(4-ソートと呼ぶ)
{8,7}{1,6}{4,3}{2,5}に分けて、それぞれをソートすると
[7, 1, 3, 2, 8, 6, 4, 5]となります。
続いて、2-ソートを行うと
{7, 3, 8, 4}{1, 2, 6, 5}が
[3, 1, 4, 2, 7, 5, 8, 6]となります。
最後に、1-ソートをしてソートを完了します。
シェルソートの過程における個々のソートをh-ソートと呼びます。
先の例だと
4-ソートを4グループ行う→2-ソートを2グループ行う→1-ソート(計7回)
となります。
# シェルソート
from typing import MutableSequence
def shell_sort(a: MutableSequence) -> None:
"""シェルソート"""
n = len(a)
h = n // 2
while h > 0:
for i in range(h, n):
j = i - h
tmp = a[i]
while j >= 0 and a[j] > tmp:
a[j + h] = a[j]
j -= h
a[j + h] = tmp
h //= 2
if __name__ == '__main__':
print('シェルソート')
num = int(input('要素数：'))
x = [None] * num #要素数numの配列を生成
for i in range(num):
x[i] =int(input(f'x[{i}]：'))
shell_sort(x) #配列xをシェルソート
print('昇順にソートしました。')
for i in range(num):
print(f'x[{i}]={x[i]}')
増分の選択
先ほどの例では、要素数nが8のときに、hの値を次のように変化させました。
h = 4 → 2 → 1
増分hはある値から減少していって最後に1となればよい性質のものですが、どのような数列が適当か考えます。
先ほどの場合は、4-ソートを4グループにしたもののうち、偶数グループと奇数グループで分かれており、偶数グループと奇数グループには交流がないため、せっかくのグループ分けが十分に機能しないことを示唆しています。
hの値が互いに倍数とならないようにすれば、要素が十分にかき混ぜられて、効率の良いソートの実行が期待できます。
単純に作り出せて、しかも良い結果が得られるのが、
h = ・・・→ 121 → 40 → 13 → 4 → 1
です。
#シェルソート(第2番：h = …, 40, 13, 4, 1)
from typing import MutableSequence
def shell_sort(a: MutableSequence) -> None:
"""シェルソート(第2版)"""
n = len(a)
h = 1
while (h < n // 9):
h = h * 3 + 1
while h > 0:
for i in range(h, n):
j = i - h
tmp = a[i]
while j >= 0 and a[j] > tmp:
a[j + h] = a[j]
j -= h
a[j + h] = tmp
h //= 3
if __name__ == '__main__':
print('シェルソート(第2版)')
num = int(input('要素数：'))
x = [None] * num #要素数numの配列を生成
for i in range(num):
x[i] =int(input(f'x[{i}]：'))
shell_sort(x) #配列xをシェルソート
print('昇順にソートしました。')
for i in range(num):
print(f'x[{i}]={x[i]}')
シェルソートの時間計算量はO(n**1.25)であり、極めて高速です。ただし、離れた要素を交換するため、安定ではありません。
本日は以上です。ありがとうございました。