[자료구조] C++로 쉽게 풀어쓴 자료구조 : 13장, 정렬

내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다.

1) 13장 정렬

정렬이란 물건을 크기순으로 오름차순이나, 내림차순으로 나열하는 것 을 의미한다. 일반적으로 정렬시켜야할 대상을 레코드(record)라고 불린다. 레코드는 다시 field라고 하는 보다 작은 단위로 나누어 진다. 여러 필드중 레코드들을 구분해주는 역할을 key가 한다.

 

선택 정렬 (selection sort)

정렬되지 않은 숫자가 모여 있는 리스트 B 와 정렬이 완료된 숫자들이 들어가는 리스트 A 가 있다고 하자.

A{ } : B{5, 3, 8, 1, 2, 7}

 

선택 정렬은 B의 리스트에서 가장 작은 숫자를 선택하여 A리스트로 이동하는 작업을 반복한다. B리스트가 공백이 될때까지 반복한다.

A{1 } : B{5, 3, 8, 2, 7}

A{1, 2 } : B{5, 3, 8, 7}

A{1, 2, 3 } : B{5, 8, 7}

A{1, 2, 3, 5} : B{8, 7}

A{1, 2, 3, 5, 7 } : B{8}

A{1, 2, 3, 5, 7, 8 } : B{ }

 

정렬을 구현하기 위해 2개의 배열을 사용할 필요는 없다.

배열 내부에서 원소들을 교환하면 되는데 이렇게 입력 배열 이외의 추가 메모리를 요구하지 않는 정렬 방법을 inplace sorting 이라고 한다.

출처 - 교제 507p

원소의 수가 n개 이면 n-1번 반복해 주면 된다. 선택 정렬 알고리즘의 sudo code를 확인해보자.

selectionSort(A, n)

for i <- 0 to n-2 do
    least <- A[i], A[i+1], ... , A[n-1] 중에서 가장 작은 값의 인덱스;
    A[i]와 A[least]의 교환;
    i++;

 

코드는 다음과 같다.

void selectionSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int least = i;
        for (int j = i + 1; j < n; j++)
            if (A[j] < A[least])
                least = j;
        swap(A[i], A[least]);
    }
}

 

선택 정렬은 시간복잡도가 O(n^2)으로 비효율적인 알고리즘이며, 또한 안정성을 만족하지 않는다. 즉. 값이 같은 레코드가 있는 경우 정렬후 상대적인 위치가 변경될 수 있다.

 

삽입 정렬 (insertion sort)

삽입 정렬은 새로운 숫자를 받으면 이미 정렬된 숫자들의 배열의 옳바른 자리에 넣는 방법이다. 선택 정렬과 같이 추가적인 메모리를 사용하지 않고 input 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어서 사용하면 된다.

출처 - 교제 511p

삽입 정렬 알고리즘을 확인해 보자.

insertionSort(A, n)

for i <- 1 to n-1 do
    key <- A[i];
    j <- i-1;
    while j >= 0 and A[j] > key do
        A[j+1] <- A[j];
        j <- j-1;
    A[j+1] <- key

 

코드는 다음과 같다.

void insertionSort(int A[], int n) {
    for (int i = 1; i < n; i++) {
        int key = A[i];
        int j;
        for (j = i - 1; j >= 0 && A[j] > key; j--)
            A[j + 1] = A[j];
        A[j + 1] = key;
    }
}

 

 

버블 정렬 (bubble sort)

버블 정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환하는 방식이다. 이러한 교환은 리스트의 왼쪽에서 시작하여 오른쪽 끝까지 진행된다.

 

비교-교환이 1회 진행되면 가장 큰 레코드가 list의 오른쪽 끝으로 이동한다.

출처 - 교제 515p

list를 한번 정렬하면 오른쪽 끝에 가장 큰 레코드가 위치하고, 이후 오른쪽의 정렬된 부분과 정렬이 아직 안된 왼쪽으로 나뉘게 된다.

이러한 정렬 과정은 전체 list가 정렬될때까지 반복한다.

 

버블 정렬의 알고리즘을 확인해보자

BubbleSort(A, n)

for i <- n-1 to 1 do
    for j <- 0 to i-1 do
        j와 j+1번째의 요소가 크기순이 아니면 교환
        j++;
    i--;

 

이를 CPP코드로 구현하면 다음과 같다.

void bubbleSort(int A[], int num)
{
    for (int len = num - 1; len > 0; len--)
    {
        for (int i = 0; i < len; i++)
        {
            if (A[i] > A[i + 1])
                swap(A[i], A[i + 1]);
        }
    }
}

 

버블 정렬의 비교횟수는 최상, 평균, 최악의 경우 모두 O(n^2)으로 일정하다. 버블정렬은 효율적이지는 않다. 데이터가 어느정도 정렬되있는 경우에 효과적으로 사용할 수 있다.

 

셸 정렬 (shell sort)

셸 정렬은 Donald L. Shell이 제안한 방법으로 삽입 정렬이 어느정도 정렬된 배열에 대해서는 매우 빠르다는점에 착안했다.

 

삽입 정렬과 달리 셸 정렬은 전체 리스트를 한번에 정렬하지 않는다. 리스트를 일정한 기준으로 나누어 연속적이지 않은 여러개의 부분 리스트로 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다.

그 다음에 다시 더 작은 부분 리스트로 만들어 반복한다. 부분 리스트의 수가 1개일때까지 반복한다.

 

부분집합을 나누는 간격이 중요한데, 보통 전체 list 사이즈의 절반부터 시작한다. 만약 원소가 10개라면 간격은 5가 된다.

간격이 5인 부분 리스트가 만들어지면 정렬은 한후, 다시 간격을 절반으로 잡는다. 엄밀하게는 2.5이지만 3이 된다.

출처 - 518p

소스코드는 다음과 같다.

static void sortGapInsertion(int A[], int first, int last, int gap)
{
    int i, j, key;
    for (i = first + gap; i <= last; i += gap) {
        key = A[i];
        for (j = i - gap; j >= first && key < A[j]; j -= gap)
            A[j + gap] = A[j];
        A[j + gap] = key;
    }
}

void shellSort(int A[], int n)
{
    for (int gap = n / 2; gap > 0; gap /= 2) {
        printArray(A, n, "Shell....");
        if ((gap % 2) == 0) gap++;
        for (int i = 0; i < gap; i++)
            sortGapInsertion(A, i, n - 1, gap);
    }
}

 

셸 정렬은 2가지 장점이 있다. (출처 - 교제 521p 상단)

 

1) 연속적이지 않은 부분 파일에서 교환이 일어나면 더 큰 거리를 이동한다. 반면 삽입 정렬에서는 한번에 한 칸씩만 이동된다.

따라서 교환되는 원소들이 삽입 정렬보다 최종 위치에 가까울 확률이 높아진다.

 

2) 부분 list가 하나가 되면 셸 정렬은 전체 리스트를 정렬해야 한다. 셸 정렬은 전체 list를 정렬해야한다.

그러나 삽입 정렬이 거의 정렬된 리스트에 대해 효율적이니 이 과정도 빠르게 수행된다.

 

시간복잡도는 최악의 경우는 O(n^2) 이지만 평균적인경우 O(n^1.5)라고 알려져 있다.

 

합병 정렬 (merge sort)

합병 정렬은 하나의 list를 두개의 같은 크기로 나눈 후 각 리스트를 정렬후 두 list를 합하여 만든다. 이는 divide and conquer 기법에 바탕을 두고 있는데, 하나의 문제를 작은 2개의 문제로 분리하고 각각 을 해결한후, 결과를 모아 해결하는 전략이다. 분할정복은 대개 순환 호출을 이용한다.

 

합병정렬은 3가지 단계로 나누어진다.

1) Divide: 입력 배열을 같은 크기의 2개의 부분 배열로 나눈다.

2) Conquer: 부분 배열을 정렬한다. 부분배열의 크기가 충분히 작지 않으면 재귀를 이용하여 다시 분할 정복한다.

3) Combine: 정렬된 부분 배열들을 하나의 배열에 통합한다.

출처 - 교제 522p

각각의 부분배열은 어떻게 정렬할까? 이또한 순환을 이용하면된다.

27, 10, 12, 20을 다시 둘로 나누어 (27, 10), (12, 20)으로 만들고, 이를 또 분할하여 4개의 27, 10, 12, 20 으로 만든 후

2개의 리스트를 합병(merge) 할때 정렬이 된다.

합병 정렬 알고리즘

mergeSort(A, left, right)

if left < right
    mid = (left+right)/2;
    mergeSort(A, left, mid);
    mergeSort(A, mid+1, right);
    merge(A, left, mid, right);

 

merge 알고리즘

merge(A, left, mid, right)

b1 <- left;
e1 <- mid;
b2 <- mid+1;
e2 <- right;
sorted 배열을 생성;
index <- 0;
while b1 <= e1 and b2 <= e2 do
    if(A[b1] < A[b2])
        then
            sorted[index] <- A[b1];
            b1++;
            index++;
        else
            sorted[index] <- A[b2];
            b2++;
            index++;
요소가 남은 부분배열을 sorted로 복사;
sorted를 A로 복사한다.

 

이 알고리즘은 하나으 배열에 2개의 정렬된 부분리스트가 저장되있다고 가정한 것 이다.

 

소스코드는 다음과 같다.

static void merge(int A[], int left, int mid, int right)
{
    int i, j, k = left, l;
    static int sorted[max_size];

    for (i = left, j = mid + 1; i <= mid && j <= right; )
        sorted[k++] = (A[i] <= A[j]) ? A[i++] : A[j++];

    if (i > mid)
        for (l = j; l <= right; l++, k++)
            sorted[k] = A[l];
    else
        for (l = i; l <= mid; l++, k++)
            sorted[k] = A[l];

    for (l = left; l <= right; l++)
        A[l] = sorted[l];
}

void mergeSort(int A[], int left, int right)
{
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(A, left, mid);
        mergeSort(A, mid + 1, right);
        merge(A, left, mid, right);
    }
}

 

합병 정렬의 시간복잡도는 O(nlogn)이다.

 

합병정렬은 레코드들의 크기가 큰 경우 이동횟수가 많아 큰 시간적 낭비가발생하지만, 이를 포인터를 이용하여 극복하면 문제가 해결된다.

 

퀵 정렬 (quick sort)

퀵 정렬은 평균적으로 매우 빠른 속도를 자랑하는 정렬 방법이다. 퀵 정렬도 합병 정렬과 같이 divide and conquer 방식을 사용한다.

 

먼저 리스트 안에있는 한 요소를 pivot으로 선택한다. 보통 리스트의 첫 요소를 pivot으로 정한다. 이후 pivot보다 작은거는 왼쪽으로, 큰거는 오른쪽으로 옮긴다. 이 상태에서 pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬된다.

출처 - 교제 529p

이후 다시 순환 호출을 이용하여 부분리스트에서도 pivot을 선택하여 이를 기준으로 2개의 부분리스트로 나눈다.

이 과정을 부분리스트를 더이상 분할 할 수 없을때까지 반복한다.

void quickSort(int A[], int left, int right)
{
    if (left < right) { // 정렬 범위가 2개 이상인 경우
        int q = partition(A, left, right);
        quickSort(A, left, q - 1);
        quickSort(A, q + 1, right);
    }
}

 

퀵 정렬에서 가장 중요한 함수가 partition() 이다. 이 함수는 pivot을 기준으로 2개의 부분 리스트로 나눈다.

피벗보다 작은 데이터는 모두 왼쪽으로, 큰 데이터는 모두 오른쪽 부분 리스트로 옮겨진다.

 

리스트의 인덱스 변수 low는 왼쪽 부분 리스트를 만드는데 사용하고, high 는 오른쪽 부분 리스트를 만드는데 사용한다. low는 왼쪽에서부터 오른쪽으로 탐색해 가다가 pivot보다 큰 데이터를 찾으면 멈춘다. high는 오른쪽 끝에서부터 왼쪽으로 탐색해가다가 pivot보다 작은 데이터를 발견하면 멈춘다. 이후 low와 high의 데이터를 서로 교환한다. 이러한 탐색-교환 과정은 low와 high가 엇갈리지 않는 한 계속 반복한다. 알고리즘이 진행되면서 언젠가는 low와 high가 엇가릴는 시점이 오고 멈추게 된다. 이후 마지막으로 high가 가리키는 데이터와 pivot을 교환하면 된다.

 

출처 - 교제 531p

소스코드는 다음과 같다.

static int partition(int A[], int left, int right)
{
    int low = left;
    int high = right + 1;
    int pivot = A[left];
    do {
        do {
            low++;
        } while (low <= right && A[low] < pivot);
        do {
            high--;
        } while (high >= left && A[high] > pivot);
        if (low < high)
            swap(A[low], A[high]);
    } while (low < high);

    swap(A[left], A[high]);
    return high;
}

 

퀵 정렬의 시간 복잡도는 평균적으로 O(nlogn)으로 나타난다. 퀵 정렬은 속도가 빠르고 추가 메모리 공간을 필요로 하지 않는다는 장점이 있지만, 단점으로는 정렬된 리스트에 대해서는 수행 속도가 많이 느려진다는 단점이 있다. 이러한 불균형을 방지하기위해 pivot을 단순히 리스트의 첫 원소를 선택하는 것 이 아니라, 리스트 내의 중간값(median)을 이용하기도 한다. 일반적으로 리스트의 왼쪽, 오른쪽, 중간 3개의 평균을 이용한다.

 

힙 정렬 (heap sort)

정렬할 배열을 먼저 최소 힙으로 변환한 다음, 가장 작은 원소부터 차례대로 추출하여 정렬하는 방법을 heap sort 라고 한다. 힙 정렬의 시간 복잡도는 O(nlogn)이다

 

힙 정렬은 리스트 중 일부만 정렬할 필요가 있는경우에 매우 유용하다. n개의 레코드 중에서 작은 레코드 k개만 필요한 경우와 같이 일부분이 필요한 경우에 유용하다.

 

기수 정렬 (Radix sort)

기수 정렬은 입력 데이터에 대하여 어떠한 비교 연산도 실행하지 않고 데이터를 정렬할 수 있는 독특한 정렬 기법이다.

기수 정렬은 일반적으로 O(kn)의 시간 복잡도를 갖는데, k값이 대부분 4 이하다.

또한 기수 정렬은 추가적인 메모리를 필요로 하지만 이런 단점을 감안하더라도 다른 방식들보다 빠르기 때문에 인기있는 정렬 기법중 하나이다.

 

기수(radix)란 숫자의 자릿수 이다. 예를들어 71은 7과 1의 두개의 자릿수를 갖고있고 이것이 기수이다.

 

어떻게 비교를 하지 않고 정렬을 진행할 수 있을까?

십징수에서는 각 자릿수가 0에서 9까지의 범위를 갖는다는점에 착안하여 다음과 같이 10개의 bucket을 만들어 입력 데이터를 값에 따라 상자에 넣는다.

출처 - 교제 538p

이후 출력리스트를 만들때 순차적으로 bucket에서 읽어온다. 그러면 정렬된 리스트를 얻을 수 있다.

비교연산은 사용되지 않았다. 각 자릿수의 값에 따라 버킷에 넣고 빼는 동작을 했을뿐 이다.

 

한자리 숫자는 이해가 된다. 하지만 2자리 그 이상의 숫자들은 어떻게 처리해야 할까?

1의 자릿수와 10의 자릿수를 따로 따로 사용하여 정렬하는 방법이다. 이렇게 하면 10개의 버킷만으로도 2자리 정수를 정렬할 수 있다.

어떤 자리수를 먼저 사용해야 할까? 낮은 자릿수로 정렬한 다음 점점 높은 자릿수로 정렬해야 한다.

 

기수정렬 알고리즘

LSD(least significant digit)은 가장 낮은 자릿수 이고, MSD(most significant digit)은 가장 높은 자릿수 이다.

RadixSort(A, n)

for d <- LSD의 위치 to MSD의 위치 do
    d번째 자릿수에 따라 0부터 9까지 버킷에 집어넣는다.
    버킷에서 숫자들을 순차적으로 읽어 하나의 list로 합친다.
    d++;

 

10개의 버킷 각각에서는 먼저 들어간 숫자가 먼저 나와야 한다. 이는 queue를 이용하면 된다.

void radixSort(int list[], int n)
{
    queue<int> queue[buckets];
    int factor = 1;
    for (int d = 0; d < digits; d++) {
        for (int i = 0; i < n; i++) // 데이터를 자릿수에 따라 삽입
            queue[(list[i] / factor) % 10].push(list[i]); 

        for (int b = 0, i = 0; b < buckets; b++)
            while (!queue[b].empty()) {
                list[i++] = queue[b].front();
                queue[b].pop();
            }

        factor *= 10;

        printArray(list, n, "Radix....");
    }
}