Sortarea din perspectiva ingineriei software
Last Updated: Dec 18 2017 00:51, Started by
dani.user
, Dec 16 2017 15:20
·
0
#1
Posted 16 December 2017 - 15:20
La inceput, elevii/studentii invata cum sa sorteze un vector de intregi folosind un algoritm banal. Toate bune pana aici. Mai departe invata algoritmi tot mai complecsi, dar mai rapizi de sortare. Utili si acestia.
Apoi insa apare un vid, lipseste cel mai important lucru din punct de vedere al practicii: cum sortam structuri mai complexe, eventual chiar dupa multiple criterii? Pasii de mai jos arata cum se poate adapta o functie banala de sortare pentru a face fata acestor nevoi practice. Ea ajunge sa semene foarte mult cu std::sort, functia oferita de standardul C++. Cod initial #include <algorithm> void sorteaza(int valori[], int numarValori) { bool efectuatInterschimbare; do { efectuatInterschimbare = false; for (int i = 1; i < numarValori; ++i) { if (valori[i] < valori[i - 1]) { std::swap(valori[i], valori[i - 1]); efectuatInterschimbare = true; } } } while (efectuatInterschimbare); } int main() { int valori[] = { 1, 3, 5, 7, 2, 4, 6 }; sorteaza(valori, 7); } Pas 1 – Numarul de valori nu poate fi negativ, deci folosim un tip unsigned #include <algorithm> void sorteaza(int valori[], unsigned int numarValori) { bool efectuatInterschimbare; do { efectuatInterschimbare = false; for (unsigned int i = 1; i < numarValori; ++i) { if (valori[i] < valori[i - 1]) { std::swap(valori[i], valori[i - 1]); efectuatInterschimbare = true; } } } while (efectuatInterschimbare); } int main() { int valori[] = { 1, 3, 5, 7, 2, 4, 6 }; sorteaza(valori, 7); } Pas 2 – Poate nu dorim sa sortam intreg vectorul ci doar o parte a sa, asa ca il transmitem ca pointer #include <algorithm> void sorteaza(int* valori, unsigned int numarValori) { bool efectuatInterschimbare; do { efectuatInterschimbare = false; for (unsigned int i = 1; i < numarValori; ++i) { if (valori[i] < valori[i - 1]) { std::swap(valori[i], valori[i - 1]); efectuatInterschimbare = true; } } } while (efectuatInterschimbare); } int main() { int valori[] = { 1, 3, 5, 7, 2, 4, 6 }; //sorteaza(valori, 7); sorteaza(valori + 2, 4); //sortam doar 5, 7, 2, 4 } Pas 3 – Vrem sa sortam alte tipuri de date, nu doar valori intregi, asa ca introducem templates #include <algorithm> template<typename T> void sorteaza(T* valori, unsigned int numarValori) { bool efectuatInterschimbare; do { efectuatInterschimbare = false; for (unsigned int i = 1; i < numarValori; ++i) { if (valori[i] < valori[i - 1]) { std::swap(valori[i], valori[i - 1]); efectuatInterschimbare = true; } } } while (efectuatInterschimbare); } int main() { int valori[] = { 1, 3, 5, 7, 2, 4, 6 }; sorteaza(valori, 7); double alteValori[] = { 2.5, 3.1, 1.6 }; sorteaza(alteValori, 3); } Pas 4 – Vrem sa sortam un vector compus din structuri, invatam compilatorul ce inseamna < in cazul structurilor #include <algorithm> struct Elev { int varsta; double medieLimbaRomana; bool operator<(const Elev& altElev) const { return varsta < altElev.varsta; //comparam doar varsta celor doi elevi } }; template<typename T> void sorteaza(T* valori, unsigned int numarValori) { bool efectuatInterschimbare; do { efectuatInterschimbare = false; for (unsigned int i = 1; i < numarValori; ++i) { if (valori[i] < valori[i - 1]) { std::swap(valori[i], valori[i - 1]); efectuatInterschimbare = true; } } } while (efectuatInterschimbare); } int main() { Elev elevi[] = { { 15, 8.5 }, { 18, 10 }, { 17, 7.6 }, { 17, 4.5 } }; sorteaza(elevi, 4); //sortam elevii crescator dupa varsta } Pas 5 – Dorim sa putem sorta si in alt mod (elevi dupa medie de exemplu) sau in alta ordine (descrescator) asa ca extragem comparatia separat Codul de mai sus functioneaza atunci cand dorim sortarea crescatoare a elevilor dupa varsta, dar are un mare neajuns cand dorim sa ii sortam dupa un alt criteriu: operator< nu poate fi definit in mai multe moduri in acelasi timp. Drept urmare, trebuie gasit un mod de a transmite la fiecare sortare cum dorim sa comparam structurile.z #include <algorithm> struct Elev { int varsta; double medieLimbaRomana; }; bool comparaEleviDupaVarstaCrescator(const Elev& elev1, const Elev& elev2) { return elev1.varsta < elev2.varsta; } bool comparaEleviDupaMedieLimbaRomanaDescrescator(const Elev& elev1, const Elev& elev2) { return elev1.medieLimbaRomana > elev2.medieLimbaRomana; } template<typename T, typename FunctieComparareMaiMic> void sorteaza(T* valori, unsigned int numarValori, FunctieComparareMaiMic comparareMaiMic) { bool efectuatInterschimbare; do { efectuatInterschimbare = false; for (unsigned int i = 1; i < numarValori; ++i) { if (comparareMaiMic(valori[i], valori[i - 1])) { std::swap(valori[i], valori[i - 1]); efectuatInterschimbare = true; } } } while (efectuatInterschimbare); } int main() { Elev elevi[] = { { 15, 8.5 }, { 18, 10 }, { 17, 7.6 }, { 17, 4.5 } }; sorteaza(elevi, 4, comparaEleviDupaVarstaCrescator); //sortam elevii crescator dupa varsta sorteaza(elevi, 4, comparaEleviDupaMedieLimbaRomanaDescrescator); //sortam elevii descrescator dupa medie limba romana } Pas 6 – Dorim sa putem sorta si alte structuri de date, de exemplu std::vector asa ca solicitam iteratori #include <algorithm> #include <iterator> #include <vector> struct Elev { int varsta; double medieLimbaRomana; }; bool comparaEleviDupaVarstaCrescator(const Elev& elev1, const Elev& elev2) { return elev1.varsta < elev2.varsta; } bool comparaEleviDupaMedieLimbaRomanaDescrescator(const Elev& elev1, const Elev& elev2) { return elev1.medieLimbaRomana > elev2.medieLimbaRomana; } template<typename Iterator, typename FunctieComparareMaiMic> void sorteaza(Iterator delaInclusiv, Iterator panaLaExclusiv, FunctieComparareMaiMic comparareMaiMic) { bool efectuatInterschimbare; do { efectuatInterschimbare = false; Iterator curent = delaInclusiv; Iterator urmator = curent; ++urmator; for (; urmator < panaLaExclusiv; ++curent, ++urmator) { if (comparareMaiMic(*urmator, *curent)) { std::swap(*curent, *urmator); efectuatInterschimbare = true; } } } while (efectuatInterschimbare); } int main() { Elev elevi[] = { { 15, 8.5 }, { 18, 10 }, { 17, 7.6 }, { 17, 4.5 } }; sorteaza(std::begin(elevi), std::end(elevi), comparaEleviDupaVarstaCrescator); std::vector<Elev> altiElevi = { { 15, 8.5 }, { 18, 10 }, { 17, 7.6 }, { 17, 4.5 } }; sorteaza(std::begin(altiElevi), std::end(altiElevi), comparaEleviDupaMedieLimbaRomanaDescrescator); } Tema de casa
|
#2
Posted 16 December 2017 - 15:53
Programatorii de succes trebuie sa stie algoritmi din astia in C++ ?
|
#4
Posted 16 December 2017 - 22:59
Tot nu ai plecat ma? Ti-e rau de viata de stai si pierzi vremea pe forum-uri in loc sa pui osu' la treaba?
|
#5
Posted 17 December 2017 - 05:35
dani.user, on 16 decembrie 2017 - 15:20, said:
La inceput, elevii/studentii invata cum sa sorteze un vector de intregi folosind un algoritm banal. Toate bune pana aici. Mai departe invata algoritmi tot mai complecsi, dar mai rapizi de sortare. Utili si acestia. Apoi insa apare un vid, lipseste cel mai important lucru din punct de vedere al practicii: cum sortam structuri mai complexe, eventual chiar dupa multiple criterii? Pasii de mai jos arata cum se poate adapta o functie banala de sortare pentru a face fata acestor nevoi practice. Ea ajunge sa semene foarte mult cu std::sort, functia oferita de standardul C++. [.....] Tema de casa
tot ce pot zice e să-ți recomand volumul I din ”Arta programării calculatoarelor” a lui Donald Knuth. A fost tradus și în română cred că că la editura Teora prin anii 90. Tot ce zicea omul ăla acum 30 de ani când a scris volumele astea (șapte + la număr) este la fel de actual și acum și va fi și peste 50 de ani că sunt chestii de teorie fundamentală. Astea fiind zise, spor la citit! PS: algoritmul prezentat de tine e unul din cele mai puțin eficiente, poți lua ca temă de casă să vezi de ce. halflife, on 16 decembrie 2017 - 15:53, said:
Programatorii de succes trebuie sa stie algoritmi din astia in C++ ? Edited by DaculScoril0, 17 December 2017 - 05:34. |
#6
Posted 17 December 2017 - 08:52
#7
Posted 17 December 2017 - 10:16
DaculScoril0, on 17 decembrie 2017 - 05:35, said:
PS: algoritmul prezentat de tine e unul din cele mai puțin eficiente, poți lua ca temă de casă să vezi de ce. |
#8
Posted 17 December 2017 - 10:42
Nu-i nevoie de atacuri in stilul "esti bazat". In rest a rezumat bine Mosotti scopul acestui topic.
|
#9
Posted 17 December 2017 - 13:49
"Esti bazat" nu-i atac. Bazat inseamna bogat sau profi in limbaj de carter, zi de zi impreuna, dusmanii mor cind ne descurcam mabine
|
#10
Posted 18 December 2017 - 00:51
|
Anunturi
Bun venit pe Forumul Softpedia!
▶ 0 user(s) are reading this topic
0 members, 0 guests, 0 anonymous users