286
Cerința
Se dă un șir cu n
elemente, numere întregi. Folosind metoda QuickSort (Sortare Rapidă), ordonați crescător elementele acestui șir.
Date de intrare
Programul citește de la tastatură numărul n
, iar apoi cele n
elemente ale șirului.
Date de ieșire
Programul va afișa pe ecran elementele șirului sortat, separate prin exact un spațiu.
Restricții și precizări
1 ≤ n ≤ 100.000
- elementele șirului vor fi cuprinse între
-1.000.000.000
și1.000.000.000
Exemplu
Intrare
1210 0 -1 -3 1 -4 9 3 -1 -4 3 -4
Ieșire
-4 -4 -4 -3 -1 -1 0 1 3 3 9 10
#include <bits/stdc++.h> using namespace std; int n, a[100001]; void Quicksort(int st, int dr){ if(st < dr){ int mij = (st + dr) / 2; swap(a[st], a[mij]); int i = st, j = dr, d = 0; while(i < j){ if(a[i] > a[j]){ swap(a[i], a[j]); d = 1 - d; } i += d; j -= 1-d; } Quicksort(st, i - 1); Quicksort(i + 1, dr); } } int main(){ cin >> n; for(int i = 1; i <= n; ++i) cin >> a[i]; Quicksort(1, n); for(int i = 1; i <= n; ++i) cout << a[i] << ' '; return 0; }
Comentarii