[algorithm] 정렬

선택 정렬 (Selection Sort)

선택 정렬은 가장 작은 값을 찾아서 앞쪽의 값과 변경하면서 정렬하는 알고리즘이다.
시간복잡도 : $O({n}^2)$

#include <iostream>
#include <vector>
using namespace std;

void selection_sort(vector<int> &v) {
    int sz = v.size();

    int minIdx;
    for (int i = 0; i < sz - 1; i++) {
        minIdx = i;
        for (int j = i + 1; j < sz; j++) {
            if (v[minIdx] > v[j]) minIdx = j;
        }
        if (i != minIdx) swap(v[i], v[minIdx]);
    }
}

int main() {
    vector<int> v{ 5, 4, 3, 8, 9, 6, 7, 1, 10, 2 };

    selection_sort(v);
    for (auto& e : v) cout << e << "\t";
    cout << endl;

    return 0;
}

삽입 정렬 (Insertion Sort)

삽입 정렬은 두번째 값부터 순회하면서 적절한 위치(이전 값보다 작아지는 곳)에 삽입하는 알고리즘이다.
시간복잡도 : $O({n}^2)$

#include <iostream>
#include <vector>
using namespace std;

void insertion_sort(vector<int>& v) {
    int sz = v.size();

    for (int i = 1; i < sz; i++) {
        int key = v[i];
        for (int j = i - 1; j >= 0 && v[j] > key; j--) {
            swap(v[j], v[j + 1]);
        }
    }
}

int main() {
    vector<int> v{ 5, 4, 3, 8, 9, 6, 7, 1, 10, 2 };

    insertion_sort(v);
    for (auto& e : v) cout << e << "\t";
    cout << endl;

    return 0;
}

버블 정렬 (Bubble Sort)

버블 정렬은 서로 인접한 두 원소를 비교하면서 정렬해나가는 알고리즘이다.
시간복잡도 : $O({n}^2)$

#include <iostream>
#include <vector>
using namespace std;

void bubble_sort(vector<int>& v) {
    int sz = v.size();

    for (int i = sz - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (v[j + 1] < v[j]) swap(v[j], v[j + 1]);
        }
    }
}

int main() {
    vector<int> v{ 5, 4, 3, 8, 9, 6, 7, 1, 10, 2 };

    bubble_sort(v);
    for (auto& e : v) cout << e << "\t";
    cout << endl;

    return 0;
}

합병 정렬 (Merge Sort)

합병 정렬은 두 개의 균등한 크기로 분할하여 부분 리스트를 정렬한 다음 두 개의 정렬된 부분 리스트를 합병하여 정렬하는 알고리즘이다.
시간복잡도 : $O(nlog_{2}n)$

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& v, int left, int mid, int right) {
    vector<int> tmp(v);
    int l = left, r = mid + 1, idx = left;

    while (l <= mid && r <= right) {
        if (v[l] < v[r]) tmp[idx++] = v[l++];
        else tmp[idx++] = v[r++];
    }

    if (l > mid) copy(v.begin() + r, v.begin() + right + 1, tmp.begin() + idx);
    else copy(v.begin() + l, v.begin() + mid + 1, tmp.begin() + idx);

    copy(tmp.begin() + left, tmp.begin() + right + 1, v.begin() + left);

}

void merge_sort(vector<int>& v, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        merge_sort(v, left, mid);
        merge_sort(v, mid + 1, right);
        merge(v, left, mid, right);
    }
}

int main() {
    vector<int> v{ 5, 4, 3, 8, 9, 6, 7, 1, 10, 2 };

    merge_sort(v, 0, v.size() - 1);
    for (auto& e : v) cout << e << "\t";
    cout << endl;

    return 0;
}

쉘 정렬 (Shell Sort)

쉘 정렬은 연속적이지 않은 여러 개의 부분 리스트로 나눈 후 각 부분 리스트에 대해 삽입 정렬을 수행한 후 전체 리스트에 대해 삽입 정렬을 수행하는 알고리즘이다.
시간복잡도 : $O(n^{1.5})$

# 추후 기술

퀵 정렬 (Quick Sort)

퀵 정렬은 pivot을 기준으로 비균등하게 분할하여 정렬하는 알고리즘이다.
시간복잡도 : $O(nlog_{2}n)$

#include <iostream>
#include <vector>
using namespace std;

void quick_sort(vector<int>& v, int left, int right) {
    if (left >= right) return;

    int i = left, j = right;
    int pivot = v[(left+right)/2];
    while (i < j) {
        while (v[i] < pivot) i++;
        while (v[j] > pivot) j--;
        if (i < j) swap(v[i], v[j]);
    }

    quick_sort(v, left, i - 1);
    quick_sort(v, i + 1, right);
}

int main() {
    vector<int> v{ 5, 4, 3, 8, 9, 6, 7, 1, 10, 2 };

    quick_sort(v, 0, v.size() - 1);
    for (auto& e : v) cout << e << "\t";
    cout << endl;

    return 0;
}

힙 정렬 (Heap Sort)

힙 정렬은 최대 힙 트리 또는 최소 힙 트리를 이용하여 정렬하는 알고리즘이다.
시간복잡도 : $O(nlog_{2}n)$

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void heap_sort(vector<int>& v) {
    priority_queue<int, vector<int>, greater<int>> pq;
    int i = 0;

    for (auto& e : v) pq.push(e);

    while (!pq.empty()) {
        v[i++] = pq.top();
        pq.pop();
    }
}

int main() {
    vector<int> v{ 5, 4, 3, 8, 9, 6, 7, 1, 10, 2 };

    heap_sort(v);
    for (auto& e : v) cout << e << "\t";
    cout << endl;

    return 0;
}

위상 정렬 (Topological Sort)

# 추후 기술