4. Array(배열) - Selection Sort(선택정렬)

1. Selection Sort란? 

- 가장 왼쪽의 수(index 0)을 기준으로 최소값을 찾아 swap하여 정렬하는 알고리즘

- 한번 탐색을 할 때마다, 기준 index값이 1씩 증가한다. 

 

a) 예제를 통한 선택정렬의 이해

---

2. 선택정렬의 시간복잡도

- 선택정렬은 버블정렬과 삽입정렬과 동일한 O(n^2)의 시간복잡도를 갖는다. 

---

3. Selection Sort의 안정성

- 선택정렬은 불안정(unstable)한 알고리즘이다. 

---

4. Selection Sort 직접 구현해보기 

- 선택정렬의 개념을 배웠으니, 직접 코드로 구현해보자. 

from typing import List

def selection_sort(case: List[int]) -> List[int]:
  for idx in range(1, len(case)):
    flag = idx - 1
    temp = 0
    min_idx = 0 
    while idx < len(case):
      if case[flag] > case[idx]:
        diff = case[flag] - case[idx]
        if diff > temp:
          temp = diff
          min_idx = idx
      idx += 1
      if idx == len(case) and min_idx != 0:
        case[flag], case[min_idx] = case[min_idx], case[flag]
  return case

print(selection_sort(case = [9, 3, 7, 1, 5])) # [1, 3, 5, 7, 9] 출력

---

5. Selection Sort 코드 

from typing import List

def selection_sort2(case: List[int]) -> List[int]:
  for idx in range(0, len(case)):
    min_num = case[idx]
    min_idx = idx
    for i in range(idx, len(case)):
      if case[i] < min_num:
        min_num = case[i]
        min_idx = i
    case[idx], case[min_idx] = case[min_idx], case[idx] #swap
  return case

print(selection_sort2(case = [5, 4, 3, 2, 1])) # [1, 2, 3, 4, 5] 출력

---

6. 코드리뷰

- 내가 구현한 선택정렬과 정석적인 선택정렬의 코드를 비교해보자. 

1) 최소값을 구하는 방법

- 나는 최소값을 구하기 위해 기준값을 고정해놓고 비교 값과의 차이를 이용했다. 

- 정석 코드에서는 최소값을 하나 지정하고, 나머지 요소와의 크기 비교를 통해서 최소값을 찾았다. 

- 이 과정에서 코드의 길이와 간결성이 달라졌다.