[Algorithm] C - 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

요약

시간 복잡도 : O(n ^ 2)

1. 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 정렬 알고리즘
2. 배열의 가장 작은 값을 찾아 맨 처음 요소와 위치를 변경하는 작업을 반복하여 정렬을 수행
3. 같은 값이 있을 경우 상대적인 위치가 변경될 수 있어 안전하지 않음
4. 배열의 크기를 알고 있기 때문에 이동 횟수를 미리 알 수 있다는 장점이 있음

단순 선택 정렬이란

단순 선택 정렬이란 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 정렬 알고리즘이다.
어떤 배열이 있을 때, 배열의 가장 작은 값을 찾아 맨 처음 요소와 위치를 변경하는 작업을 반복하여 정렬을 수행한다.

 

1. 배열에서 가장 작은 값 1을 찾아 0번째 인덱스 6과 위치를 교환한다.
2. 1번째 인덱스부터 가장 작은 값 3을 찾아 정렬되지 않은 2번째 인덱스 4와 위치를 교환한다.
3. 2번째 인덱스부터 가장 작은 값 4을 찾아 정렬되지 않은 3번째 인덱스 8와 위치를 교환한다.
4. 3번째 인덱스부터 가장 작은 값 6을 찾아 정렬되지 않은 4번째 인덱스 8와 위치를 교환한다.
5. 4번째 인덱스부터 가장 작은 값 7을 찾아 정렬되지 않은 5번째 인덱스 8와 위치를 교환한다.
6. 5번째 인덱스부터 가장 작은 값 8을 찾아 정렬되지 않은 6번째 인덱스 8와 위치를 교환한다.
7. 마지막 인덱스 9가 가장 낮은 값이므로 정렬이 완성된다.

이렇게 단순 선택 정렬의 교환 과정은 2단계로 나뉜다.

1. 배열에서 가장 작은 값을 선택
2. 절열하지 않은 앞쪽의 요소와 교환

위 과정을 n - 1회 반복하면 선택 정렬이 완성된다.

단점

선택 정렬은 서로 떨어져 있는 요소를 교환하는 것이기 때문에 안정적이지 않다.
만약 중복되는 값이 있을 경우 요소의 위치가 뒤바뀌기 때문이다.

 

예제 코드

#include <stdio.h>
#include <stdlib.h>

void SelectionSort(int *a, int n);
void Swap(int* num1, int* num2);

int main() 
{
    int i, n;
    int *x;
    
    printf("요소 개수 : ");
    scanf("%d", &n);
    
    x = malloc(sizeof(int) * n);
    
    for(i = 0; i < n; i++) {
        printf("x[%d] : ", i);
        scanf("%d", &x[i]);
    }
    
    SelectionSort(x, n);
    
    printf("오름차순 정렬\n");
    
    for(i = 0; i < n; i++) {
        printf("x[%d] = %d\n", i, x[i]);
    }
    
    free(x);

    return 0;
}

void Swap(int* num1, int* num2) 
{  
    int temp;
    
    temp = *num2;
    *num2 = *num1;
    *num1 = temp;
}

void SelectionSort(int *a, int n)
{
    int i, j;
    
    for(i = 0; i < n; i++) {
        // min 값 정의
        int min = i;
        for(j = i + 1; j < n; j++) {
            // 전체 배열에서 min값 확인
            if(a[j] < a[min]) {
                min = j;
            }
            
            // 정렬되지 않은 앞쪽 인덱스와 가장 작은 값 교환
            Swap(&a[i], &a[min]);
        }
    }
}

실행 결과

요소 개수 : 7
x[0] : 5
x[1] : 23
x[2] : 12
x[3] : 77
x[4] : 12
x[5] : 68
x[6] : 99
오름차순 정렬
x[0] = 5
x[1] = 12
x[2] = 12
x[3] = 23
x[4] = 77
x[5] = 68
x[6] = 99

 

https://github.com/JeHeeYu/Algorithm/tree/main/Sort/Selection%20Sort

GitHub - JeHeeYu/Algorithm: 알고리즘 문제 풀이

 

 

출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문: C 언어 편