演習課題「挿入ソートの部分的な実装」
整数nと、要素数nの整数列aが与えられるので、挿入ソートでaを小さい順にソートするプログラムを作成してください。
アルゴリズムが正しく実装されていることを確認するために、各i(i=1,2,...,n-1) についてi回目の処理が終わった時点での配列を出力してください。
右側のコードエリアには、入力を受け取り、挿入ソートのループ処理と配列の出力をおこなうコードが用意されています。コードを書き加え、問題を解くコードを完成させてください。
期待する出力値
1 4 3 5 2
1 3 4 5 2
1 3 4 5 2
1 2 3 4 5
演習課題「挿入ソート・コード修正」
整数nと、要素数nの整数列aが与えられるので、挿入ソートでaを小さい順にソートするプログラムを作成してください。
アルゴリズムが正しく実装されていることを確認するために、各i(i=1,2,...,n-1)についてi回目の処理が終わった時点での配列を出力してください。
右側のコードエリアに用意されているコードには誤りがあります。訂正し、問題を解くコードを完成させてください。
期待する出力値
1 4 3 5 2
1 3 4 5 2
1 3 4 5 2
1 2 3 4 5
演習課題「挿入ソートの実装」
整数nと、要素数nの整数列aが与えられるので、挿入ソートでaを小さい順にソートするプログラムを作成してください。
アルゴリズムが正しく実装されていることを確認するために、各i(i=1,2,...,n-1)についてi回目の処理が終わった時点での配列を出力してください。
右側のコードエリアには、入力を受け取るコードが用意されています。コメントを参考にコードを書き加え、問題を解くコードを完成させてください。
期待する出力値
1 4 3 5 2
1 3 4 5 2
1 3 4 5 2
1 2 3 4 5
＃03:挿入ソート
実際に挿入ソートを実装してレベルアップ問題集の問題を解いてみます。
def print_array(a):
print(*a)
def insertion_sort(a, n):
for i in range(1, n):
# 先に a[i] を保存しておき、x とする
x = a[i]
# 挿入する位置を探すための変数 j を用意する
j = i - 1
# j が 0 以上かつ a[j] が x より大きい間
while j >= 0 and x < a[j]:
# a[j] を 1 つ右にずらす
a[j+1] = a[j]
# j を 1 減らす
j -= 1
# a[j+1] に x を挿入する
a[j+1] = x
print_array(a)
n = int(input())
a = [int(x) for x in input().split()]
insertion_sort(a, n)
4
8 1 3 2