Kuplalajittelu

Lajittelu yksinkertaisten vaihtojen mukaan, lajittelu kuplan mukaan ( englanniksi  bubble sort ) on yksinkertainen lajittelualgoritmi . Tämän algoritmin ymmärtäminen ja toteuttaminen on yksinkertaisinta, mutta se on tehokas vain pienille taulukoille. Algoritmin monimutkaisuus : .

Algoritmia pidetään opetuksellisena, eikä sitä käytännössä käytetä opetuskirjallisuuden ulkopuolella, vaan käytännössä käytetään tehokkaampia lajittelualgoritmeja. Samaan aikaan vaihtolajittelumenetelmä on joidenkin kehittyneempien algoritmien, kuten shaker sort , keon lajittelu ja pikalajittelu , taustalla .

Algoritmi

Algoritmi koostuu toistuvista läpikulkuista lajitellun taulukon läpi. Jokaisella läpimenolla elementtejä verrataan peräkkäin pareittain ja jos parin järjestys on virheellinen, elementit permutoidaan. Matriisin läpikäymiset toistetaan kerran tai kunnes seuraavassa läpikäynnissä käy ilmi, että vaihtoja ei enää tarvita, mikä tarkoittaa, että taulukko on lajiteltu. Jokaisella algoritmin sisäisen silmukan läpikäymisellä taulukon seuraavaksi suurin elementti asetetaan paikoilleen taulukon loppuun edellisen "suurimman elementin" viereen ja pienin elementti siirtyy yhden kohdan taulukon alkuun. array ("kelluu" haluttuun kohtaan, kuten kupla vedessä - tästä ja algoritmin nimi).

Toteutus

Vaikeusaste :.

Pahimmassa tapauksessa:

Paras tapaus (jo lajiteltu matriisi syötetään):

Tämän algoritmin erikoisuus on seuraava: sisäisen silmukan ensimmäisen valmistumisen jälkeen taulukon maksimielementti on aina -: nnessa paikassa. Toisella ajolla seuraavaksi suurin elementti on paikallaan. Ja niin edelleen. Siten jokaisella myöhemmällä läpikäynnillä prosessoitujen elementtien lukumäärä vähenee yhdellä, eikä koko taulukkoa tarvitse "kulkea" alusta loppuun joka kerta.

Koska yhden elementin aliryhmää ei tarvitse lajitella, lajittelu ei vaadi enempää kuin ulomman silmukan iteraatioita. Siksi joissakin toteutuksissa ulompi silmukka toimii aina sujuvasti eikä seuraa, oliko vai ei ollut vaihtoja jokaisessa iteraatiossa.

Varsinaisen vaihdon indikaattorin (lippu F) käyttöönotto sisäsilmukassa vähentää ylimääräisten läpivientien määrää tapauksissa, joissa syötetaulukot ovat osittain lajiteltuja. Ennen jokaista sisäisen silmukan läpikulkua lippu palautetaan arvoon 0, ja sen jälkeen, kun vaihto todella tapahtui, se asetetaan arvoon 1. Jos lippu on 0 sisäisestä silmukasta poistumisen jälkeen, vaihtoja ei ollut, eli taulukko on lajiteltu ja voit poistua lajitteluohjelmasta etuajassa.

Pseudokoodi vieläkin parannellulle algoritmille, joka tarkistaa, onko sisäisessä silmukassa todella tapahtunut vaihtoja.

Syöte: taulukko , joka koostuu elementeistä, numeroitu alkaen -

SILMUKAUS J = 1 - N - 1 VAIHE 1 J = 1 - N - 1 VAIHE 1 F = 0 F = 0 SILMUKKO I = 0 - N - 1 - J VAIHE 1 I = 0 - N - 1 - J _ _ _ _ VAIHE 1 JOS A [ I ] > A [ I + 1 ] SIIN VAIHDA A [ I ], A [ I + 1 ]: F = 1 JOS A [ I ] > A [ I + 1 ] SIIN VAIHDA A [ I ], A [ I + 1 ]: F = 1 SEURAAVA I SEURAAVA I JOS F = 0 NIIN POISTU SILMUKKOSTA JOS F = 0 SIIN POISTU JOS SEURAAVA J SEURAAVA J

Jos lajittelusta poistutaan aikaisin, tämä algoritmi tekee yhden redundantin läpimenon ilman vaihtoja.

Pahin tapaus (ei parane):

  • Vertailujen määrä silmukan rungossa on .
  • Vertailujen määrä silmukan otsikoissa .
  • Vertailujen kokonaismäärä on .
  • Tehtävien määrä silmukkaotsikoissa on .
  • Vaihtojen määrä on .

Paras tapaus (parempi):

  • Vertailujen määrä silmukan rungossa on .
  • Vertailujen määrä silmukan otsikoissa .
  • Vertailujen kokonaismäärä on .
  • Vaihtojen määrä on .

10 000 lyhyen kokonaisluvun lajitteluaika samassa laitteisto-ohjelmistokompleksissa (vertailutoiminto ≈3,4 µs, vaihto ≈2,3 µs) valintalajittelulla oli ≈40 sekuntia, vielä parannetulla kuplalajittelulla ≈30 sekuntia ja pikalajittelulla ≈0,027 . sek.

suurempi kuin yhdistämislajittelu , mutta pienellä ero ei ole kovin suuri ja ohjelmakoodi on hyvin yksinkertainen, joten on varsin hyväksyttävää käyttää kuplalajittelua monissa tehtävissä pieniulotteisilla taulukoilla tyhjäkäynnillä ja kevyesti ladatuissa koneissa.

Algoritmia voidaan hieman parantaa seuraavasti:

  • Sisäsilmukkaa voidaan muokata siten, että se skannaa taulukkoa vuorotellen alusta ja sitten lopusta. Tällä tavalla muokattua algoritmia kutsutaan sekoituslajitteluksi tai shaker sortiksi. Tämä ei vähennä monimutkaisuutta .

Kuplalajittelussa voit jokaisella sisäisen silmukan läpikäymisellä lisätä seuraavan minimielementin määritelmän ja sijoittaa sen taulukon alkuun, eli yhdistää kuplalajittelu- ja valintalajittelualgoritmit samalla kun läpikulkujen määrä sisäsilmukka puolitetaan, mutta vertailujen määrä ja yksi vaihto lisätään jokaisen sisäisen silmukan läpikulun jälkeen.

Yhdistetyn kuplalajittelu- ja valintalajittelualgoritmin pseudokoodi ( vakaa toteutus):

J = 0 - N - 1 VAIHE 1 F = 0 MIN = J I = J - N - 1 - J VAIHE 1 JOS [ I ] > K [ I + 1 ] NIIN VAIHDA Y [ I ] , Y [ I _ _ + 1 ] : F = 1 JOS [ I ] < K [ MIN ] NIIN MIN = I SEURAAVA JOS F = 0 POISTU JOS MIN < > J SIIN VAIHDA Y [ J ] , Y [ MIN ] SEURAAVA J

C

Esimerkki algoritmin toiminnasta

Otetaan taulukko numeroilla "5 1 4 2 8" ja lajitellaan arvot nousevaan järjestykseen käyttämällä kuplalajittelua. Tässä vaiheessa verrattavat elementit korostetaan.

Ensimmäinen läpimeno:

( 5 1 4 2 8) ( 1 5 4 2 8), Tässä algoritmi vertaa kahta ensimmäistä elementtiä ja vaihtaa ne. (1 5 4 2 8) (1 4 5 2 8), Vaihtaa koska (1 4 5 2 8) (1 4 2 5 8), Vaihto, koska (1 4 2 5 8 ) (1 4 2 5 8 ), Koska elementit ovat nyt paikoillaan ( ), algoritmi ei vaihda niitä keskenään.

Toinen passi:

( 1 4 2 5 8) ( 1 4 2 5 8) (1 4 2 5 8) (1 2 4 5 8), Vaihto, koska (1 2 4 5 8) (1 2 4 5 8)

Nyt matriisi on täysin lajiteltu, mutta algoritmi ei tiedä tätä. Siksi hänen on suoritettava täysi läpäisy ja määritettävä, että elementtien permutaatioita ei ollut.

Kolmas passi:

( 1 2 4 5 8) ( 1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8)

Nyt matriisi on lajiteltu ja algoritmi voidaan suorittaa loppuun.

Linkit