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

선택 정렬

선택 정렬이란 제자리 정렬 알고리즘 중 한가지 방법이다.

보통 오름차순으로 정렬되는 선택 정렬은 다음과 같은 과정으로 이루어져 있다.

1. 가장 작은 원소 값을 찾는다.
2. 그 값을 맨 앞에 있는 값과 교체를 한다.
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.
4. 하나의 원소만 남을 때까지 위의 과정을 반복한다.

 

선택 정렬 예시​

 

예시를 통해 좀 더 자세히 살펴보자.

위 그림과 같이, [5, 3, 8, 1, 2, 7] 로 구성된 배열이 있다고 하자.

1. 앞에서부터 탐색하여, 가장 작은 원소 1을 찾은 후 맨 앞의 값 5와 교체한다.
2. 1의 위치를 확정짓고 [3,8,5,2,7] 중 가장 작은 수 2를 맨 앞의 값 3과 교체한다.
3. 같은 방법으로 [8,5,3,7] 중 가장 작은 수 3과 맨 앞의 값 8을 교체한다.
   ....
   마지막 원소까지 같은 방법으로 진행하면
   최종적으로 [1, 2, 3, 5, 7, 8] 이라는 정렬된 배열이 완성된다.

 

선택정렬 구현 및 시간복잡도 및 공간복잡도

void selectionSort(int[] arr) {
    int indexMin, temp;
    for (int i = 0; i < arr.length-1; i++) { // 1.
        indexMin = i;
        for (int j = i + 1; j < arr.length; j++) { // 2.
            if (arr[j] < arr[indexMin]) { // 3.
                indexMin = j;
            } 
        } // 4.swap(arr[indexMin], arr[i]) 
        temp = arr[indexMin]; 
        arr[indexMin] = arr[i];
        arr[i] = temp; 
    } 
    System.out.println(Arrays.toString(arr)); 
}

이 위의 코드처럼, 선택정렬은 데이터가 n 개일 때

첫번째 회전에서의 비교 횟수 : 1 ~ n-1 => n-1개

두번째 회전에서의 비교 횟수 : 2 ~ n-1 => n-2개

 

결국, n(n-1)/2개의 시간이 걸리게 되고

n개의 원소를 가진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸린다.

 

TIP

최선, 평균, 최악의 경우 시간복잡도는 O(n^2)로 동일하다.

선택정렬은 주어진 배열 안에서 교환을 통하여 정렬되는 제자리 정렬 이므로,

공간복잡도는 O(n) 이다.

 

선택 정렬의 장단점​

장점​

1. 알고리즘이 단순하다.
2. 정렬을 위한 비교 횟수는 많지만, 거품 정렬에 비해서 교환하는 횟수가 적기 때문에
   많은 교환이 일어나야 하는 자료에서는 효율적이다.
3. 다른 메모리 공간이 필요하지 않는다.

단점​

1. 시간복잡도가 O(n^2)이므로 비효율적이다.