[SCCC 스터디] 선택, 퀵, 머지, 카운팅 소트

이번엔 선택 정렬, 병합정렬(merge sort), 퀵 소트(quick sort), 카운팅 소트(counting sort)를 직접 구현해보았다.

1. 선택 정렬 -구현 난이도 : ●○○○○

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
vector<int> list;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int input;
        cin >> input;
        list.push_back(input);
    }
 
 
    for (int i = 0; i < n - 1; i++)
    {
        int mini = list[i];
        int index = i;
        for (int j = i + 1; j < n; j++)
        {
            if (mini > list[j])
            {
                mini = list[j];
                index = j;
            }
        }
        swap(list[i], list[index]);
    }
 
    for (int i = 0; i < n; i++)
    {
        cout << list[i] << '\n';
    }
 
    return 0;
}

2. 병합 정렬(merge sort) -구현 난이도 : ●●●○○

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
vector<int> list;
vector<int> save;
 
void merge(int left, int right)
{
    int mid = (left + right) / 2;
    int first = left, second = mid;
    int pointer = left;
 
    while (first < mid && second < right)
    {
        if (list[first] < list[second])
            save[pointer++] = list[first++];
        else
            save[pointer++] = list[second++];
    }
    if (first != mid)
        for (int i = first; i < mid; i++)
            save[pointer++] = list[i];
    else
        for (int i = second; i < right; i++)
            save[pointer++] = list[i];
 
    for (int i = left; i < right; i++)
        list[i] = save[i];
    return;
}
 
void mergesort(int left, int right)
{
    if (left >= right || abs(right - left) <= 1)return;
    int mid = (left + right) / 2;
 
    mergesort(left, mid);
    mergesort(mid, right);
    merge(left, right);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    save.resize(n);
    for (int i = 0; i < n; i++)
    {
        int input;
        cin >> input;
        list.push_back(input);
    }
    
    mergesort(0, n);
 
    for (int i = 0; i < n; i++)
    {
        cout << list[i] << '\n';
    }
 
    return 0;
}

3. 퀵 소트 -구현 난이도 : ●●◐○○

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
vector<int> list;
 
void parition(int left, int right, int &pivotpoint)
{
    int pivot = list[left];
 
    int pointer = left;
    for (int i = left + 1; i < right; i++)
        if (list[i] < pivot)
            swap(list[i], list[++pointer]);
    
    pivotpoint = pointer;
    swap(list[pivotpoint], list[left]);
}
 
void quicksort(int left, int right)
{
    int pivotpoint;
    if (right > left)
    {
        parition(left, right, pivotpoint);
        if (abs(left - pivotpoint) <= 50000)
        {
            sort(list.begin() + left, list.begin() + right);
        }
        else
        {
            quicksort(left, pivotpoint);
            quicksort(pivotpoint + 1, right);
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        int input;
        cin >> input;
        list.push_back(input);
    }
 
    quicksort(0, n);
    
    for (int i = 0; i < n; i++)
    {
        cout << list[i] << '\n';
    }
 
    return 0;
}

4. 카운팅 소트 -구현 난이도 : ○○○○○ (엄청 쉽다)

#include<iostream>
 
using namespace std;
 
int list[10001];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, input;
    cin >> n;
    while (n--)
    {
        cin >> input;
        list[input]++;
    }
 
    for (int i = 1; i <= 10000; i++)for (int j = 0; j < list[i]; j++)
    {
        cout << i << '\n';
    }
    return 0;
}