[C++ 응용] 퀵, 머지, 힙, 버블, 선택, 삽입 정렬 알고리즘 구현

* 알고리즘의 기본인 정렬 알고리즘들의 대표적인 케이스들을 직접 C++로 구현해보았다. C++을 이용해서 재귀적으로도 처리하기도 하고, O(nlogn)이나 O(n^2)에 대한 알고리즘 분석의 기본이 되므로 기본적으로 알고 있으면 유용하다.

 

* Quick Sort

: 퀵소트는 하나의 피봇이 있어서 피봇보다 작은 값들을 앞으로, 큰 값들을 뒤로 보낸 다음, 다시 나뉘어진 그룹을 정렬하는 top-down 식 정렬 알고리즘이다.

#include <iostream>

using namespace std;

void quickSort(int arr[], int size) { 
    int pivot = arr[0];
    int cursor = 0;

    for (int i = 1; i < size ; i++) {
        if (pivot > arr[i]) {
            cursor++;
            swap(arr[cursor], arr[i]);
        }
    }


    swap(arr[0], arr[cursor]);

    if (cursor > 0) {
        quickSort(arr, cursor);
    }

    if (cursor + 1 < size - 1) {
        quickSort(arr + cursor + 1, size - cursor - 1);
    }
}  

int main() {
    int arr[] = {9,8,7,4,2,6,1,3,5};
    int size = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, size);

    for(int i = 0 ; i < size ; i++) {
        cout << arr[i] << " ";
    }

    cout << endl;

    return 0;
}

* Heap sort

: 힙 소트는 max-heap을 이용해서 처음에 max-heap으로 O(nlogn)으로 전체를 max-heap으로 만든 다음, Max 값을 계속 추출 O(logn) 함으로써 max-heap이 최대 값을 뽑는데 최적화 되어있는 것을 이용한다.

#include <iostream>

using namespace std;


void heapify(int arr[], int size, int rootIndex) {
    int leftChildIndex = (rootIndex + 1) * 2 - 1;
    int rightChildIndex = (rootIndex + 1) * 2;
    int largest = rootIndex;

    if (leftChildIndex < size && arr[leftChildIndex] > arr[largest]) {
        largest = leftChildIndex;
    }
    if (rightChildIndex < size && arr[rightChildIndex] > arr[largest]) {
        largest = rightChildIndex;
    }

    if (largest != rootIndex) {
        swap(arr[rootIndex], arr[largest]);
        heapify(arr, size, largest);
    }
}

void heapSort(int arr[], int size) {
    for (int i = size / 2 - 1; i >= 0 ; i--) {
        heapify(arr, size, i);
    }
    for (int i = size - 1 ; i >= 0 ; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {4,5,1,6,8,9,3,10, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, size);

    for(int i = 0 ; i < size ; i++) {
        cout << arr[i] << " ";
    }

    

    return 0;
}

* Merge Sort

: 머지 정렬은 bottom-up으로 정렬 그룹이 2개 이하일때를 종료 조건으로 하고, 하위 그룹의 머지 정렬이 끝나면 상위 그룹에서 두 개의 그룹을 합치는 것으로 동작한다.

#include <iostream>

using namespace std;


void mergeSort(int arr[], int size) {
    if (size > 2) {
        mergeSort(arr, size / 2);
        mergeSort(arr + size / 2, size - size / 2);
        
        int leftCursor = 0;
        int rightCursor = size / 2;
        int buff[50];
        int buffCursor = 0;
        
    
        while (leftCursor < size / 2 && rightCursor < size) {
            if (arr[leftCursor] < arr[rightCursor]) {
                buff[buffCursor++] = arr[leftCursor++];
            } else {
                buff[buffCursor++] = arr[rightCursor++];
            }
        }
        for (int i = leftCursor ; i < size / 2 ; i++) {
            buff[buffCursor++] = arr[i];
        }
        for (int j = rightCursor ; j < size ; j++) {
            buff[buffCursor++] = arr[j];
        }

        memcpy(arr, buff, size * sizeof(int));

    } else {
        if (arr[0] > arr[1]) {
            swap(arr[0], arr[1]);
        }
    }
}

int main() {
    int arr[] = {9,8,7,4,2,6,1,3, 5};
    int size = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, size);

    for(int i = 0 ; i < size ; i++) {
        cout << arr[i] << " ";
    }

    cout << endl;

    return 0;
}

* Bubble Sort

: 버블소트는 항상 연달아 있는 2개의 값을 계속 비교해서 방울이 떠오르는 것과 유사하게 동작하는 정렬이다.

#include 

using namespace std;


void bubbleSort(int arr[], int size) {
    bool isSwap;
    do {
        isSwap = false;
        for (int i = 1 ; i < size ; i++) {
            if (arr[i - 1] > arr[i]) {
                swap(arr[i - 1] , arr[i]);
                isSwap = true;
            }
        }
    } while(isSwap);
}

int main() {
    int arr[] = {9,8,7,4,2,6,1,3, 5};
    int size = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, size);

    for(int i = 0 ; i < size ; i++) {
        cout << arr[i] << " ";
    }

    cout << endl;

    return 0;
}

* Selection Sort

: 하나의 값을 선택해서 그 값이 최소(최대) 값인지 구분하여 계속 최소 값을 선택해가면서 다른 값들과 비교하는 정렬 방법이다.

#include 

using namespace std;


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

int main() {
    int arr[] = {9,8,7,4,2,6,1,3, 5};
    int size = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, size);

    for(int i = 0 ; i < size ; i++) {
        cout << arr[i] << " ";
    }

    cout << endl;

    return 0;
}

* Insertion Sort

: 삽입 정렬은 항목을 점차적으로 정렬해나가면서 하나씩 항목을 추가해가면서 뒤에서부터 삽입 해서 정렬되는 위치까지 삽입시키는 알고리즘이다.

#include 

using namespace std;


void insertionSort(int arr[], int size) {
    for(int i = 0 ; i < size - 1 ; i++) {
        for (int j = i + 1 ; j >= 0 ; j--) {
            if(arr[j - 1] > arr[j]) {
                swap(arr[j - 1], arr[j]);
            } else {
                continue;
            }
        }
    }
}

int main() {
    int arr[] = {9,8,7,4,2,6,1,3, 5};
    int size = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, size);

    for(int i = 0 ; i < size ; i++) {
        cout << arr[i] << " ";
    }

    cout << endl;

    return 0;
}

: 다음에는 다시 기본 문법에 대해서 정리하고 데이터구조를 구현해보는 예를 적어볼 것이다.

끝.

* 다음편

2016/05/19 - [C++ 기본] 변수형과 기본 자료 구조(vector, map, set)