[C++] 정렬 (Sorting)

느리면 O(N^2), 빠르면 O(NlogN) 의 시간복잡도를 만족하는 기본적인 정렬 알고리즘을 구현해두었다. 주기적으로 들어와서 복습하자!

---

목표

• 시간복잡도를 비교해보며 각종 정렬 알고리즘의 효율성 및 특징을 학습한다.

---

Selection Sort

• 선택정렬은 가장 작은 수를 선택하여 가장 뒷쪽으로 보낸다.
• O(N^2) 을 만족하는 정렬 알고리즘 중에서는 느린 축에 속한다.

Code

void selection_sort(vi &array) {
    for (int i=0; i<array.size(); i++) {
        int min_index = i;
        for (int j=i+1; j<array.size(); j++) {
            if (array[min_index] > array[j]) {
                min_index = j;
            }
        }
        swap(array[i], array[min_index]);
    }
}

int main()
{
    vi array = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    selection_sort(array);  // O(N^2), [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    return 0;
}

---

Bubble Sort

• 인접한 값과 비교하여 더 작은 값을 앞으로 보낸다.
• 시간복잡도 O(N^2) 을 따른다.
• 선택 정렬과 비교해보았을 때 swap 연산을 더 많이 사용하고 있기에 상대적으로 더 비효율적이다.
• 할당 연산은 메모리 -> 레지스터, 누적, 레지스터 -> 메모리를 합쳐서 구현하기 때문에 연산량이 더 많다.

Code

void burble_sort(vi &array) {
    for (int i=0; i<array.size(); i++) {
        for (int j=0; j<array.size()-1-i; j++) {
            if (array[j] > array[j+1]) {
                swap(array[j], array[j+1]);
            }
        }
    }
}

int main()
{
    vi array = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    burble_sort(array);     // O(N^2), [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    return 0;
}

---

Insertion Sort

• 정렬된 부분과 정렬해야할 부분으로 나눌 때 정렬할 카드를 정렬된 부분에 적정 위치에 삽입한다.
• 데이터가 거의 정렬되어 있는 경우 가장 효율적인 방법이다.

Code

void insertion_sort(vi &array) {
    for (int i=0; i<array.size(); i++) {
        for (int j=i; j>0; j--) {
            if (array[j-1] > array[j]) {
                swap(array[j], array[j-1]);
            }
        }
    }
}

int main()
{
    vi array = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    insertion_sort(array);  // O(N^2), [1, 2, 3, 4, 5, 6, 7, 8, 9]
    return 0;
}

---

Quick Sort

• 특정 기준값으로 큰수와 작은수를 나눈 뒤에 정렬 한다.
• 퀵정렬의 구현에는 분할정복 기법이 숨어있다.
• 평균 O(NlogN) 을 만족하며 최악의 경우 O(N^2) 을 만족할 수 있다.
• 최악은 데이터가 거의 정렬되어 있을 경우이다.
• 데이터 특성에 알맞게 정렬 알고리즘 선택 필요함.

Figure: Quick sort Implement

Code

void quick_sort(vi &array, int start, int end) {
    if (start >= end) return;

    int pivot = start;
    int i = pivot+1; int j = end;

    while (i <= j) {
        while (i <= end && array[pivot] >= array[i]) i++;
        while (j > start && array[pivot] <= array[j]) j--;
        int idx = (i > j)? pivot:i;
        swap(array[idx], array[j]);
    }

    quick_sort(array, start, j-1);
    quick_sort(array, j+1, end);
}

void quick_sort(vi array) {
    quick_sort(array, 0, array.size()-1);
    to_string(array);
}

int main()
{
    vi array = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    quick_sort(array);      // AVG: O(NlogN) Worst Case: O(N^2) (sorted array) 
    return 0;
}

---

Merge Sort

• 작은 단위로 분할하여 들어갔다가 정렬하면서 나온다.
• 병합 정렬의 구현에는 재귀함수를 활용한 분할 정복 기법이 숨어있다.
• 전역변수로 설정된 예비 sorted 배열이 필요하다.
• 평균 O(NlogN) 을 만족하지만 메모리 공간을 비효율적으로 사용한다.

Code

void merge(vi &array, vi &sorted, int start, int mid, int end) {
    int i = start; int j = mid+1; int k = start;
    while (i<=mid && j<=end) {
        sorted[k++] = (array[i] <= array[j])? array[i++]:array[j++];
    }
    
    int index = (i>mid)? j:i;
    for (int m=index; m<=end; m++) {
        sorted[k++] = array[m];
    }
    for (int m=start; m<=end; m++) {
        array[m] = sorted[m];
    }
}

void merge_sort(vi &array, vi &sorted, int start, int end) {
    if (start >= end) return;
    
    int mid = (start + end) / 2;
    merge_sort(array, sorted, start, mid);
    merge_sort(array, sorted, mid+1, end);
    merge(array, sorted, start, mid, end);
}

void merge_sort(vi array) {
    vi sorted(array.size(), 0);
    merge_sort(array, sorted, 0, array.size()-1);
}

int main()
{
    vi array = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    merge_sort(array);      // AVG: O(NlogN) Worst Case: Time Complexity O(NlogN)
    return 0;		    // But large memory use
}

Heap Sort

• Binary Tree (이진 트리): 모든 노드의 자식 노드가 2개 이하인 구조
• Complete Binary Tree (완전 이진 트리): 데이터가 Root 부터 시작해서 자식노드에 왼쪽에서 오른쪽 순서대로 채워지는 이진트리구조

• Heap: 최소값이나 최댓값을 빠르게 찾아내기 위해 사용되는 완전이진트리를 기반으로 하는 트리구조
  1. Max Heap: 부모노드 > 자식노드 관계를 만족한다
  2. Min Heap: 부모노드 < 자식노드 관계를 만족한다
• Heapify 힙 생성 알고리즘을 통하여 Heap Sort 를 구현할 수 있다.

Code

void heap_sort(vi array) {
    const int SIZE = array.size();
    for (int i=1; i<SIZE; i++) {
        int ptr = i;
        while (ptr != 0) {
            int root = (ptr-1) / 2;
            if (array[root] < array[ptr]) {
                swap(array[ptr], array[root]);
            }
            ptr = root;
        }
    }

    for (int i=SIZE-1; i>=0; i--) {
        swap(array[0], array[i]);
        int root = 0; int c = 1;
        while (c < i) {
            c = 2 * root + 1;
            if (c < i - 1 && array[c] < array[c+1]) {
                c++;
            }
            if (c < i && array[root] < array[c]) {
                swap(array[root], array[c]);
            }
            root = c;
        }
    }
}

int main()
{
    vi array = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    heap_sort(array);       // AVG: O(NlogN)
    return 0;
}

Counting Sort

• 작은 범위에 대해서 값의 개수를 세어 순차적으로 출력한다
• 범위 만큼 배열을 생성한 뒤에 배열값이 존재하는 만큼 해당 인덱스를 출력하면 된다.
• 시간복잡도 O(N) 을 만족하기 때문에 O(NlogN) 이 안먹히면 한번쯤 생각해볼만하다.