選択ソート
選択ソートアルゴリズムは、最も直感的なソートアルゴリズムの一つです。配列の中から最小要素を繰り返し見つけ出し、それを先頭の位置に移動します。そして、残りの配列でも同じように最小要素を探し、配列の最後に到達するまでこれを続けます。
a = [...]
for i in range(len(a)): # a[i:] の中から最小要素を a[i] に配置する
min_idx = i # 最小要素のインデックス
for j in range(i + 1, len(a)): # 最小要素のインデックスを探す
if a[j] < a[min_idx]: # もしさらに小さい要素を見つけたら
min_idx = j # 最小要素のインデックスを更新
a[i], a[min_idx] = a[min_idx], a[i] # a[i] と a[min_idx] を入れ替える
print(a)各イテレーションでは、残りの配列から最小値を取り出し、そのインデックスを使って、現在の要素と入れ替えます。もし現在の要素が最小値であれば、自分自身と入れ替えるだけなので配列は変化しません。
選択ソートは、配列から最小要素を探し出して、現在のインデックスとそれを入れ替えるアルゴリズムです。つまり各イテレーションで、残りの配列全体をループして最小値を探します（
min 関数は最小値を求めるために配列を一つ一つ走査します）。そのため、アルゴリズムの全体の実行時間は、約 n 回のイテレーションそれぞれで n 回ほどの処理を行うことになり、合計で の演算量となります。いくつかの配列でこのアルゴリズムの処理をシミュレートしてみましょう:
[4, 1, -1, 0, 2, 8]
i = 0⇒val = -1⇒idx = 2⇒ swap ⇒[-1, 1, 4, 0, 2, 8]
i = 1⇒val = 0⇒idx = 3⇒ swap ⇒[-1, 0, 4, 1, 2, 8]
i = 2⇒val = 1⇒idx = 3⇒ swap ⇒[-1, 0, 1, 4, 2, 8]
i = 3⇒val = 2⇒idx = 4⇒ swap ⇒[-1, 0, 1, 2, 4, 8]
i = 4⇒val = 4⇒idx = 4⇒ swap ⇒[-1, 0, 1, 2, 4, 8]
i = 5⇒val = 8⇒idx = 5⇒ swap ⇒[-1, 0, 1, 2, 4, 8]
[10, 5, 1, -1, -2, -7]
i = 0⇒val = -7⇒idx = 5⇒ swap ⇒[-7, 5, 1, -1, -2, 10]
i = 1⇒val = -2⇒idx = 4⇒ swap ⇒[-7, -2, 1, -1, 5, 10]
i = 2⇒val = -1⇒idx = 3⇒ swap ⇒[-7, -2, -1, 1, 5, 10]
i = 3⇒val = 1⇒idx = 3⇒ swap ⇒[-7, -2, -1, 1, 5, 10]
i = 4⇒val = 5⇒idx = 4⇒ swap ⇒[-7, -2, -1, 1, 5, 10]
i = 5⇒val = 10⇒idx = 5⇒ swap ⇒[-7, -2, -1, 1, 5, 10]
[1, 2, 3, 4, 5]
i = 0⇒val = 1⇒idx = 0⇒ swap ⇒[1, 2, 3, 4, 5]
i = 1⇒val = 2⇒idx = 1⇒ swap ⇒[1, 2, 3, 4, 5]
i = 2⇒val = 3⇒idx = 2⇒ swap ⇒[1, 2, 3, 4, 5]
i = 3⇒val = 4⇒idx = 3⇒ swap ⇒[1, 2, 3, 4, 5]
i = 4⇒val = 5⇒idx = 4⇒ swap ⇒[1, 2, 3, 4, 5]
課題
与えられた
n 個の整数を、選択ソートを使って昇順に整列してください。入力
入力の最初の行には、配列の要素数を表す単一の整数
n (1 ≤ n ≤ 1000) が与えられます。次の行には、
n 個の整数 ( ≤ ≤ ) が空白区切りで与えられます。出力
入力で与えられた配列を昇順に整列した結果を出力してください。
例
入力 | 出力 |
5
5 5 3 2 3 | 2 3 3 5 5 |
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB