[백준 - 2750] 수 정렬하기 - C++

분류: 정렬 /

 

문제

문제 링크

문제 설명

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

풀이

- STL sort

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    int arr[n];
    for(int &x:arr) cin >> x;
    sort(arr, arr + n);
    for(const int &x:arr) cout << x << '\n';
}

- Counting Sort

#include <iostream>
using namespace std;

bool numbers[2001];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for(int i=0; i<n; i++) {
        int num; cin >> num;
        numbers[num + 1000] = true;
    }
    for(int i=0, cnt=0; cnt != n && i<2001; i++) {
        if(numbers[i]) {
            cnt++;
            cout << i - 1000 << '\n';
        }
    }
}

- Merge Sort

#include <iostream>
using namespace std;

void merge(int arr[], int start, int end) {
    int tmp[end-start];
    int mid = (start + end) / 2;
    int left = start, right = mid;
    for(int i = 0; i < end-start; i++) {
        if(right == end) tmp[i] = arr[left++];
        else if(left == mid) tmp[i] = arr[right++];
        else if(arr[left] <= arr[right]) tmp[i] = arr[left++];
        else tmp[i] = arr[right++];
    }
    for(int i=start; i<end; i++) arr[i] = tmp[i-start];
}
void mergeSort(int arr[], int start, int end) {
    if(end - start <= 1) return;
    int mid = (start + end) / 2;
    mergeSort(arr, start, mid);
    mergeSort(arr, mid, end);
    merge(arr, start, end);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    int arr[n];
    for(int &x:arr) cin >> x;
    mergeSort(arr, 0, n);
    for(const int &x:arr) cout << x << '\n';
}

- Quick Sort

#include <iostream>
using namespace std;

void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}
void quickSort(int arr[], int start, int end) {
    if(end - start <= 1) return;
    int &pivot = arr[start];
    int p = start;
    for(int i = start+1; i < end; i++)
        if(arr[i] < pivot) 
            swap(arr[++p], arr[i]);
    swap(pivot, arr[p]);
    quickSort(arr, start, p);
    quickSort(arr, p+1, end);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    int arr[n];
    for(int &x:arr) cin >> x;
    quickSort(arr, 0, n);
    for(const int &x:arr) cout << x << '\n';
}

n의 최댓값이 1000이므로 최악의 경우에도 1000000으로 퀵소트로 해결 가능하다

 

#include <iostream>
using namespace std;

void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}
void quickSort(int arr[], int start, int end) {
    if(end - start <= 1) return;
    int &pivot = arr[start];
    int left = start + 1, right = end - 1;
    while(true) {
        while(left <= right and arr[left] <= pivot) left++;
        while(left <= right and arr[right] >= pivot) right--;
        if(left > right) break;
        swap(arr[left], arr[right]);
    }
    swap(pivot, arr[right]);
    quickSort(arr, start, right);
    quickSort(arr, right + 1, end);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    int arr[n];
    for(int &x:arr) cin >> x;
    quickSort(arr, 0, n);
    for(const int &x:arr) cout << x << '\n';
}