sorting algorithm(basic)

기본적인 sorting 알고리즘을 구현해 봤습니다. 설명은 링크를 따라가시면 굉장히 잘 되어있습니다.

백준 수 정렬하기 문제를 여러가지 방식으로 풀어보면서 연습을 해봤습니다. 아래 코드는 모두 AC 받은 코드들입니다.

코드는 C++로 되어 있구요. 나중에 혹시 면접 때 사용할 것을 생각하여 최대한 깔끔하게 작성해봤습니다.

bucket sort / counting sort / radix sort 에 대해서는 sorting algorithm(advanced)에 작성하겠습니다.

아래 에니메이션은 각 algorithm이 어떻게 작동하는지 쉽게 알 수 있어서 공유해봅니다.

[출처 : https://medium.com/@kamyarg/comparison-sorting-algorithms-and-mystery-of-nlogn-complexity-d7e80c34876 ]

1. QUICK SORT

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>

using namespace std;
 
vector<int> arr;
 
void qsort(int l, int r) {
    if (l >= r) return;
    
    int pivot = arr[l];
    int l_idx = l, r_idx = r;
 
    while (1) {
        while (l_idx < r_idx && pivot <= arr[r_idx]) r_idx -= 1;
        while (l_idx < r_idx && arr[l_idx] <= pivot) l_idx += 1;
        if (l_idx == r_idx) break;
        swap(arr[l_idx], arr[r_idx]);
    }
    
    swap(arr[l], arr[l_idx]);
 
    qsort(l, l_idx - 1);
    qsort(l_idx + 1, r);
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
    cin >> n;
    int a;
    for (int i = 0; i < n; i++) {
        cin >> a;
        arr.push_back(a);
    }
 
    qsort(0, n - 1);
    for (int i : arr) 
        cout << i << endl;
    
    return 0;
 
}

- 시간 복잡도 : O(NlogN) / O(N^2)

- 공간 복잡도 : O(logN) / O(N)

참고 사이트)

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

2. MERGE SORT

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
 
using namespace std;
 
vector<int> arr;
 
vector<int> merge_sort(int l, int r) {
    if (l == r) {
        vector<int> ret(1,arr[l]);
        return ret;
    }
 
    int m = (l + r) >> 1;
    vector<int> left = merge_sort(l, m);
    vector<int> right = merge_sort(m + 1, r);
    vector<int> total(left.size() + right.size());
    int l_idx = 0, r_idx = 0, t_idx = 0;
    while (l_idx < left.size() && r_idx < right.size()) {
        if (left[l_idx] > right[r_idx]) total[t_idx++] = right[r_idx++];
        else total[t_idx++] = left[l_idx++];
    }
 
    while (l_idx < left.size()) 
        total[t_idx++] = left[l_idx++];
    while (r_idx < right.size())
        total[t_idx++] = right[r_idx++];
 
    return total;
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
    cin >> n;
    int temp;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        arr.push_back(temp);
    }
 
    vector<int> ans = merge_sort(0, arr.size()-1);
    for (int i : ans) {
        cout << i << endl;
    }
 
    return 0;
 
}

- 시간 복잡도 : O(NlogN)

- 공간 복잡도 : O(N)

참고 사이트)

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

3. SELECTION SORT

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int arr[1001];
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    for (int j = n - 1; j > 0; j--) {
        int idx = 0;
        for (int i = 0; i <= j; i++) {
            if (arr[idx] < arr[i]) idx = i;
        }
        swap(arr[idx], arr[j]);
    }
 
    for (int i = 0; i < n; i++)
        cout << arr[i] << endl;
 
    return 0;
 
}

-시간 복잡도 : O(N^2)

-공간 복잡도 : O(N)

참고 사이트)

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

4. BUBBLE SORT

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
 
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int arr[1001];
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
        }
    }
 
    for (int i = 0; i < n; i++)
        cout << arr[i] << endl;
 
 
    return 0;
 
}

-시간 복잡도 : O(N^2)

-공간 복잡도 : O(N)

참고 사이트)

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

[출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html ]