[알고리즘] 정렬(1) - 선택 정렬, 버블 정렬, 삽입 정렬

반응형

 

 정렬은 정해진 순서대로 나열하는 것이다. 학교에 처음 갔을 때 키 순서대로 자리를 배치하는 것이 좋은 예이다.  컴퓨터에서 정렬 알고리즘은 시간 복잡도가 Θ(\(n^2\))인 것 부터, Θ(\(nlogn\)), Θ(\(n\))등 여러가지 알고리즘이 있다. 각각의 알고리즘들을 알아보면서 직접 구현하는 시간을 가져보겠다. 모든 예시코드에는 공통적으로 아래의 배열을 예시로 정렬 알고리즘을 구현할 것이다.

const int SIZE = 10;
int arr[SIZE] = { 6, 2, 9, 7, 3, 10, 4, 1, 8, 5 };

선택 정렬(Selection Sort)

가장 큰 원소를 찾은 후, 맨 뒷자리에 있는 원소와 자리를 바꾸는 정렬 알고리즘이다. 가장 큰 원소의 이동이 끝나면, 다음으로 큰 원소를 마지막 자리 이전의 원소와 자리를 바꾼다. 이 과정을 계속해서 반복하면 된다. 아래는 위의 배열을 예시로 선택 정렬의 과정을 간략하게 표현한 것이다.

 

가장 큰 수(10)을 찾는다.

6

2

9

7

3

10

4

1

8

5

맨 뒤(5)와 자리를 바꾼다.

6

2

9

7

3

5

4

1

8

10

다음으로 큰 수(9)를 찾는다.

6

2

9

7

3

5

4

1

8

10

뒤에서 2번째(8)과 바꾼다.

6

2

8

7

3

5

4

1

9

10

.
.
.

정렬이 끝난 배열

1

2

3

4

5

6

7

8

9

10

 

C++로 구현한 선택 정렬

void selection_sort(int* arr) {
    for (int i = SIZE - 1; i >= 0; i--) {
        int maxi = i;
        for (int j = 0; j <= i; j++) {
            if (arr[maxi] < arr[j]) {
                maxi = j;
            }
        }
        swap(arr[maxi], arr[i]);
    }
}

선택 정렬의 시간 복잡도를 구해보자. 첫번째 for 루프가 n번 반복될 동안, 두번째 for 루프의 비교연산은 n-1번 수행된다. 전체 수행 시간은 \((n-1) + (n-2) + ... + 2 + 1 = \)\(n(n-1)\over2\)가 된다. 즉, 선택 정렬의 시간 복잡도는 Θ(\(n^2\))이다.

 

버블 정렬(Selection Sort)

선택 정렬과 비슷하게 큰 원소를 뒤로 보내는 것은 똑같다. 다만, 선택 정렬과는 달리 이웃한 쌍을 서로 비교해 가며 서로의 자리를 바꿔가는 것이다.

 

맨 앞에서 부터 순서대로 이웃한 쌍들(6과 2)를 비교한다.

6

2

9

7

3

10

4

1

8

5

더 큰 원소를 뒤로 보낸다. 

2

6

9

7

3

10

4

1

8

5

 

2

6

9

7

3

10

4

1

8

5

 

2

6

7

9

3

10

4

1

8

5

.

.
.

2

6

7

3

9

4

1

8

5

10

이 과정을 다시 반복한다.

.

.

.

정렬이 끝난 배열

1

2

3

4

5

6

7

8

9

10

 

C++로 구현한 버블 정렬

void bubble_sort(int* arr) {
    for (int i = SIZE - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        } 
    }
}

이 경우의 시간 복잡도를 알아보자. 첫번째 for문은 n번 반복될 동안. 두번째 for문은 n-1번 반복된다. 즉, 2번째 for문은 \((n-1) + (n-2) + ... + 2 + 1 = \)\(n(n-1)\over2\) 다시 말해 버블 정렬의 시간 복잡도는 Θ(\(n^2\))이다. 그런데, 위의 코드는 이미 정렬된 배열일 경우에도 무의미한 순환을 실시한다. 이를 방지해줘보자.

void bubble_sort(int* arr) {
    for (int i = SIZE - 1; i > 0; i--) {
        bool is_sorted = true;
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                is_sorted = false;
            }
        }
        if (is_sorted == true) {
            return;
        }
    }
}

이미 정렬이 되어있다면 for 루프를 바로 빠져나오게 한다. 그렇게 되면 두번째 for 루프를 통해 처음부터 끝까지 한번만 돌면 된다. 즉, 시간 복잡도가 Θ(\(n\))이 된다.

 

삽입 정렬(Insertion Sort)

정렬이 되지 않은 부분의 원소를 적절한 위치를 찾아 삽입하는 정렬 방식이다.

 

2의 위치가 정렬되지 않았다.

6

2

9

7

3

10

4

1

8

5

2를 6 앞에 삽입한다.

2

6

9

7

3

10

4

1

8

5

7의 위치가 정렬되지 않았다.

2

6

9

7

3

10

4

1

8

5

7을 9앞에 삽입한다.

2

6

7

9

3

10

4

1

8

5

3의 위치가 정렬되지 않았다.

2

6

7

9

3

10

4

1

8

5

3을 6앞에 삽입한다.

2

3

6

7

9

10

4

1

8

5

.

.

.

정렬이 끝난 배열

1

2

3

4

5

6

7

8

9

10

 

C++로 구현한 삽입 정렬

void insertion_sort(int* arr) {
    for (int i = 1; i < SIZE; i++) {
        for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
            swap(arr[j - 1], arr[j]);
        }
    }
}

뒤에서 부터 앞으로 삽입해 나가는 것에 유의하자.

이 정렬 방식의 시간 복잡도를 구해보자. 2번째 for 루프를 유심히 보면, 이미 정렬이 되어 있다면 루프가 돌지 않음을 알 수 있다. 즉, 이미 정렬된 배열일 경우에는 Θ(\(n\))이 된다. 이에 반해 최악의 경우를 생각해보자. 자료가 역순일 경우가 그러하겠다. 이 경우에는, 첫번째 for 루프가 n - 1번, 두번째 for 루프는 i번이 수행된다. 즉, \(1 + 2 + ... + (n-2) + (n-1) = \)\(n(n-1)\over2\)로 최악의 경우에는 시간 복잡도가 Θ(\(n^2\))이 된다.

 

 

[Reference]

문병로, 「쉽게 배우는 알고리즘」 (한빛 아카데미, 2018)

 

 

728x90