データ構造とアルゴリズム：selection（選択ソート）

重要度：高い

左から一つづつ、一時的にtmp変数に格納して左から順にそれぞれの配列要素と大きさを比べ、tmpに入っている数値より小さい数値があればその数と入れ替える。その作業を一番右端まで行い、一番小さい数値が入っているインデックス番号の要素を配列の一番左の要素と入れ替える。

その後、２番目の数値を同じようにtmp変数に格納して、左から一番小さい値を除いて右に順次確認していく。 比較して小さい数値があれば、その数値と入れ替え、最後まで行った後に一番小さい数値の入っている要素と左から２番目の要素を入れ替えどんどん小さい値を左側の要素と入れ替えて、左側から順に小さい要素を揃えていく。

３と５を比較した時に３の方が小さいので５の要素と入れ替える。

from typing import List

def selectioin_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    for i in range(len_numbers):
        min_idx = i
        for j in range(i + 1, len_numbers):
            if numbers[min_idx] > numbers[j]:
                min_idx = j
        numbers[i], numbers[min_idx] = numbers[min_idx], numbers[i]

    return numbers


nums = [random.randint(0, 1000) for i in range(10)]
print(selectioin_sort(nums))

[351, 532, 539, 550, 601, 686, 773, 871, 908, 995]

rubyで描くとこんな感じでできた

def selection_sort(numbers)
  len_numbers = numbers.length
  
  (0..len_numbers-1).each do |i|
    min_idx = i
    ((i+1)..len_numbers-1).each do |j|
      if numbers[min_idx] > numbers[j]
        min_idx = j
      end  
    end
    numbers[i], numbers[min_idx] = numbers[min_idx], numbers[i]
  end
  numbers
end


numbers = Array.new(10){ rand 1000 }
print selection_sort(numbers)

[71, 91, 136, 271, 352, 371, 566, 720, 861, 870]