概要
概要
未整列領域を最後まで見て最小値を選び、先頭と交換します。交換回数は少なめですが、比較回数は基本的に O(n²) です。
ソート / Selection Sort（選択ソート）
未整列領域を最後まで見て最小値を選び、先頭と交換します。交換回数は少なめですが、比較回数は基本的に O(n²) です。
目次
このページでわかること
概要
未整列領域を最後まで見て最小値を選び、先頭と交換します。交換回数は少なめですが、比較回数は基本的に O(n²) です。
考え方
for i = 0 to n - 2
minIndex = i
for j = i + 1 to n - 1
if a[j] < a[minIndex]
minIndex = j
swap a[i], a[minIndex]要点
O(n²)
O(n²)
O(n²)
いいえ
補足
その場で何度も交換せず、最後に最小値だけを前へ持ってきます。
各パスで高々 1 回なので少なく見えます。
ただし未整列部分は毎回最後まで見るため、比較回数は減りません。
動きで確認
ここでは「今の最小候補がどれか」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。