Selection Sort with C

수업 중 selection sort를 C로 구현하는 게 있어 업로드 합니다? 한다?

매번 C++ 을 쓰다가 C를 쓰니 문법이 기억날랑말랑 했다.
하지만 멀록은 내가 가장 좋아하는 명령어라서 기억이 났다.

Selection sort 과정

Selection sort은 정렬 기법 중에 하나로 구현은 쉽지만 시간복잡도가 크다.

오래 걸린다는 뜻이다. Selection sort의 구현방법은 다음과 같다.

(오름차순 기준)

1. N개의 숫자가 무작위로 있다고 가정할 때, 각각 1번, 2번 ... N-1번, N번 이라고 생각해보자.

2. index를 1로 초기화한다

3. index번 ~ N번까지 중 가장 작은 수를 찾는다.

4. 젤 작은 것을 찾아 index 위치의 수와 자리를 바꾼다.

5. index++을 해준 뒤 2,3 번을 index가 N이 될 때까지 해준다.

대강 { 1, 5, 3, 6, 4, 2, 7, 9, 8, 6 } 이 있다고 가정하면

결과는 { 1, 2, 3, 4, 5, 6, 7, 8, 9 } 가 되는 것이다.(정렬이니 당연하다)

시간복잡도 정리

첫 번째 자리의 수를 찾기위해 N번의 탐색,

두 번째 자리의 수를 찾기위해 N-1번의 탐색,

세 번째 자리의 수를 찾기위해 N-2번의 탐색

...

...

...

N-1 번째 자리의 수를 찾기위해 2번의 탐색,

N 번째 자리의 수를 찾기위해 1번의 탐색.

탐색한 수를 전부 더하면 N(1+N) / 2 이다.

합공식이 가물가물한데.. 사실 시간복잡도 계산에선 차수가 제일 큰 놈이 중요하기 때문에

째깐둥이들은 조금 엇나가도 괜찮을 거다.

N(1+N) / 2 = 1/2(N^2 + N)

여기서 차수가 제일 큰 놈은 N^2이니, 앞뒤로 다 떼어주면 

시간복잡도는 O(N^2)가 되는 것이다.

소스코드 정리

#include <stdio.h>
 
void swap(int arr[], int x, int y);
void selectionSort(int arr[], int size);
 
int main(void)
{
    int N;
    scanf("%d", &N);
 
    int *arr = (int*)malloc(sizeof(int) * N);
    for(int i = 0; i < N; i++)
    {
        scanf("%d", &arr[i]);
    }
 
    selectionSort(arr, N);
 
    for(int i = 0; i < N; i++)
    {
        printf("%d ", arr[i]);
    }
    free(arr);
    system("pause");
    return 0;
}
 
 
void swap(int arr[], int x, int y)
{
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}
 
void selectionSort(int arr[], int size)
{
    for(int i = 0; i < size -1 ; i++)
    {
        int min = arr[i];
        int index = i;
        for(int j = i; j < size; j++)
        {
            if(min > arr[j])
            {
                min = arr[j];
                index = j;
            }
        }
 
        if(index != i)
        {
            swap(arr, index, i);
        }
    }
}

N을 입력받고, N개의 무작위 정수를 입력받는다.

이후 정렬된 N개의 수를 출력한다.

위의 'Selection sort 과정'을 읽으면 이해에 도움이 될 것이다.