[알고리즘] Selection Sort(선택 정렬)

선택 정렬은 배열 안의 자료 중 가장 작은수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다.

선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.

 

그림과 같이 정렬되지 않은 것들로부터 가장 작은 것을 찾아서 sorted list 옆에 둔다. 이 과정을 끝까지 반복해서 주어진 list를 정렬한다.

 

다음과 같은 정렬되지 않은 숫자들을 오름차순 정렬해보자.

6 3 8 5 2 7 4 1

 

먼저 가장 작은 값을 찾는다.

6 3 8 5 2 7 4 1

 

가장 작은 값인 1은 가장 앞에 있어야 하므로 현재 리스트의 첫 번째 값인 6과 교환한다.

1 3 8 5 2 7 4 6

 

그리고 정렬되어 있는 1은 제외하고, 두 번째 숫자부터 시작해서 또 가장 작은 값을 찾는다.

1 3 8 5 2 7 4 6

 

가장 작은 값인 2는 정렬되지 않는 숫자들 중에서 가장 앞에 있어야 하므로 3과 교환한다.

1 2 8 5 3 7 4 6

 

이 과정을 더 이상 교환이 일어나지 않을때까지 반복하면, 아래와 같이 오름차순 정렬이 완료된다.

1 2 3 4 5 6 7 8

 

의사코드는 아래와 같이 표현할 수 있다.

For i from 0 to n–1

    Find smallest item between i'th item and last item

    Swap smallest item with i'th item

 

즉, for문으로 나타내면 다음과 같다.

for( i=0; i<n-1; i++ ){

    smallest(i.e. list[min])를 찾기 위해서 list[i]부터 list[n-1]까지 검사한다.

    list[i]와 list[min]을 교환한다.

}

 

위의 for문을 C코드로 나타내면 아래와 같다.

//#define SWAP(x, y, t) ( (t) = (x), (x) = (y), (y) = (t) )
void sort(int list[], int n){
    int i, j, min, temp;
    for(i=0; i< n-1; i++){
        min = i;
        for(j=i+1; j<n; j++)
            if(list[j] < list[min])
                min=j;
        SWAP(list[i], list[min], temp);
    }
}

 

파이썬으로 나타내면 다음과 같다.

def selectionSort(alist):
   for fillslot in range(0, len(alist)-1):
       positionOfMin = fillslot
       for location in range(fillslot, len(alist)):
           if alist[location] < alist[positionOfMin]:
               positionOfMin = location
       temp = alist[fillslot]
       alist[fillslot] = alist[positionOfMin]
       alist[positionOfMin] = temp

 

총 2번의 루프를 돌아야 한다.

바깥 루프에서는 숫자들을 처음부터 순서대로 방문하고, 안쪽 루프에서는 가장 작은 값을 찾아야 한다.

따라서 소요 시간의 상한은 O(n^2)이 된다. 하한도 마찬가지로 Ω(n^2)이다. 

 

출처: 부스트코스, 모두를 위한 컴퓨터 과학, https://www.boostcourse.org/cs112/lecture/119023/?isDesc=false