[C] 선택 정렬과 삽입 정렬 원리, C언어로 구현하기

1. 선택 정렬

 

1-1. 선택 정렬의 원리

선택 정렬이란, 가장 작은 것을 선택해서 앞으로 보내는 정렬 기법이다. 가장 작은 것을 선택하는 데에 N번, 앞으로 보내는 데에 N번의 연산을 하기 때문에 O(N2)의 시간 복잡도를 가진다. 

 

이렇게 초기 원소가 있다고 했을 때, 

2

4

3

1

9

6

7

8

10

5

 

가장 작은 원소는 1이므로 맨 앞으로 보내준다. 기존의 맨 앞에 있었던 원소와 자리를 바꿔준다. 

1

4

3

2

9

6

7

8

10

5

 

나머지 원소 중 가장 작은 값인 2를 1 다음으로 넣어 주고 마찬가지로 그 자리에 있었던 원소와 자리를 바꿔준다. 

1

2

3

4

9

6

7

8

10

5

 

이렇게 해서 결과적으로 올림차순으로 정렬할 수 있는 것이다.

1

2

3

4

5

6

7

8

9

10

 

1-2. 선택 정렬 구현하기

 

(1) 필요한 헤더 파일을 가져오고, 초기 배열 a를 원소가 1000까지 들어가도록 자리를 만들어 줬다.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define SIZE 1000

int a[SIZE];

 

(2) swap 함수를 만들어 준다. 

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

 

(3) main 함수에서 먼저 변수를 선언해 주고, 정렬을 원하는 수의 개수와 숫자를 입력받도록 한다. 

 

(4) 이중 for문을 돌면서, 가능한 큰 값이 할당되어 있는 min보다 작은 수를 발견하면 min값을 업데이트한다. 원래 자리의 원소와 최소 원소의 인덱스를 활용하여 swap 함수로 값을 바꿔 준다. 

int main(void) {
    int n, min, index;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; i++) {
        min = INT_MAX; 
        for (int j = i; j < n; j++) {
            if (min > a[j]) {
                min = a[j];
                index = j;
            }
        }

        swap(&a[i], &a[index]);
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
}

 

(5) 출력하여 결과를 확인한다.

6
2 8 3 7 1 6
1 2 3 6 7 8

 

2. 삽입 정렬

 

2-1. 삽입 정렬의 원리

 

삽입 정렬이란 각 숫자를 적절한 위치에 삽입하는 정렬 기법이다. 들어갈 위치를 선택하는 데 N번, 선택하는 횟수로 N번이므로 O(N2)의 시간 복잡도를 가진다. 선택 정렬과 시간 복잡도는 같지만, 일반적으로 삽입 정렬이 선택 정렬보다 빠르게 동작한다.

 

초기 원소가 이렇게 있으면 2번째 원소인 4부터 출발해서 앞의 인덱스 중 4가 들어갈 곳을 확인한다. 그대로 있는 게 맞다.

2

4

3

1

9

6

7

8

10

5

 

다음 3같은 경우에는 인덱스를 앞으로 1씩 옮기다가 2, 4 사이에 위치한다.

2

3

4

1

9

6

7

8

10

5

 

이어서 1은 들어갈 위치를 인덱스 1씩 앞으로 가면서 고르게 되는데 가장 작은 수이므로 맨 앞으로 간다.

1

2

3

4

9

6

7

8

10

5

 

9는 그 자리에 계속 있는다.

1

2

3

4

9

6

7

8

10

5

 

정렬이 성공적으로 수행되면 다음과 같다.

1

2

3

4

5

6

7

8

9

10

 

2-2. 삽입 정렬 코드로 구현하기

 

삽입 정렬을 코드로 나타내면 다음과 같다.

int main(void) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n - 1; i++) {
        int j = i;
        while (j >= 0 && a[j] > a[j + 1]) {
            swap(&a[j], &a[j + 1]);
            j--;
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
}

선택정렬과 다른 점은 for문을 돌면서 대상 원소가 왼쪽에 있는 원소보다 크다면 위치를 하나씩 바꿔준다는 것이다.

 

4
3 2 5 1
1 2 3 5

정렬이 잘 된 것을 확인할 수 있다.