Informatică, întrebare adresată de mvrabie128, 8 ani în urmă

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


lucaciucandrei: iti trebuie neapart explicare pe problema?
lucaciucandrei: o alta sortare este aceasta, care e usor de retinut si se face din citire
lucaciucandrei: #include

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;
}
mvrabie128: Andrei , imi da zero puncte pe platforma !!! DE CE ?

Răspunsuri la întrebare

Răspuns de lucaciucandrei
6

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;

}


lucaciucandrei: iar aia da e gresita ca trebuia sa pun contidita ca daca v[i]!=0 sa afiseze pe i, dar m-am grabit
mvrabie128: SCRIE UN CODE BUN CAP CODA SI DAU CORANA !
lucaciucandrei: pai unde sa-l scriu?
iliketocode: Andrei, programelele tale sufera de buffer overflow. Mare atentie la cum declari si folosesti memoria.
lucaciucandrei: cum asa? :))
iliketocode: Nu ai fost suficient de atent. Bufferul tau nu intruneste conditia acestei probleme. [n <= 100000]. De altfel daca folosesti C++ te-as sfatui sa renunti sa mai scrii in stil C.
lucaciucandrei: iar eu iti garantez ca tu nu esti suficient de atent la enunt :)) also, pune mana pe C++! stima! ;)
iliketocode: Esti la inceput, este de inteles cand faci astfel de greseli. Nu sunt aici sa imi masor cunostintele cu voi ci sa va invat, iar daca asa raspunzi atunci cand ti se atrage atentia unde ai gresit consider ca nu vei avea viitor prea stralucit.
mvrabie128: ti-am dat coroana aici ? mai revin cu probleme ! MULTUMESC !
lucaciucandrei: ms da mi-ai dat daca poti si la celelalte ar fi supr
Alte întrebări interesante