CS50 | 알고리즘 - 버블 정렬, 선택 정렬, 정렬 알고리즘의 실행 시간

버블 정렬

정렬되지 않은 리스트를 탐색하는 것 보다 정렬한 뒤 탐색하는 것이 더 효율적이다.

정렬 알고리즘 중 하나는 버블 정렬이다.

버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말한다.

버블 정렬은 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중한다.

이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다.

아래와 같은 8개의 숫자가 임의의 순서로 나열되어 있다.

이 숫자들을 오름차순으로 정렬하기 위해 바로 옆의 있는 숫자들과 비교하는 방법을 사용해 보자.

 

6 3 8 5 2 7 4 1

 

먼저 가장 앞의 6과 3을 비교해서 순서를 바꾼다.

 

교환 전: 6 3 8 5 2 7 4 1

교환 후: 3 6 8 5 2 7 4 1

 

다음 쌍인 6과 8을 비교해보면 교환할 필요가 없으므로 그대로 둔다.

바로 다음에 있는 쌍인 8과 5를 비교해서 순서를 바꾼다.

 

교환 전: 3 6 8 5 2 7 4 1

교환 후: 3 6 5 8 2 7 4 1

 

이런 식으로 숫자 끝까지 진행하면 아래와 같이 정렬이 된다.

 

3 6 5 2 7 4 1 8

 

하지만 아직 오름차순으로 정렬이 되지 않았기 때문에, 다시 처음부터 동일한 작업을 반복한다.

 

3 6 5 2 7 4 1 8

3 6 5 2 7 4 1 8 (교환)

3 5 6 2 7 4 1 8 (교환)

3 5 2 6 7 4 1 8 

3 5 2 6 7 4 1 8 (교환)

3 5 2 6 4 7 1 8 (교환)

3 5 2 6 4 1 7 8

 

조금 더 잘 정렬이 된 모습이다. 이 과정을 끝까지 반복하면 최종적으로 아래와 같이 오름차순 정렬이 될 것이다.

 

1 2 4 3 5 6 7 8

 

이러한 정렬 방식을 ‘버블 정렬’이라고 한다.

마치 거품이(비교 및 교환이) 터지면서 위로 올라오는 (배열의 옆으로 이동하는) 방식이기 때문이다.

아래와 같이 의사 코드로 나타낼 수 있다.

Repeat n–1 times

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

중첩 루프를 돌아야 하고,

n개의 값이 주어졌을 때 각 루프는 각각 n-1번, n-2번 반복되므로  

(n-1)*(n-2) = n^2-3n+2(n−1)∗(n−2)=n​2​​−3n+2  번의 비교 및 교환이 필요하다.

여기서 가장 크기가 큰 요소는 n^2 이므로 위와 같은 코드로 작성한 버블 정렬 실행 시간의 상한은 O(n^2)이라고 말할 수 있다.

정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교를 해야 하므로

위와 같은 코드로 작성한 버블 정렬의 실행 시간의 하한도 여전히 Ω(n^2)이 된다. 

 

선택 정렬

보통 배열이 정렬되어 있으면 정렬되지 않은 배열보다 더 쉽게 탐색할 수 있다.

정렬을 위한 알고리즘 중 선택정렬을 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아

첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다.

선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.

다음과 같은 정렬되지 않은 숫자들을 오름차순 정렬해보도록 하자.

 

6 3 8 5 2 7 4 1

 

먼저 아래 숫자들 중에서 가장 작은 값을 찾는다.

 

6 3 8 5 2 7 4 1

 

가장 작은 값인 1은 가장 앞에 있어야 하므로 현재 리스트의 첫 번째 값인 6과 교환한다.

 

1 3 8 5 2 7 4 6

 

그리고 정렬되어 있는 1은 제외하고, 두 번째 숫자부터 시작해서 또 가장 작은 값을 찾는다.

 

1 3 8 5 2 7 4 6

 

가장 작은 값인 2는 정렬되지 않는 숫자들 중에서 가장 앞에 있어야 하므로 3과 교환한다.

 

1 2 8 5 3 7 4 6

 

이 과정을 더 이상 교환이 일어나지 않을때까지 반복하면, 아래와 같이 오름차순 정렬이 완료된다.

 

1 2 3 4 5 6 7 8

 

이러한 정렬 방법을 ‘선택 정렬’ 이라고 한다. 의사 코드로 아래와 같이 표현할 수 있다.

For i from 0 to n–1

    Find smallest item between i'th item and last item

    Swap smallest item with i'th item

여기서도 두 번의 루프를 돌아야 한다.

바깥 루프에서는 숫자들을 처음부터 순서대로 방문하고, 안쪽 루프에서는 가장 작은 값을 찾아야 한다.

따라서 소요 시간의 상한은 O(n^2)이 된다. 하한도 마찬가지로 Ω(n^2) 이다. 버블 정렬과 동일하다.

 

선형 검색, 이진 검색, 버블 정렬, 선택 정렬의 실행시간이 각각 어떻게 되는지 정리해보자.

 

실행시간의 상한

• O(n^2): 선택 정렬, 버블 정렬
• O(n log n)
• O(n): 선형 검색
• O(log n): 이진 검색
• O(1)

실행시간의 하한

• Ω(n^2): 선택 정렬, 버블 정렬
• Ω(n log n)
• Ω(n)
• Ω(log n)
• Ω(1): 선형 검색, 이진 검색

여기서 버블 정렬을 좀 더 잘 할 수 있는 방법을 알아보자.

만약 정렬이 모두 되어 있는 숫자 리스트가 주어진다면 어떨까?

 

원래 의사 코드는 아래와 같다.

Repeat n–1 times

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

여기서 안쪽 루프에서 만약 교환이 하나도 일어나지 않는다면 이미 정렬이 잘 되어 있는 상황일 것이다.

따라서 바깥쪽 루프를 ‘교환이 일어나지 않을때’까지만 수행하도록 다음과 같이 바꿀 수 있다.

Repeat until no swaps

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

따라서 최종적으로 버블 정렬의 하한은 Ω(n)이 된다.

상황에 따라서는 선택 정렬보다 더 빠른 방법이 되는 것이다.

 

실행시간의 하한

• Ω(n^2): 선택 정렬
• Ω(n log n)
• Ω(n): 버블 정렬
• Ω(log n)
• Ω(1): 선형 검색, 이진 검색

재귀

함수를 사용할 때 main 안에서 프로그램을 작성하면서 필요한 순간에 호출하여 사용한다.

그런데 main 역시 함수라는 점을 기억해야한다. main이라는 함수 안에서 또 다른 함수를 사용한 것이다.

이 사실을 알게 되었을 때, 함수가 본인 스스로를 호출해서 사용할 수 있는지에 대해 의문을 가질 수 있다.

답은 가능하다. 이러한 것을 재귀(Recursion)라고 부른다.

 

아래와 같이 피라미드 모양을 출력하기 위해 다음과 같은 코드를 작성할 수 있다.

 

#

##

###

####

 

#include <cs50.h>
#include <stdio.h>

void draw(int h);

int main(void)
{
    // 사용자로부터 피라미드의 높이를 입력 받아 저장
    int height = get_int("Height: ");

    // 피라미드 그리기
    draw(height);
}

void draw(int h)
{
    // 높이가 h인 피라미드 그리기
    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            printf("#");
        }
        printf("\n");
    }
}

 

위 코드는 높이를 입력 받아 중첩 루프를 통해 피라미드를 출력해주는 draw 함수를 정의한 것이다.

여기서 꼭 중첩 루프를 써야만 할까? 사실 바깥 쪽 루프는 안 쪽 루프에서 수행하는 내용을 반복하도록 하는 것일 뿐이다.

따라서 바깥 쪽 루프를 없앤 draw함수를 만들고, 이를 ‘재귀적으로’ 호출하도록 해서 똑같은 작업을 수행할 수 있다.

즉, draw 함수 안에서 draw 함수를 호출 하는 것이다. 아래 코드와 같이 수정할 수 있다.

#include <cs50.h>
#include <stdio.h>

void draw(int h);

int main(void)
{
    int height = get_int("Height: ");

    draw(height);
}

void draw(int h)
{
    // 높이가 0이라면 (그릴 필요가 없다면)
    if (h == 0)
    {
        return;
    }

    // 높이가 h-1인 피라미드 그리기
    draw(h - 1);

    // 피라미드에서 폭이 h인 한 층 그리기
    for (int i = 0; i < h; i++)
    {
        printf("#");
    }
    printf("\n");
}

 

draw 함수 안에서 draw 함수를 다시 호출 하는 부분을 유의하시기 하자.

h라는 높이를 받았을 때, h-1 높이로 draw 함수를 먼저 호출하고, 그 후에 h 만큼의 #을 출력한다.

여기서 내부적으로 호출된 draw 함수를 따라가다 보면 h = 0인 상황이 오게 된다.

따라서 그 때는 아무것도 출력을 하지 않도록 하는 조건문을 추가해줘야 한다.

 

이렇게 재귀를 사용하면 중첩 루프를 사용하지 않고도 하나의 함수로 동일한 작업을 수행할 수 있다.

 

병합 정렬

전화번호부의 분할 정복 탐색처럼 데이터를 반으로 나누어간다는 것과 공통점이 있는 방법, 병합 정렬(합병 정렬)

병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다.

그리고 이 과정은 재귀적으로 구현된다.

마찬가지로 다음 숫자들을 오름차순으로 정렬해 보자.

 

7 4 5 2 6 3 8 1

 

먼저 숫자들을 반으로 나눈다.

 

7 4 5 2 | 6 3 8 1

 

그리고 나눠진 부분 중 첫번째를 한번 더 반으로 나눠본다.

 

7 4 | 5 2 | 6 3 8 1

 

마지막으로 한 번 더 나눠본다.

 

7 | 4 | 5 2 | 6 3 8 1

 

이제 숫자가 두 개 밖에 남지 않았으므로 더 이상 나누지 않고, 두 숫자를 다시 병합한다.

단, 이 때 작은 숫자가 먼저 오도록 한다. 4와 7의 순서를 바꿔서 병합하는 것이다.

 

4 7 | 5 2 | 6 3 8 1

 

마찬가지로 5 2 부분도 반으로 나눈 후에 작은 숫자가 먼저 오도록 다시 병합할 수 있다.

 

4 7 | 2 5 | 6 3 8 1

 

그럼 이제 4 7과 2 5 두 개의 부분들을 병합하자.

각 부분들의 숫자들을 앞에서 부터 순서대로 읽어들여 비교하여 더 작은 숫자를 병합되는 부분에 가져온다.

즉, 4와 2를 먼저 비교해서 2를 가져온다. 그 후에 4와 5를 비교해서 4를 가져온다.

그리고 7과 5를 비교해서 5를 가져오고, 남은 7을 가져온다.

 

2 4 5 7 | 6 3 8 1

 

이제 남은 오른쪽 4개의 숫자들도 위와 동일한 과정을 거친다.

 

2 4 5 7 | 1 3 6 8

 

마지막으로 각각 정렬된 왼쪽 4개와 오른쪽 4개의 두 부분을 병합한다.

2와 1을 비교하고, 1을 가져온다. 2와 3을 비교하고, 2를 가져온다. 4와 3을 비교하고, 3을 가져온다.

4와 6을 비교하고… 이 과정을 병합이 끝날때까지 진행하면 아래와 같이 정렬이 완료된다.

 

1 2 3 4 5 6 7 8

 

전체 과정을 요약해서 도식화해보면 아래와 같다.

 

7 | 4 | 5 | 2 | 6 | 3 | 8 | 1 → 가장 작은 부분 (숫자 1개)으로 나눠진 결과이다.

4   7 | 2   5 | 3   6 | 1   8 → 숫자 1개씩을 정렬하여 병합한 결과이다.

2   4   5   7 | 1   3   6   8 → 숫자 2개씩을 정렬하여 병합한 결과이다.

1   2   3   4   5   6   7   8 → 마지막으로 숫자 4개씩을 정렬하여 병합한 결과이다.

 

이러한 방법을 ‘병합 정렬’ 이라고 한다.

 

병합 정렬 실행 시간의 상한은 O(n log n) 이다.

숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고,

각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문이다.

실행 시간의 하한도 역시 Ω(n log n) 이다. 숫자들이 이미 정렬되었는지 여부에 관계 없이 나누고 병합하는 과정이 필요하기 때문이다.

 

퀴즈까지 끝!

내일은 배운 내용을 총 복습해야겠다.