Ero kuplalajittelu ja lisäyslajittelu

Kuplalajittelu vs. Lisäyslajittelu

Kuplalajittelu on lajittelualgoritmi, joka toimii lajiteltavan luettelon läpi toistuvasti samalla kun verrataan vierekkäisiä elementtiparia. Jos pari elementtiä on väärässä järjestyksessä, ne vaihdetaan toisiinsa asettaaksesi ne oikeaan järjestykseen. Tämä läpikulku toistetaan, kunnes uusia vaihtoja ei tarvita. Lisäyslajittelu on myös lajittelualgoritmi, joka toimii lisäämällä elementti syöttöluetteloon oikeaan kohtaan luettelossa, joka on jo lajiteltu. Tätä prosessia sovelletaan toistuvasti, kunnes luettelo on lajiteltu.

Mikä on Bubble Sort?

Kuplalajittelu on lajittelualgoritmi, joka toimii lajiteltavan luettelon läpi toistuvasti samalla kun verrataan vierekkäisiä elementtiparia. Jos pari elementtiä on väärässä järjestyksessä, ne vaihdetaan toisiinsa asettaaksesi ne oikeaan järjestykseen. Tämä läpikulku toistetaan, kunnes enää vaihtoa ei tarvita (mikä tarkoittaa, että luettelo on lajiteltu). Koska luettelon pienemmät elementit tulevat kärkeen, kun kupla tulee pintaan, sille annetaan nimi kuplalajittelu. Kuplalajittelu on hyvin yksinkertainen lajittelualgoritmi, mutta siinä on keskimääräinen tapausajan monimutkaisuus O (n2) lajitellessaan luetteloa n elementillä. Tämän vuoksi kuplalajittelu ei sovellu lajitteluun, jossa on paljon elementtejä. Mutta yksinkertaisuuden takia kuplalajittelu opetetaan algoritmien johdannossa.

Mikä on lisäyslajittelu?

Lisäyslajittelu on toinen lajittelualgoritmi, joka toimii lisäämällä elementti syöttöluetteloon oikeaan kohtaan luettelossa (joka on jo lajiteltu). Tätä prosessia sovelletaan toistuvasti, kunnes luettelo on lajiteltu. Lisäyslajittelussa lajittelu tapahtuu paikallaan. Siksi algoritmin i: nnen toiston jälkeen luettelon ensimmäiset i + 1 -merkinnät lajitellaan ja loput luettelosta lajitellaan. Jokaisessa iteraatiossa luettelon lajittelemattoman osan ensimmäinen elementti otetaan ja lisätään oikeaan kohtaan luettelon lajiteltuun kohtaan. Lisäyksellä on keskimääräinen tapausajan monimutkaisuus O (n2). Tästä syystä lisäyslajittelu ei sovellu myös suurten luetteloiden lajitteluun.

Mitä eroa kuplalajittelu ja lisäyslajittelu ovat??

Vaikka sekä kuplalajittelu- että lisäyslajittelualgoritmeilla on keskimääräiset tapauskohtaiset kompleksisuudet O (n2), kuplalajittelu on lähes koko ajan parempi kuin lisäyslajittelu. Tämä johtuu kahden algoritmin tarvitsemasta vaihtosummasta (kuplalajit tarvitsevat enemmän vaihtosopimuksia). Mutta kuplalajittelun yksinkertaisuuden vuoksi sen koodikoko on hyvin pieni. Lisäksi on olemassa lisäyslajittelulaji, nimeltään kuorilajittelu, jolla on aikakompleksisuus O (n3 / 2), mikä mahdollistaisi sen käytön käytännössä. Lisäksi lisäyslajittelu on erittäin tehokas "melkein lajiteltujen" luetteloiden lajitteluun verrattuna kuplalajitteluun.