[백준 2750번] 수 정렬하기

문제 링크: 2750번 수 정렬하기

https://www.acmicpc.net/problem/2750

 

O(n^2) 알고리즘으로 풀린다고 하니,

정렬에서 설명하지 않았고 구현이 간단한 selection sort를 사용한다.

 

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

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

bool compare(int a, int b) {
// 왼쪽이 더 크면 true, 그렇지 않으면 false
    if (a>b) return true;
    else return false;
}

void selectionSort(vector<int> &arr) {
// 바깥쪽 for문을 돌 때마다 arr[i]가 가장 작은 수가 된다.
    int n = arr.size();
    for (int i=0; i<n-1; i++) {
        for (int j=i+1; j<n; j++) {
            if (compare(arr[i], arr[j])) {
                swap(&(arr[i]), &(arr[j]));
            }
        }
    }
}

int main(void) {
    // create arr
    int n; cin >> n;
    
    vector<int> arr;
    for (int i=0; i<n; i++) {
        int t; cin >> t;
        arr.push_back(t);
    }
    
    // sort arr
    selectionSort(arr);
    
    // print arr
    for (int i=0; i<arr.size(); i++) {
        cout << arr[i] << '\n';
    }
    
    return 0;
}