⚙️ Programare C++: Algoritmi de Sortare

⚙️ Programare C++: Algoritmi de Sortare

În tutoriatul de astăzi vă voi arată cum funcționează și cum putem aplica trei algoritmi de sortare a tablourilor unidimensionale (vectori), în limbajul de programare C++. Înainte de a începe, considerăm sortat vectorul care are aranjate, în ordine crescătoare, toate valorile. Primul pas este să înțelegem cum funcționează codul prezentat. Fiind 3 algoritmi separați vom parcurge înainte explicația logică, apoi vom vedea reprezentarea în limbaj. Un exemplu de intrare - ieșire care funcționează este v = { 12, 51, 32, 61, 14 }, cu afișarea 12 14 32 51 61.

Primul algoritm de sortare pe care îl vom parcurge în tutorial este sortare prin selecție, un algoritm simplu, care folosește 2 structuri repetitive cu număr cunoscut de pași și o structură alternativă pentru a testa valorile parcurse. Complexitatea algoritmului este O(n²). Acest program constă în folosirea a două variabile de parcurgere (i, j), care reprezintă 2 poziții consecutive din șirul nesortat de numere. Apoi, la fiecare pas, vom verifica dacă numărul de pe poziția mai mică este mai mare ca valoare decât cel de pe poziția următoare. Dacă da, vom interschimba numerele folosind funcția integrată, swap().

Al doilea algoritm pe care îl vom parcurge astăzi este sortarea STL (Standard Template Library). Acesta poate fi folosit apelând funcția cu 2 parametri (în cazul sortării în ordine crescătoare), primul fiind prima poziție din vector, iar al doilea ultima. Complexitatea algoritmului este O(n * log_n). Chiar dacă este cel mai la îndemână algoritm, acesta poate fi greu de folosit în unele situații mai complexe (sortări în funcție de ceva), necesitând crearea unor funcții cu parametrii speciali.

Ultimul, dar nu cel din urmă, algoritm pe care îl vom înțelege este QuickSort, numit și sortare Divide Et Impera. Acest algoritm se bazează pe procedeul menționat anterior pentru a funcționa. Va partiționa șirul mare în mai multe subșiruri, pe care va lucra simultan și care vor fi sortate. Cel mai simplu de scris este folosind recursivitatea, în timp ce celelalte 2 programe prezentate nu au nevoie necesară de funcții separate. Începem prin a apela funcția sortare_quick(), folosind 3 parametrii, vectorul pe care dorim să îl modificăm, poziția de start de pe care se va începe sortarea și poziția de stop. De ce poziție de start și stop și nu prima poziție din vector respectiv ultima? Răspunsul este simplu, pe parcursul fragmentării vom folosi diverse repere numite pivoți. Apoi, folosind fiecare pivot, vom verifica toate numerele din partiție și le vom interschimba în funcție de valori, folosind funcția prestabilită, swap(). La finalul partiționării vom trimite noul pivot către procesare. Rapiditatea ultimului algoritm din tutorial constă în metoda de împărțire a activitățiilor și oferă complexitatea O(n * log_n).

Mai jos poți vedea problemele recomandate și totodată concluzia tutorialului. Ordinea vitezei algoritmilor este: sortarea prin selecție > sortarea Standard Template Library (STL) > sortarea rapidă (QuickSort). În timp ce ordinea permisibilității de modificare este: sortarea rapidă (QuickSort) > sortarea prin selecție > sortarea Standard Template Library (STL).

Probleme recomandate de pe platforma PBinfo: sortpp, paresort, sort2

Andrei Frîntu

Fondatorul platformei - mentor Academia