[알고리즘] Selection Sort

Selection Sort

처리되지 않은 데이터 중 가장 작은 데이터를 선택해

처리되지 않은 데이터 중 맨 앞의 데이터와 바꿔가는 알고리즘

---

Process

1. 처리되지 않은 데이터 중 최소값을 찾는다

2. 처리되지 않은 데이터 중 맨 앞에 위치한 값과 교체한다

3. 그 다음 인덱스 부터 같은 방법으로 교체한다

---

Code

numbers = []
length = 100

for i in range(length, 0, -1):
    numbers.append(i)

for idx, num in enumerate(numbers):
    min_idx = idx
    for n_idx in range(idx + 1, length):
        if numbers[n_idx] < numbers[min_idx]:
            min_idx = n_idx
    numbers[idx], numbers[min_idx] = numbers[min_idx], numbers[idx]

print(numbers)

---

Time Complexity

(n-1) + (n-2) + (n-3) + ... + 2 + 1 = n(n-1)/2 이므로 O(N²) 이다

 

Bubble Sort 와 동일한 시간복잡도이지만, 그보다 실제로 교환하는 횟수가 적어 비교적 효율적이다

---

Space Complexity

정렬하고자하는 배열안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다 (in-place sorting)

따라서 O(N) 이다

---

최솟값을 찾아 swap 하는 과정에서 같은 값을 가지는 데이터의 인덱스가 변경될 수 있으므로 unstable sorting 이다