정렬

버블 정렬Bubble Sort

버락 오바마 대통령이 선거 유세를 하던 시절 구글을 방문했을 때 구글 임원이 질문 하나를 던진다. "백만 개의 32비트의 정수를 정렬하는 가장 효율적인 방법이 뭡니까What is the most efficient way to sort a million 32-bit integers?" 방청객들은 웃고, 오바마가 뜸을 들이자 구글 임원은 미안하다며 말을 풀어서 설명하려는데(아마도 그는 오바마가 한 방 먹었다고 생각했던 것 같다) 오바마가 자신있게 대답한다. "적어도 버블 정렬Bubble sort은 잘못된 방향일 거라고 생각합니다I think the 'bubble sort' would be the wrong way to go."

버블 정렬은 어떤 알고리즘이길래 100만 개의 정수를 정렬하는 데 적합하지 않은가? (어떻게 버락 오바마도 그것을 아는가) 버블 정렬의 원리는 다음과 같다. 제일 왼쪽의 요소부터 제일 오른쪽의 요소까지 비교를 시작한다. 비교는 인접한 항끼리만 진행된다. 첫 번째 원소와 두 번째 원소를 비교해 작은 것을 왼편으로 둔다. 그 다음 두 번째 요소(바뀌었을 수도 있고 아닐 수도 있다)의 자리로 이동해 두 번째 요소와 세 번째 요소에 같은 작업을 반복한다. 그렇게 마지막까지 가면 마지막 요소는 집단 내에서 가장 큰 수로 고정된다. n개의 숫자가 있었다고 한다면 n-1번의 비교를 통해 제일 큰 수를 우측에 정렬하는 데 성공했다.

문제는 이게 끝이 아니라는 점이다. 우리는 n번째 요소가 명확히 정렬되었다는 것을 알 뿐, 다른 요소들은 아직 정렬되지 않았다는 사실을 안다. 그러므로 같은 작업을 n-1번째 원소까지 진행한다. n-2번의 비교를 통해 n-1번째 요소를 정렬하는 것이 가능하다. 이렇게 정렬을 하다보면 n(n-1)/2번의 정렬을 통해 배열 내의 수들을 완벽히 정렬할 수 있게 된다.

딱 보기에도 지나치게 많은 자원이 소모되는 것처럼 느껴지지 않는가? 아래에 이를 구현한 코드가 있다.

#include <stdio.h>

void BubbleSort( int Set[], int length )
{
    int i, j, tmp;

    for ( i = 0; i < length - 1; i++ )
    {
        for ( j = 0; j < length - (i + 1); j++ )
        {
            if ( Set[j] > Set[j+1] )
            {
                tmp = Set[j+1];
                Set[j+1] = Set[j];
                Set[j] = tmp;
            }
        }
    }
}

삽입 정렬Insertion Sort

삽입 정렬Insertion sort은 버블 정렬을 조금 더 개선시켰다. 원리는 간단하다. 첫 번째 원소와 두 번째 원소를 먼저 비교해서 순서대로 정렬한다. 그러면 우리는 이것을 오른편으로 버블링bubbling(전파)시키는 것이 아니라 이 둘이 정렬이 끝났다고 보고 이 둘을 고정시킨다.

다음으로는 세 번째 원소와 두 번째 원소를 비교한다. 만일 세 번째 원소가 두 번째 원소보다 작으면 첫 번째 원소와도 비교하여 필요한 위치로 이동시킨다. 그렇지 않은 경우, 첫 번째 원소와의 비교를 생략하고 네 번째 원소로 눈을 돌린다(원소의 비교를 맨 끝 원소부터 하든 맨 앞 원소부터 하든 큰 상관은 없다). 같은 작업을 마지막 원소에까지 진행한다.

삽입 정렬의 비교 횟수는 최대 n(n-1)/2로 버블 정렬과 동일하다. 하지만 아주 운이 좋은 경우 n-1번만 비교해도 된다(첫 번째 원소와 두 번째 원소를 제외하고 모든 원소가 원래부터 정렬이 잘 되어 있었던 경우). 버블 정렬은 운이 좋아도 운이 나빠도 n(n-1)/2번의 비교가 필요했다. 즉, 경우에 따라 삽입 정렬의 성능이 좀 더 좋을 가능성이 있다.

#include <stdio.h>
#include <string.h>

void InsertionSort( int Set[], int length )
{
    int i, j, val;

    for ( i = 1; i < length; i++ )
    {
        if ( Set[i-1] <= Set[i] ) continue;

        val = Set[i];

        for ( j = 0; j < i; j++ )
        {
            if ( Set[j] > val )
            {
                memmove( &Set[j+1], &Set[j], sizeof( Set[0] ) * (i - j) );
                Set[j] = val;
                break;
            }
        }
    }
}

여기서의 핵심은 break;다. 이 녀석이 들어갈 수 있어 버블 정렬보다 삽입 정렬이 더 빠른 것이다.

memmove는 byte 단위로 움직이므로 sizeof( Set[0] )을 곱해주는 것을 까먹지 말자!

퀵 정렬Quick Sort

이름부터 자부심에 가득 찬 '퀵' 정렬Quick sort은 임의의 기준 요소를 통해 요소들을 분할해서 정렬하는 기법이다. n개의 요소 중 한 개를 임의로 정하여 그 요소의 왼편에는 기준이 된 수보다 작은 수들을, 오른편에는 기준이 된 수보다 큰 수들을 놓는다. 기준이 되었던 수는 정렬이 완료된 것이므로 기준이 된 수의 위치는 고정해준다.

남은 일은 같은 작업을 기준이 된 요소의 왼편과 오른편에서 진행해주는 것이다. 다만 한 가지, 성능을 더 끌어올리기 위해 만일 기준 요소의 양쪽에 정렬되지 않은 수가 1개 혹은 0개가 남으면 거기서 정렬을 종료한다. 왜냐하면 그 요소를 기준으로 잡고 비교를 하려고 해도 더 비교할 나머지 수가 없는 상태이므로 자동으로 정렬이 완료된 것과 마찬가지이기 때문이다.

다만 링크드 리스트 기반이 아닌 배열 기반의 요소를 퀵 정렬해야 할 때 노드와 노드 사이에 요소를 삽입하고 인덱스index를 변경하는 것이 요소의 수가 많아질수록 부담이 된다(이런 과정을 파티션 스텝partition step이라고 한다). 따라서 우리는 기준 요소를 맨 왼쪽 혹은 맨 오른쪽 값으로 잡고, 양쪽 끝에서부터 투 포인터two pointer를 가지고 비교를 하는 알고리즘을 채택할 수 있다.

양 포인터는 중앙으로 진군하며, 왼쪽의 포인터가 기준 요소보다 크면 멈춘다. 오른쪽 포인터는 기준 요소보다 작을 때 멈춘다. 두 포인터가 멈추면 두 요소의 위치를 서로 교환해준 뒤 한 칸씩 중앙으로 전진한다. 만일 두 포인터가 만나서 파티션 스텝이 끝났다면 마지막으로 기준 요소와 왼쪽 포인터(만일 왼쪽 끝의 값이 기준값이었다면)를 바꾸어주고 한 사이클을 마무리짓는다. 만일 오른쪽 끝의 값이 기준값이었다면 오른쪽 포인터와 기준값의 위치를 치환해준다.

한쪽 끝의 값을 기준으로 잡고 두 포인터의 시작을 반대편에서 기준값쪽으로 이동시키며 정렬하는 파티션 스텝을 짤 수도 있다. 같은 퀵 정렬이어도 파티션 스텝이 차이가 날 수 있고, 그 차이로 인해 성능이 크게 달라질 수 있다. 아래의 코드는 위의 설명을 기준으로 짜여진 코드이다.

#include <stdio.h>

void Swap( int* a, int* b )
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int PartitionStep( int Set[], int left, int right )
{
    int first = left;
    int pivot = Set[first];

    left++;

    while ( left <= right )
    {
        while ( Set[left] <= pivot && left < right )
            left++;
        
        while ( Set[right] >= pivot && left <= right )
            right--;

        if ( left < right )
            Swap( &Set[left], &Set[right] );
        else
            break;
    }

    Swap( &Set[first], &Set[right] );

    return right;
}

void QuickSort( int Set[], int left, int right )
{
    if ( left < right )
    {
        int idx = PartitionStep( Set, left, right );

        QuickSort( Set, left, idx - 1 );
        QuickSort( Set, idx + 1, right );
    }
}

다음 재귀 QuickSort()의 실행을 위해 PartitionStep()이 인덱스를 반환하게 구현하는 것이 포인트다.

참고로 C언어에는 퀵 정렬이 qsort()라는 내장 함수로 구현되어 있어 직접 구현할 필요 없이 비교함수만 잘 짜서 사용하면 된다. 비교함수는 해당 집합(혹은 배열)을 어떤 기준으로 정렬할지 알려주는 함수다. 대개 오름차순이거나 내림차순이다. 여러 개를 순차비교하여 정렬하는 것도 가능하다.

#include <stdlib.h>

int cmp( const void* _elem1, const void* _elem2 )
{
    int* elem1 = (int*)_elem1;
    int* elem2 = (int*)_elem2;

    if ( *elem1 > *elem2 )
        return 1;
    else if ( *elem1 < *elem2 )
        return -1;
    else
        return 0;
}

qsort( Books, bookNum, sizeof( int ), cmp );

첫 번째 파라미터parameter는 정렬 대상인 배열의 주소이며 두 번째 파라미터는 데이터 요소의 갯수, 세 번째는 개별 데이터 요소의 크기를 나타낸다. 마지막 파라미터는 상기한 비교함수다.

퀵 정렬도 단점은 있다. 퀵 정렬은 데이터가 완전히 거꾸로 들어오는 사태에 대비하기 어렵다. Big-O 표기법 기준으로 제곱의 시간복잡도를 갖는다. 따라서 어떤 케이스에도 시간 소요가 비슷해야 하는 경우에는 병합 정렬Merge Sort이나 힙 정렬Heap Sort을 사용해야 한다. 다만 병합 정렬은 추가적인 메모리 공간을 필요로 한다. 힙 정렬은 퀵 정렬이나 병합 정렬과 마찬가지로 시간복잡도가 NlogN이나, 셋 중엔 느린 편이다.

참고 서적:
박상현, 2022, 한빛미디어, 『이것이 자료구조+알고리즘이다』

참고 사이트:
유튜브: Bubble sort algorithm || obama || fun
나무위키: 정렬 알고리즘
얍문's Coding World..: 정렬별 장단점 및 시간복잡도
IBM documentation: memcmp() — 버퍼 비교