Lajittelu on prosessi, jossa taulukon elementit järjestetään siten, että ne voidaan sijoittaa joko nousevaan tai laskevaan järjestykseen. Tarkastellaan esimerkiksi taulukkoa A = {A1, A2, A3, A4, ?? An }, taulukkoa kutsutaan olemaan nousevassa järjestyksessä, jos A:n elementit on järjestetty kuten A1 > A2 > A3 > A4 > A5 > ? > An.
Harkitse taulukkoa;
int A[10] = { 5, 4, 10, 2, 30, 45, 34, 14, 18, 9 )
Nousevaan järjestykseen lajiteltu taulukko annetaan muodossa;
A[] = { 2, 4, 5, 9, 10, 14, 18, 30, 34, 45 }
On monia tekniikoita, joiden avulla lajittelu voidaan suorittaa. Tässä opetusohjelman osassa käsittelemme jokaista menetelmää yksityiskohtaisesti.
Lajittelualgoritmit
Lajittelualgoritmit kuvataan seuraavassa taulukossa kuvauksen kanssa.
| SN | Lajittelualgoritmit | Kuvaus |
|---|---|---|
| 1 | Kuplalajittelu | Se on yksinkertaisin lajittelumenetelmä, joka suorittaa lajittelun siirtämällä toistuvasti suurimman elementin taulukon korkeimpaan indeksiin. Se koostuu kunkin elementin vertaamisesta viereiseen elementtiin ja niiden korvaamisesta vastaavasti. |
| 2 | Kauhan lajittelu | Ämpärilajittelu tunnetaan myös nimellä roskakorilajittelu. Se toimii jakamalla elementin taulukkoon, jota kutsutaan myös kauhoiksi. Tässä lajittelualgoritmeissa kauhat lajitellaan yksitellen käyttämällä eri lajittelualgoritmeja. |
| 3 | Kampa lajittelu | Comb Sort on kuplalajittelun edistynyt muoto. Bubble Sort vertaa kaikkia vierekkäisiä arvoja, kun taas kampalajittelu poistaa kaikki kilpikonnaarvot tai pienet arvot luettelon lopusta. |
| 4 | Laskennallinen lajittelu | Se on avaimiin perustuva lajittelutekniikka, eli objektit kerätään avaimien mukaan, jotka ovat pieniä kokonaislukuja. Laskeva lajittelu laskee objektien esiintymistiheyden ja tallentaa sen avainarvot. Uusi taulukko muodostetaan lisäämällä aiempia avainelementtejä ja määrittämällä niitä objekteihin. |
| 5 | Keon lajittelu | Keon lajittelussa taulukon elementeistä ylläpidetään Min-keko tai max-keko valinnan mukaan ja elementit lajitellaan poistamalla keon juurielementti. |
| 6 | Lisäys Lajittele | Kuten nimestä voi päätellä, lisäyslajittelu lisää taulukon jokaisen elementin oikeaan paikkaansa. Se on hyvin yksinkertainen lajittelumenetelmä, jota käytetään korttipakan järjestämiseen bridžaa pelatessa. |
| 7 | Yhdistä lajittelu | Yhdistämislajittelu noudattaa jakaa ja hallitse -lähestymistapaa, jossa lista ensin jaetaan samansuuruisiin elementteihin ja sitten listan kukin puolikas lajitellaan yhdistämislajittelulla. Lajiteltu lista yhdistetään uudelleen muodostamaan alkeislajiteltu taulukko. |
| 8 | Nopea lajittelu | Pikalajittelu on optimoiduin lajittelualgoritmi, joka suorittaa lajittelun O(n log n) -vertailuissa. Kuten Yhdistä lajittelu, myös nopea lajittelu toimii jakaa ja hallitse -lähestymistavan avulla. |
| 9 | Lajittele Radix | Radix-lajittelussa lajittelu tapahtuu samalla tavalla kuin lajittelemme nimet niiden aakkosjärjestyksen mukaan. Se on leeneaarinen lajittelualgoritmi, jota käytetään Inegereille. |
| 10 | Valinta Lajittele | Valintalajittelu etsii taulukon pienimmän elementin ja sijoittaa sen listan ensimmäiselle paikalle, sitten se löytää taulukon toiseksi pienimmän elementin ja sijoittaa sen toiselle sijalle. Tämä prosessi jatkuu, kunnes kaikki elementit on siirretty oikeaan järjestykseen. Se kuljettaa käyntiaikaa O(n2), joka on huonoin kuin lisäyslajittelu. |
| yksitoista | Shell Lajittele | Shell-lajittelu on lisäyslajittelun yleistys, joka poistaa lisäyslajittelun haitat vertaamalla elementtejä, jotka on erotettu useiden paikkojen väliltä. |