LAJITTELUALGORITMIT

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 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ä.