IN C++ , Sortare 406
Fiecare locuitor al unui oraş a donat o sumă de bani pentru realizarea unui centru de excelenţă în informatică. Pentru a determina care este valoarea cea mai mare care s-a donat, primarul oraşului te-a angajat să creezi un program care să sorteze crescător toate valorile donate. Fiindcă nu işi permite să piardă timp, te-a rugat să faci un program care să execute sortarea într-un timp cât mai scurt posibil.
Date de intrare
Se citește de la tastatură un număr n, urmat de un șir de n numere naturale.
Date de ieșire
Programul va afișa pe ecran elementele șirulului sortat în ordine crescătoare.
Restricții și precizări
0 < n ≤ 100 000
elementele șirului sunt numere cuprinse intre 0 și 500, inclusiv.
Exemplu
Date de intrare ........ Date de ieșire
10
15 47 98 23 145 74 89 32 1 74 ..... 1 15 23 32 47 74 74 89 98 145
VA ROG SA EXPLICATI ! MULTUMESC
using namespace std;
int main() {
int n, v[501];
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i];
int x = v[i];
int p = i - 1;
while (p > 0 && v[p] > x)
v[p + 1] = v[p--];
v[p + 1] = x;
}
for (int i = 1; i <= n; i++)
cout << v[i] << ' ';
return 0;
}
Răspunsuri la întrebare
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;
}