[Algorithm] 선택 정렬(Selection Sort) 이란?

선택 정렬(Selection Sort)

선택 정렬은 n개의 레코드 중에서 최소값을 찾아 첫 번째 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 알고리즘이다.

 

선택 정렬의 특징은 다음과 같다.

 

• 평균과 최악 모두 수행 시간 복잡도는 O(n^2) 이다.
• 회전을 수행할 때마다 가장 작은 값의 레코드가 맨 앞으로 이동하므로 다음 회전에서는 맨 앞에 있는 레코드는 정렬하지 않는다.
  • 예를 들어 [8, 5, 6, 2, 4] 라는 5의 길이를 가지고 있는 배열이 있다고 가정해보면
  • 1회전이 끝나면 2라는 값은 맨 앞으로 정렬된다.
  • 따라서 2회전 때에는 2번째 부터 정렬 알고리즘을 수행하면 된다.

예제를 통해서 선택 정렬을 이해해보자.

선택 정렬 예제

• 초기 상태 : [8, 5, 6, 2, 4]

1 회전

• 첫 번째 레코드(8)와 두 번째 레코드(5)을 비교하여 첫 번째 레코드가 값이 크므로 교환한다.
• 첫 번째 레코드(5)와 세 번째 레코드(6)을 비교하여 첫 번째 레코드가 값이 작으므로 교환하지 않는다.
• 첫 번째 레코드(5)와 네 번째 레코드(2)을 비교하여 첫 번째 레코드가 값이 크므로 교환한다.
• 첫 번째 레코드(2)와 다섯 번째 레코드(4)을 비교하여 첫 번째 레코드가 값이 작으므로 교환하지 않는다.
• 1회전 후 정렬 상태 : [2, 8, 6, 5, 4]

2 회전

• 첫 번째 레코드는 1회전이 끝났으므로 비교하지 않는다. (2번째 부터 수행)
• 두 번째 레코드(8)와 세 번째 레코드(6)을 비교하여 두 번째 레코드가 값이 크므로 교환한다.
• 두 번째 레코드(6)와 네 번째 레코드(5)을 비교하여 두 번째 레코드가 값이 크므로 교환한다.
• 두 번째 레코드(5)와 다섯 번째 레코드(4)을 비교하여 두 번째 레코드가 값이 크므로 교환한다.
• 2회전 후 정렬 상태 : [2, 4, 8, 6, 5]

3 회전

• 두 번째 레코드는 2회전이 끝났으므로 비교하지 않는다. (3번째 부터 수행)
• 세 번째 레코드(8)와 네 번째 레코드(6)을 비교하여 세 번째 레코드가 값이 크므로 교환한다.
• 세 번째 레코드(6)와 다섯 번째 레코드(5)을 비교하여 세 번째 레코드가 값이 크므로 교환한다.
• 3회전 후 정렬 상태 : [2, 4, 5, 8, 6]

4 회전

• 세 번째 레코드는 3회전이 끝났으므로 비교하지 않는다. (4번째 부터 수행)
• 네 번째 레코드(6)와 다섯 번째 레코드(5)을 비교하여 네 번째 레코드가 값이 크므로 교환한다.
• 4회전 후 정렬 상태 : [2, 4, 5, 6, 8]

선택 정렬 파이썬(Python) 코드

def selection_sort(A):
    for i in range(len(A) - 1):
        min_index = i

        for j in range(i + 1, len(A)):
            if A[j] < A[min_index]:
                min_index = j

        A[i], A[min_index] = A[min_index], A[i]

A = [8, 5, 6, 2, 4]
selection_sort(A)