Kuplalajittelu vs valintalajittelu
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. Valintalajittelu on myös lajittelualgoritmi, joka aloittaa etsimällä luettelon minimielementin ja vaihtamalla sen ensimmäiseen elementtiin. Tämä prosessi toistetaan luettelon loppuosan ajan asettamalla vaihdetut elementit järjestykseen.
Mikä on kuplalajittelu?
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 (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 valintalajittelu?
Valintalajittelu on myös toinen lajittelualgoritmi, joka alkaa etsimällä luettelosta vähimmäiselementti ja vaihtamalla se ensimmäiseen elementtiin. Sitten minimielementti löydetään listan loppuosasta (toisesta elementistä listan viimeiseen elementtiin) ja vaihdetaan toiseen elementtiin. Tämä prosessi toistetaan luettelon loppuosan ajan asettamalla vaihdetut elementit järjestykseen. Joten valintalajittelussa missä tahansa algoritmin vaiheessa lista jaetaan kahteen osaan, joista toinen sisältää lajiteltuja elementtejä ja toinen osa lajittelemattomia elementtejä. Algoritmin edetessä lajiteltu luettelo kasvaa vasemm alta oikealle. Valintalajittelulla on myös keskimääräinen tapausajan monimutkaisuus O(n2). Siksi se ei myöskään sovellu suurten luetteloiden lajitteluun.
Mitä eroa on kuplalajittelulla ja valintalajittelulla?
Vaikka sekä kuplalajittelu- että valintalajittelualgoritmeilla on keskimääräinen tapausajan monimutkaisuus O(n2), kuplalajittelu on lähes aina parempi kuin valintalajittelu. Tämä johtuu kahden algoritmin tarvitsemasta vaihtojen määrästä (kuplalajittelu vaatii enemmän vaihtoja). Mutta kuplalajittelun yksinkertaisuuden vuoksi sen koodikoko on hyvin pieni. Vakaus on toinen ero näissä kahdessa algoritmissa. Vakaa lajittelualgoritmi on lajittelualgoritmi, joka säilyttää tietueiden järjestyksen, jos luettelo sisältää elementtejä, joilla on sama arvo. Tässä mielessä valintalajittelu ei ole vakaa algoritmi, kun taas kuplalajittelu on vakaa algoritmi.
