コード判定結果
この動画を見るにはpaiza会員登録のうえ
有料会員登録が必要です
演習課題「正しくシェルソートを実装する」
整数nと要素数nの数列A、整数kと要素数kの数列hが与えられるので、この数列を与えられた間隔列hでシェルソートでソートしてください。
右側のコードエリアに用意されているコードには誤りがあります。訂正し、問題を解くコードを完成させてください。
【制約】
・ 入力は全て整数
・ 1≦k
・ 1=h_k
期待する出力値
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