演習課題「正しくシェルソートを実装する」
整数nと要素数nの数列A、整数kと要素数kの数列hが与えられるので、この数列を与えられた間隔列hでシェルソートでソートしてください。
右側のコードエリアに用意されているコードには誤りがあります。訂正し、問題を解くコードを完成させてください。
期待する出力値
4
※有料会員になるとこの動画をご利用いただけます
詳しい説明を読む
＃03:シェルソートの実装
実際にシェルソートを実装してみます。そして、効率的にソートが行われていることを確認してみましょう。
n
A_1 A_2 ... A_n
k
h_1 h_2 ... h_k・ 入力はすべて整数
・ 1行目に、数列の要素数nが与えられます。
・ 2行目に、数列の要素A_1,A_2,...,A_nが半角スペース区切りで与えられます。
・ 3行目に、間隔列の要素数kが与えられます。
・ 2行目に、間隔列の要素h_1,h_2,...,h_kが半角スペース区切りで与えられます。
def insertion_sort(a, n, h):
num_of_move = 0
# i が h から n - 1 までのループを書く
for i in range(h, n):
# a[i] を x に保存する
x = a[i]
# 変数 j を用意する
j = i - h
# j が 0 以上で、a[j] が x より大きい間
while j >= 0 and a[j] > x:
# a[j] を h だけ右にずらす
a[j+h] = a[j]
# j を h だけ減らす
j -= h
num_of_move += 1
# a[j+h] に x を代入する
a[j+h] = x
print(num_of_move)
def shell_sort(a, n, h, k):
for i in range(k):
# 間隔 h の挿入ソートを呼び出す
insertion_sort(a, n, h[i])
n = int(input())
a = [int(x) for x in input().split()]
k = int(input())
h = [int(x) for x in input().split()]
shell_sort(a, n, h, k)10
7 6 10 2 5 4 8 3 9 1
2
4 1
プログラミング学習
>
Python3
>
新・アルゴリズムとデータ構造入門 Python編
>
新・アルゴリズムとデータ構造入門 Python編5: 効率的なソートアルゴリズム
>
シェルソートの実装
def insertion_sort(a, n, h):num_of_move = 0
コードの実行