Metoda Bucket Sort constă în distribuirea elementelor în mai multe grupe, numite “bucket-uri”. Apoi fiecare bucket este sortat individual folosind un algoritm de sortare oarecare.

Cerința

Se dă un şir cu n numere naturale ce trebuie sortat în funcţie de d. Dacă d este 1, şirul se va sorta descrescător, iar dacă este 0, se va sorta crescător.

Date de intrare

Fișierul de intrare bucketsort.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații, iar pe a treia linie se va afla d.

Date de ieșire

Fișierul de ieșire bucketsort.out va conține pe prima linie şirul sortat în funcţie de d.

Restricții și precizări

• n ≤ 10.000
• toate numerele ≤ 100.000.000
• d=0 pentru 50% din teste
• d=1 pentru 50% din teste

Exemplu 1:

bucketsort.in

5
10 90 5 6 101
0

bucketsort.out

5 6 10 90 101 

Explicație

Deoarece d este 0, şirul se sortează crescător

Exemplu 2:

bucketsort.in

5
10 90 5 6 101
1

bucketsort.out

101 90 10 6 5 

Explicație

Deoarece d este 1, şirul se sortează descrescător

#include <bits/stdc++.h>

using namespace std;

ifstream cin("bucketsort.in");
ofstream cout("bucketsort.out");

int a[10001];

int main()
{
    int n;
    cin >> n;
    for(int i = 0 ; i < n ; ++i)
        cin >> a[i];
    int d;
    cin >> d;
    sort(a , a + n);
    if(d==1)
        for(int i = n-1 ; i >= 0 ; --i)
            cout << a[i] << ' ';
    else
        for(int i = 0 ; i < n ; ++i)
            cout << a[i] << ' ';
    return 0;
}