Question

Cerința
Se dă un vector cu n elemente, numere naturale și un număr k. Ordonați crescător primele k elemente ale vectorului și descrescător ultimele n-k elemente.

Pentru sortare se va folosit metoda QuickSort

Date de intrare
Programul citește de la tastatură numerele n și k, iar apoi n numere naturale, reprezentând elementele vectorului.

Date de ieșire
Programul va afișa pe ecran elementele vectorului, separate prin exact un spațiu, după efectuarea operațiilor cerute.

Restricții și precizări
1 ≤ k < n ≤ 200 000
cele n numere citite vor fi mai mici decât 1 000 000 000



Exemplu
Intrare

7 3
13 1 10 15 3 7 11
Ieșire

1 10 13 15 11 7 3

Answer 1

#include <iostream>
using namespace std;

int n , v[200005] , k;

void QuickSort(int st, int dr, int semn)
{
if(st < dr)
{
//determinam pivotul
int m = (st + dr) / 2;
int aux = v[st];
v[st] = v[m];
v[m] = aux;
int i = st , j = dr, d = 0;
while(i < j)
{
if(semn * v[i] > semn * v[j])
{
aux = v[i]; 
v[i] = v[j];
v[j] = aux;
d = 1 - d;
}
i += d;
j -= 1 - d;
}
QuickSort(st , i - 1, semn);
QuickSort(i + 1 , dr , semn);
}
}

int main(){
cin >> n >> k;
for(int i = 1 ; i <= n ; i ++)
cin >> v[i];
QuickSort(1 , k , 1);
QuickSort(k+1, n , -1);
for(int i = 1 ; i <= n ; i ++)
cout << v[i] << " ";
return 0;
}