in cazul de fata problema ta nici nu necesita o sortare deoarece elementele sunt in plaja de valori 0, 500 rezulta ca putem folosi un vector de aparitii de 500 componente si pe masura ce citim elementele, le vom contoriza de cate ori apar in citire in vectorul v, pe pozitia x, x fiind numarul citit curent, prin instructiunea v[x]++, astfel stocam si de cate ori apare un element si le avem puse si in ordine deoarece asa se parcurg indicii unui vector :))
complexitatea in timp este liniara O(n)
#include<iostream>
using namespace std;
int main() {
int n, v[501], x;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x;
v[x]++;
}
for (int i = 1; i <= n; i++)
cout << v[i] << ' '
return 0;
}
In cazul general, cea mai eficienta sortare CARE SE PREDA din pdv timp, in general, este quicksort, dar este o metoda destul de greutza de invatat pentru majoritatea elevilor, totusi o voi arata mai jos
#include<iostream>
using namespace std;
int partitionare(int st, int dr, int x[]) {
int aux, i = st, j = dr, di = 0, dj = 1;
while (i < j) {
if (x[i] > x[j]) {
aux = x[i];
x[i] = x[j];
x[j] = aux;
aux = di;
di = dj;
dj = aux;
}
i = i + di;
j = j - dj;
}
return j;
}
void quick(int st, int dr, int x[]) {
int p;
if (st < dr) {
p = partitionare(st, dr, x);
quick(st, p - 1, x);
quick(p + 1, dr, x);
}
}
int main() {
int n, v[501], x;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> v[i];
quick(1, n, v);
for (int i = 1; i <= n; i++)
cout << v[i] << ' ';
return 0;
}