[알고리즘] 선택정렬(Selection Sort)이란? | c언어 선택정렬 구현

선택정렬(Selection Sort)

선택정렬은 현재 위치에 들어갈 값을 찾아서 바꾸는 알고리즘이다. 오름차순으로 정렬하는 선택정렬은 다음과 같은 과정을 거친다.

1. 현재 정렬되지 않은 가장 맨 앞의 인덱스를 선택한다.
2. 현재 인덱스의 다음 인덱스부터 끝까지 가장 작은 값을 찾으면 현재 인덱스의 값과 바꿔준다.
3. 다음 인덱스에서 위 과정을 반복한다.

과정이 잘 이해가 가지 않는다면, 다음 예시를 보면 이해가 빠를 것이다.

예를 들어 위와 같은 배열을 오름차순으로 선택정렬한다고 하자.

 

가장 먼저 맨 앞의 7부터 시작한다. 7 뒤의 값들 중 가장 작은 값인 1과 자리를 바꾼다. i는 현재 인덱스, minIdx는 가장 작은 값의 인덱스를 나타낸다.

 

다음은 5와 그 이후 값들 중 가장 작은 값인 3의 위치를 바꿔준다.

 

다음으로 7과 그 이후 값들 중 가장 작은 값인 4의 위치를 바꿔준다.

다음으로 7과 그 이후 값들 중 가장 작은 값인 5의 위치를 바꿔준다.

오름차순으로 정렬이 완료된 것을 확인 할 수 있다.

 

선택정렬의 특징

• 선택정렬은 하나의 배열에서 값을 바꾸는 식으로 동작하므로 공간 복잡도는 O(1) 이다. 기껏해야 swap 할때 임시변수 하나의 공간 정도가 더 필요하므로 선택 정렬은 in-place 정렬이다.
• 탐색은 (n-1)번, (n-2)번 ... 1번 진행되므로 시간복잡도는 O(n^2) 이다.
• 선택정렬은 중복된 키값이 순서대로 바뀌지 않을 수 있어 (예를 들어 {7,7,1}을 오름차순으로 선택정렬해보라) not-stable 하다. 

 

소스코드

#include <stdio.h>
#define LEN 5
 
void selectionSort(int* arr){
    int i,j, min, minIdx, temp;
    for(i=0; i < LEN ; i++){
        min = 987654321;
        for(j=i+1; j<LEN; j++){
            if(arr[j] < min){
                min = arr[j];
                minIdx = j;
            }
        }
        /* swap */
        temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}
 
int main(){
    
    int arr[LEN] = {7,5,1,4,3};
    int i;
    printf("정렬 전 : ");
    for(i=0; i<5; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    selectionSort(arr);
    printf("정렬 후 : ");
    for(i=0; i<5; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");    
    
    return 0; 
}

 

---