Sisällysluettelo:
Määritelmä - mitä kuplalajittelu tarkoittaa?
Kuplalajittelu on lajittelualgoritmi, joka toimii toistuvasti läpi lajiteltavien luetteloiden avulla, vertaamalla kutakin vierekkäisten esineiden paria ja vaihtamalla niitä, jos ne ovat väärässä järjestyksessä. Tämä ohitusmenettely toistetaan, kunnes vaihtoa ei vaadita, mikä osoittaa, että luettelo on lajiteltu. Kuplalajittelu saa nimensä, koska pienemmät elementit kupliavat kohti luettelon kärkeä.
Kuplalajitteluun viitataan myös uppoamislajitteluna tai vertailulajitteluna.
Techopedia selittää Bubble Sort
Kuplalajittelu on pahimmassa tapauksessa ja keskimääräinen monimutkaisuus O (n2), missä n on lajiteltujen kappaleiden lukumäärä. Toisin kuin muut lajittelualgoritmit, kuplalajittelu tunnistaa, onko lajiteltu luettelo tehokkaasti sisäänrakennettu algoritmiin. Kuplan lajitteluteho jo lajitellun luettelon yli on O (n).
Elementtien paikalla kuplalajikkeessa on tärkeä rooli suorituskyvyn määrittämisessä. Alussa suuret elementit eivät ole ongelmia, koska ne ovat helposti vaihdettavissa. Pienet elementit kohti loppua liikkuvat alkuun hitaasti. Sellaisenaan näitä elementtejä kutsutaan kaneiksi ja kilpikonniksi.
Kuplalajittelualgoritmi voidaan optimoida sijoittamalla suurempia elementtejä lopulliseen sijaintiin. Jokaisen läpikulun jälkeen kaikki viimeisen vaihdon jälkeiset elementit lajitellaan eikä niitä tarvitse tarkistaa uudelleen, jolloin ohitetaan vaihdettujen muuttujien seuranta.
