1083번: 소트

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

가능한 한 큰 수가 앞에 오도록 만든다.

시간복잡도는 테스트케이스마다 $O(n^2)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, s, a[50];
int main() {
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) scanf("%d", a + i);
        scanf("%d", &s);
        for (int i = 0; i < n; i++) {
            int p = max_element(a + i, a + min(s + i + 1, n)) - a;
            rotate(a + i, a + p, a + p + 1);
            s -= p - i;
        }
        for (int i = 0; i < n; i++) printf("%d ", a[i]);
        puts("");
    }
    return 0;
}