Kuplalajittelu

PerformanceEdit

Kuplalajittelulla on huonoin tapaus ja keskimääräinen monimutkaisuus О (n2), jossa n on lajiteltavien kohteiden lukumäärä. Useimmilla käytännön lajittelualgoritmeilla on huomattavasti parempi pahimman tai keskimääräisen monimutkaisuus, usein O (n log n). Jopa muut О (n2) lajittelualgoritmit, kuten lisäyslajittelu, toimivat yleensä nopeammin kuin kuplalajittelu, eivätkä ne ole monimutkaisempia. Siksi kuplalajittelu ei ole käytännöllinen lajittelualgoritmi.

Ainoa merkittävä etu, jonka kuplalajittelulla on useimpiin muihin algoritmeihin verrattuna, jopa pikalajittelu, mutta ei lisäyslajittelu, on se, että kyky havaita, että luettelo on lajiteltu tehokkaasti on sisäänrakennettu algoritmiin. Kun luettelo on jo lajiteltu (paras tapa), kuplalajittelun monimutkaisuus on vain O (n). Sitä vastoin useimmat muut algoritmit, jopa ne, joiden keskimääräinen tapaus on monimutkaisempi, suorittavat koko lajitteluprosessin joukossa ja ovat siten monimutkaisempia. Lisälajittelu ei kuitenkaan vain jaa tätä etua, vaan se toimii paremmin myös luettelossa, joka on olennaisesti lajiteltu (jossa on pieni määrä inversioita). Lisäksi, jos tätä käyttäytymistä halutaan, se voidaan lisätä triviaalisesti mihin tahansa muuhun algoritmiin tarkistamalla luettelo ennen algoritmin suorittamista.

Kuplalajittelua tulisi välttää suurten kokoelmien tapauksessa. Se ei ole tehokas, kun kyseessä on käänteisesti järjestetty kokoelma.

Kanit ja TurtlesEdit

Etäisyys ja suunta, jonka elementtien on siirrettävä lajittelun aikana, määrää kuplalajittelun suorituskyvyn, koska elementit liikkuvat eri suuntiin eri nopeuksilla. Elementti, jonka on siirryttävä luettelon loppua kohti, voi liikkua nopeasti, koska se voi osallistua peräkkäisiin vaihtosopimuksiin. Esimerkiksi luettelon suurin elementti voittaa jokaisen vaihdon, joten se siirtyy sen lajiteltu sijainti ensimmäisellä kierroksella, vaikka se alkaa läheltä alusta. Toisaalta elementti, jonka on siirryttävä luettelon alkuun, ei voi liikkua nopeammin kuin yksi askel per kulku, joten elementit liikkuvat kohti alkua hyvin hitaasti. pienin elementti on luettelon lopussa, sen siirtäminen alkuun vie n − 1 läpikulkua, mikä on johtanut siihen, että tämän tyyppiset elementit nimetään kaneiksi ja kilpikonniksi Aesopin tarinan merkkien mukaan. Kilpikonna ja jänis.

Eri kilpikonnat on pyritty poistamaan kuplalajittelun nopeuden parantamiseksi. Cocktail-lajittelu on kaksisuuntainen kuplalaji, joka kulkee alusta loppuun ja kääntää sitten itsensä päin, alusta loppuun. Se voi liikuttaa kilpikonnia melko hyvin, mutta se säilyttää O (n2) pahimman tapauksen monimutkaisuuden. Kampaamolajittelu vertaa elementtejä, jotka on erotettu suurilla aukoilla, ja voi siirtää kilpikonnia erittäin nopeasti, ennen kuin siirryt pienempiin aukkoihin tasoittamaan luetteloa. Sen keskinopeus on verrattavissa nopeampiin algoritmeihin, kuten quicksort.

Vaiheittainen esimerkkiMuokkaa

Ota joukko numeroita ”5 1 4 2 8” ja lajittele matriisi alimmasta. numero suurimpaan lukuun käyttämällä kuplalajittelua. Jokaisessa vaiheessa verrataan lihavoituja elementtejä. Kolme ohitusta vaaditaan;

Ensimmäinen syöttö (5 1 4 2 8) → (1 5 4 2 8), Tässä algoritmi vertaa kahta ensimmäistä elementtiä ja vaihtaa, koska 5 > 1. (1 5 4 2 8) → (1 4 5 2 8), Vaihda vuodesta 5 > 4 (1 4 5 2 8) → (1 4 2 5) 8), Vaihda, koska 5 > 2 (1 4 2 5 8) → (1 4 2 5 8), Nyt, koska nämä elementit ovat jo järjestyksessä (8 > 5), algoritmi ei vaihda niitä. Toinen kulku (1 4 2 5 8) → (1 4 2 5 8) (1 4 2 5 8) → (1 2 4 5 8), Vaihda vuodesta 4 > 2 ( 1 2 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8)

Nyt taulukko on jo lajiteltu, mutta algoritmi ei tiedä onko se valmis . Algoritmi tarvitsee yhden kokonaisen siirron ilman vaihtoja tietääkseen, että se on lajiteltu.