#1156 Pbinfo
Cerința
Se dau înălțimile a n copii, numerotați de la 1 la n, exprimate prin numere naturale. Afișați numerele de ordine ale copiilor în ordinea crescătoare a înălțimii lor.
Pentru sortare se va folosit metoda QuickSort sau MergeSort.
Date de intrare
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând, în ordine, înălțimile copiilor.
Date de ieșire
Programul va afișa pe ecran n numere naturale distincte cuprinse între 1 și n, separate prin exact un spațiu, reprezentând numerele de ordine ale copiilor în ordinea crescătoare a înălțimii.
Restricții și precizări
1 ≤ n ≤ 1000
înălțimile copiilor vor fi numere naturale distincte din intervalul [1 , 10000]
Exemplu
Intrare
7
8 20 16 14 10 4 12
Ieșire
6 1 5 7 4 3 2;
Trebuie folosita si Divide et Impera si quicksort o functie separata,nu tot in main
Răspunsuri la întrebare
Răspuns:
Explicație:
#include <iostream>
using namespace std;
int n;
struct elev
{
int inaltime, indice;
};
elev v[1005];
void sortare(elev *v, int st, int dr);
int main(){
cin>>n;
for(int i = 1; i <= n ; i++)
cin>>v[i].inaltime, v[i].indice = i;
sortare(v, 1, n);
for(int i = 1; i <= n ; i++)
cout<<v[i].indice<<" ";
return 0;
}
void sortare(elev v[], int st, int dr)
{
if(st < dr)
{
int i = st, j = dr, d = 0;
while( i < j)
{
if(v[i].inaltime > v[j].inaltime)
{
elev aux = v[i];
v[i] = v[j];
v[j] = aux;
if(d == 0)
d = 1;
else
d = 0;
}
if(d == 0)
j--;
else
i++;
}
int k = i;
sortare(v, st, k -1);
sortare (v, k+1, dr);
}
}