🧨 문제

nums라는 정렬되지 않은 숫자 리스트가 주어지면, 선택정렬 알고리즘을 사용하여 오름차순(1,2,3..10) 으로 정렬된 리스트를 return하는 함수를 만들어라

🎯 풀이

def selectionSort(nums):
    for i in range(len(nums) - 1):
      min_index = i
      for j in range(i + 1, len(nums)):
        if nums[min_index] > nums[j]:
          min_index = j

      nums[i], nums[min_index] = nums[min_index], nums[i]

    return nums
    

🏹 선택 정렬

선택 정렬(選擇整列, selection sort)은
제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
   
   

비교하는 것이 상수 시간에 이루어진다는 가정 아래,
n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 $O(n^2)$ 만큼의 시간이 걸린다.

선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.

📍 복잡도

$N$은 테이블(혹은 리스트)의 자료 수,
최선, 평균, 최악일 경우 선택 정렬에 소요되는 비교 횟수를 각각 $C_{min}$, $C_{av}$, $C_{max}$ 라고 할 때,

🧶 예제

[9, 1, 6, 8, 4, 3, 2, 0]

1회
[9, 1, 6, 8, 4, 3, 2, 0]
[0, 1, 6, 8, 4, 3, 2, 9]

2회
[0, 1, 6, 8, 4, 3, 2, 9]

3회
[0, 1, 6, 8, 4, 3, 2, 9]
[0, 1, 2, 8, 4, 3, 6, 9]

4회
[0, 1, 2, 8, 4, 3, 6, 9]
[0, 1, 2, 3, 4, 8, 6, 9]

5회
[0, 1, 2, 3, 4, 8, 6, 9]

6회
[0, 1, 2, 3, 4, 8, 6, 9]
[0, 1, 2, 3, 4, 6, 8, 9]

출처
위키백과