선택정렬(Selection Sort) 알고리즘

선택정렬은 각 반복에서 정렬되지 않은, 가장 작은 요소를 선택하고, 해당 요소를 배열의 가장 앞쪽에 위치시켜 차례대로 정렬시키는 알고리즘입니다.

---

선택 정렬 알고리즘

1. 첫 번째 요소를 minimum으로 설정합니다.

첫 번째 요소, 20을 minimum으로 선택

2. 두 번째 요소(12)와 비교합니다.
두 번째 요소가 minimum보다 작으면, 두 번째 요소를 minimum으로 선택합니다.

이후 세번째 요소와 비교하여 minimum(지금 두번째 요소)보다 세번째 요소가 더 작으면,
세번째 요소를 minimum으로 선택합니다.

이 process는 마지막까지 반복되어, 한 바퀴가 끝나면 첫 번째 minimum자리에 가장 작은 값이 위치하게 됩니다.

첫 번째 회차에서, minimum으로 2를 선택

 

선택된 minimum은 배열의 첫 번째 자리에 위치하게 됩니다.

minimum값을 첫번째 인덱스의 자리에 swap

 

모든 요소가 올바른 위치에 배치될때까지 1~3단계를 반복합니다.

첫 번째 반복, minimum=2

두 번째 반복, minimum=10

세 번째 반복, minimum=12

네 번째 반복, minimum=15

---

선택 정렬 알고리즘

selectionSort(array, size)
  for i from 0 to size - 1 do
    set i as the index of the current minimum
    for j from i + 1 to size - 1 do
      if array[j] < array[current minimum]
        set j as the new current minimum index
    if current minimum is not i
      swap array[i] with array[current minimum]
end selectionSort

 

먼저 minimum의 자리를 찾아야겠죠?

for i from 0 to size - 1 do

전체 배열에서 1을 빼서 인덱스의 총 크기를 정합니다. 0~n
그리고 i에 배열의 0을 줘서 첫번째 임을 알려줍니다.

 

set i as the index of the current minimum

minimum에는 i(=0)의 인덱스 번호가 들어가서, 첫 번째 위치임을 알려줍니다.

 

for j from i + 1 to size - 1 do

배열은 i다음 번째 j부터 끝까지(전체길이의 인덱스에서 -1)까지 반복합니다.

 

if array[j] < array[current minimum]
        set j as the new current minimum index

만약, 현재 값이 minimum보다 작다면, 현재 값(j)를 minimum에 넣어줍니다.

 

if current minimum is not i
      swap array[i] with array[current minimum]

i번째 값과 minimum의 값이 일치하지 않는다면 minimum이 바뀌었다는 뜻이므로 swap합니다.