Kuplalajittelu vs lisäyslajittelu
Kuplalajittelu on lajittelualgoritmi, joka toimii käymällä lajiteltavaa luetteloa läpi toistuvasti samalla kun vertaamalla vierekkäisiä elementtipareja. Jos elementtipari on väärässä järjestyksessä, ne vaihdetaan sijoittamaan ne oikeaan järjestykseen. Tätä läpikulkua toistetaan, kunnes muita vaihtoja ei tarvita. Lisäyslajittelu on myös lajittelualgoritmi, joka toimii lisäämällä syöteluettelon elementin oikeaan paikkaan jo lajiteltuun luetteloon. Tätä prosessia käytetään toistuvasti, kunnes luettelo on lajiteltu.
Mikä on kuplalajittelu?
Kuplalajittelu on lajittelualgoritmi, joka toimii käymällä lajiteltua luetteloa läpi toistuvasti samalla kun vertaamalla vierekkäisiä elementtipareja. Jos elementtipari on väärässä järjestyksessä, ne vaihdetaan sijoittamaan ne oikeaan järjestykseen. Tätä läpikulkua toistetaan, kunnes muita vaihtoja ei tarvita (mikä tarkoittaa, että luettelo on lajiteltu). Koska luettelon pienemmät elementit tulevat yläosaan kuplan noustessa pintaan, sille annetaan nimi kuplalajittelu. Kuplalajittelu on hyvin yksinkertainen lajittelualgoritmi, mutta sen keskimääräinen tapausaikainen monimutkaisuus on O(n2), kun lajitellaan luetteloa, jossa on n elementtiä. Tästä johtuen kuplalajittelu ei sovellu sellaisten luetteloiden lajitteluun, joissa on paljon elementtejä. Mutta sen yksinkertaisuuden vuoksi kuplalajittelu opetetaan algoritmien johdannossa.
Mikä on lisäyslajittelu?
Lisäyslajittelu on toinen lajittelualgoritmi, joka toimii lisäämällä syöttöluettelon elementin oikeaan kohtaan luettelossa (joka on jo lajiteltu). Tätä prosessia käytetään toistuvasti, kunnes luettelo on lajiteltu. Lisäyslajittelussa lajittelu suoritetaan paikan päällä. Siksi algoritmin i:nnen iteraation jälkeen listan ensimmäiset i+1-merkinnät lajitellaan ja loput listasta jätetään lajittelematta. Jokaisessa iteraatiossa luettelon lajittelemattoman osan ensimmäinen elementti otetaan ja lisätään oikeaan paikkaan luettelon lajitellussa osassa. Lisäyslajittelun keskimääräinen tapausajan monimutkaisuus on O(n2). Tästä johtuen lisäyslajittelu ei myöskään sovellu suurten luetteloiden lajitteluun.
Mitä eroa on kuplalajittelulla ja lisäyslajittelulla?
Vaikka sekä kuplalajittelu- että lisäyslajittelualgoritmien tapausten keskimääräinen monimutkaisuus on O(n2), kuplalajittelu ylittää lähes aina lisäyslajittelun. Tämä johtuu kahden algoritmin tarvitsemasta vaihtojen määrästä (kuplalajittelu vaatii enemmän vaihtoja). Mutta kuplalajittelun yksinkertaisuuden vuoksi sen koodikoko on hyvin pieni. Myös lisäyslajittelusta on olemassa muunnos nimeltä shell sort, jonka aikamonimutkaisuus on O(n3/2), mikä mahdollistaisi sen käytön käytännössä. Lisäksi lisäyslajittelu on erittäin tehokas "lähes lajiteltujen" luetteloiden lajitteluun verrattuna kuplalajitteluun.
