[파이썬으로 배우는 알고리즘] 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)이란?

선택 정렬은 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 그 위치에 어떤 원소를 넣을지 "선택"하는 정렬 알고리즘입니다.

 

---

선택 정렬 과정

위와 같이 정렬되어 있지 않은 배열을 선택 정렬 알고리즘을 사용하여 정렬해보겠습니다.

 

제일 왼쪽 인덱스 0 즉, 제일 작은 원소가 들어갈 자리를 정하고, 해당 인덱스에 어떤 원소를 넣을지 다음 원소부터 순서대로 탐색합니다.

 

11, 2, 4, 3 원소 중에는 2가 제일 작으므로 2의 인덱스 2를 기억합니다.

 

인덱스 0에 저장된 원소 10과 인덱스 2에 저장된 2를 비교하여 2가 더 작은 것을 알 수 있습니다. 2가 더 작기 때문에 두 원소를 서로 바꿔줍니다.

 

1회전이 끝나고 인덱스 0의 원소를 구했습니다. 그다음으로 왼쪽에 위치한 인덱스 1에 어떤 원소를 넣을지 다음 원소부터 순서대로 탐색합니다.

 

10, 4, 3 원소 중에는 3이 제일 작으므로 3의 인덱스 4를 기억합니다.

 

인덱스 1에 저장된 원소 11과 인덱스 4에 저장된 3을 비교하여 3이 더 작은 것을 알 수 있습니다. 3이 더 작기 때문에 두 원소를 서로 바꿔줍니다.

 

위 과정을 반복하여 각 인덱스 자리에 들어갈 원소를 저장하여 정렬이 완료됩니다.

 

---

선택 정렬 특징

• 간단한 구현
• 정렬을 위한 비교 횟수는 많지만 버블 정렬에 비해 실제로 교환하는 횟수는 적음
• 정렬 과정에서 배열에서 값을 바꾸는 식으로 동작하여 공간 복잡도는 O(N). 값을 바꿀 때 임시 공간만 필요하기 때문에 in-place 정렬
• 최선이든 최악이든 시간 복잡도는 O(N^2)

 

---

선택 정렬 구현

코드

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


a = [10, 11, 2, 4, 3]
print('###정렬전###')
print(a)
selection_sort(a)
print('###정렬후###')
print(a)

결과