선택 정렬 (Selection Sort)

선택 정렬은 추가 메모리를 요구하지 않는 제자리 정렬 (in-place sort) 방법 중 하나로 해당 배열의 각 인덱스에 어떤 원소를 넣을지 선택하는 방법입니다. 예를 들어 살펴보기 전에 정렬은 기본적으로 오름차순 정렬을 기본으로 가정합니다. 숫자가 제일 작은 원소가 맨 앞에 오고 제일 큰 원소가 맨 뒤에 가는 식이죠. 내림차순도 가능하고 오름차순의 반대 방향으로 하기 때문에 정렬 원리만 알면 가능합니다. 한 번 배열 [9,6,7,3,5] 예를 들어 살펴볼까요 ?  

 

EXAMPLE

 

1. 첫 번째 인덱스 (현재는 9) 에 넣을 원소를 선택합니다. 이 때, 두 번째 인덱스부터 마지막 인덱스까지 값을 비교해서 가장 작은 값 (3)을 선택하고 첫 번째 인덱스에 넣습니다.
2. 두 번째 인덱스에 넣을 원소를 선택합니다. 이 때, 세 번째 인덱스부터 마지막 인덱스까지 값을 비교해서 가장 작은 값 (5)를 선택하고 두 번째 인덱스에 넣습니다.
3. 이 과정을 마지막 인덱스 직전까지 반복합니다. 마지막 인덱스에서는 그 이후에 비교할 값이 없으니 할 수가 없고 전 단계에서 비교를 통해 작은 값들은 선택이 되었을 테니 자연스럽게 가장 큰 값이 남아 있게 됩니다.

 

파이썬 코드

from typing import List

def selection_sort(List: array) -> List:
    ## 첫 번째 for loop
    for i in range(0, len(array)-1): # 마지막 인덱스는 필요 없음
    	minIndex = i
    	for j in range(i+1, len(array)): # 다음 인덱스부터 마지막 인덱스까지 비교
            if array[j] < array[midIndex]: # 가장 작은 값의 인덱스 획득
                minIndex = j 
        ## Swap
        array[minIndex], array[i] = array[i], array[minIndex]
        
 	return array

 

시간 복잡도

알고리즘의 꽃은 시간 복잡도 계산이죠. 선택 정렬은 제자리 정렬로 추가적인 메모리를 요구하지 않기 때문에 공간 복잡도는 크지 않습니다. 그렇다면 선택 정렬의 시간 복잡도는 어떻게 될까요? 

배열의 길이를 n이라 했을 때, 먼저 전체 배열에 대해 for 문을 돌립니다. 첫 번째 for 문 안에서 그 다음 인덱스부터 마지막 인덱스까지 값을 비교해야 하니 n-1, n-2, n-3 .. 1 번의 작업이 필요합니다.

따라서 $(n-1) + (n-2) + (n-3) .... + 2 + 1 = O(n^2)$ 의 빅오가 나오게 되네요. 참고로 빅오는 상수항은 무시하고 가장 큰 차수만 사용합니다. 

 

홍머스 정리

• 쉽다. 
• 최선의 경우에도 O(n^2) 시간 복잡도를 가지니 비효율적이다.

 

참조

• gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html