Razvrščanje je postopek razvrščanja elementov matrike, tako da jih je mogoče postaviti v naraščajočem ali padajočem vrstnem redu. Na primer, razmislite o matriki A = {A1, A2, A3, A4, ?? An } se matrika prikliče v naraščajočem vrstnem redu, če so elementi A urejeni kot A1 > A2 > A3 > A4 > A5 > ? > An .
Razmislite o nizu;
int A[10] = { 5, 4, 10, 2, 30, 45, 34, 14, 18, 9 )
Matrika, razvrščena v naraščajočem vrstnem redu, bo podana kot;
A[] = { 2, 4, 5, 9, 10, 14, 18, 30, 34, 45 }
Obstaja veliko tehnik, s pomočjo katerih je mogoče izvesti razvrščanje. V tem delu vadnice bomo podrobno obravnavali vsako metodo.
Algoritmi za razvrščanje
Algoritmi za razvrščanje so skupaj z opisom opisani v naslednji tabeli.
| SN | Algoritmi za razvrščanje | Opis |
|---|---|---|
| 1 | Bubble Sort | Je najpreprostejša metoda razvrščanja, ki izvaja razvrščanje tako, da večkrat premakne največji element na najvišji indeks matrike. Vključuje primerjavo vsakega elementa z njegovim sosednjim elementom in njihovo ustrezno zamenjavo. |
| 2 | Razvrščanje vedra | Razvrščanje z vedri je znano tudi kot razvrščanje v koših. Deluje tako, da razdeli element v matriko, imenovano tudi vedra. V teh algoritmih za razvrščanje so vedra razvrščena posamezno z uporabo različnih algoritmov za razvrščanje. |
| 3 | Glavnik Razvrsti | Comb Sort je napredna oblika Bubble Sort. Razvrščanje z mehurčki primerja vse sosednje vrednosti, medtem ko razvrščanje z glavnikom odstrani vse vrednosti želve ali majhne vrednosti blizu konca seznama. |
| 4 | Štetje Razvrsti | To je tehnika razvrščanja, ki temelji na ključih, tj. predmeti se zbirajo glede na ključe, ki so majhna cela števila. Razvrščanje s štetjem izračuna število pojavitev predmetov in shrani njihove ključne vrednosti. Nova matrika se oblikuje z dodajanjem prejšnjih ključnih elementov in dodeljevanjem objektom. |
| 5 | Razvrščanje kopice | Pri razvrščanju kopice se najmanjša kopica ali največja kopica vzdržuje iz elementov matrike, odvisno od izbire, elementi pa so razvrščeni tako, da se izbriše korenski element kopice. |
| 6 | Razvrščanje vstavljanja | Kot že ime pove, razvrščanje z vstavljanjem vstavi vsak element matrike na svoje pravo mesto. To je zelo preprosta metoda razvrščanja, ki se uporablja za urejanje kompleta kart med igranjem bridža. |
| 7 | Spoji Razvrsti | Razvrščanje z združevanjem sledi pristopu deli in vladaj, pri katerem je seznam najprej razdeljen na nize enakih elementov, nato pa je vsaka polovica seznama razvrščena z uporabo razvrščanja z združevanjem. Razvrščeni seznam se ponovno združi v osnovno razvrščeno matriko. |
| 8 | Hitro razvrščanje | Hitro razvrščanje je najbolj optimiziran algoritem za razvrščanje, ki izvaja razvrščanje v O(n log n) primerjavah. Tako kot razvrščanje z združitvijo tudi hitro razvrščanje deluje z uporabo pristopa deli in vladaj. |
| 9 | Razvrsti Radix | Pri razvrščanju Radix se razvrščanje izvaja tako, da razvrščamo imena po njihovem abecednem vrstnem redu. To je algoritem lenearnega razvrščanja, ki se uporablja za Inegers. |
| 10 | Izbor Razvrsti | Izbirno razvrščanje poišče najmanjši element v matriki in ga postavi na prvo mesto na seznamu, nato najde drugi najmanjši element v matriki in ga postavi na drugo mesto. Ta postopek se nadaljuje, dokler niso vsi elementi premaknjeni v pravilen vrstni red. Nosi čas delovanja O(n2), ki je najslabši od sortiranja z vstavljanjem. |
| enajst | Shell Sort | Lupinsko razvrščanje je posplošitev razvrščanja z vstavljanjem, ki premaguje pomanjkljivosti razvrščanja z vstavljanjem s primerjavo elementov, ločenih z vrzeljo več položajev. |