Kuplalajittelu

Kuplalajittelualgoritmi edellyttää paria sisäkkäisiä silmukoita. Ulomman silmukan täytyy toistaa kerran kullekin tietojoukon elementille (koko n), kun taas sisempi silmukka toistaa n kertaa ensimmäistä kertaa syötettäessä, n-1 kertaa toinen ja niin edelleen. Harkitse kunkin silmukan tarkoitusta. Kuten yllä selitettiin, kuplalajittelu on jäsennelty siten, että jokaisella luettelon läpäisyllä tiedon seuraava suurin osa siirretään oikeaan paikkaan. Siksi, jotta kaikki n elementti saadaan oikeisiin paikkoihin, ulompi silmukka on suoritettava n kertaa.

Sisäinen silmukka suoritetaan jokaisella ulomman silmukan iteroinnilla. Sen tarkoitus on asettaa seuraavaksi suurin elementti asetetaan paikalleen. Sisäinen silmukka tekee siten vertailun ja vaihtaa vierekkäisiä elementtejä. Tämän silmukan monimutkaisuuden määrittämiseksi laskemme suoritettavien vertailujen määrän. Ulkosilmukan ensimmäisellä iteroinnilla, kun yritetään sijoittaa suurinta elementtiä, on oltava n – 1 vertailua: ensimmäinen vertailu tehdään ensimmäisen ja toisen elementin välillä, toinen tehdään toisen ja kolmannen elementin välillä ja niin edelleen, kunnes n-1: n ja n: nnen elementin välillä tehdään n-1. vertailu. Ulkosilmukan toisella iteroinnilla ei tarvitse verrata luettelon viimeistä elementtiä, koska se asetettiin oikeaan paikkaan edellisellä kierroksella. Siksi toinen iterointi vaatii vain n-2-vertailuja. Tämä malli jatkuu ulomman silmukan toiseksi viimeiseen iterointiin, kun vain luettelon kaksi ensimmäistä elementtiä on lajittelematta; selvästi tässä tapauksessa tarvitaan vain yksi vertailu. Siksi vertailujen kokonaismäärä on (n – 1) + (n – 2) … (2) + (1) = n (n – 1) / 2 tai O (n2).

Paras tapa kuplalajittelulle tapahtuu, kun luettelo on jo lajiteltu tai melkein lajiteltu. Jos luettelo on jo lajiteltu, kuplalajittelu päättyy ensimmäisen iteraation jälkeen, koska vaihtoja ei tehty. Aina kun luettelon läpi tehdään läpikäynti eikä vaihtoja suoritettu, luettelo on lajiteltu. Kuplalajittelu on tehokas myös silloin, kun yksi satunnaiselementti on lajiteltava lajiteltuun luetteloon edellyttäen, että uusi elementti sijoitetaan alkuun eikä loppuun. Kun se asetetaan alkuun, se vain kuplii oikeaan paikkaan, ja toinen iterointi luettelon läpi tuottaa 0 swapia, mikä lopettaa lajittelun. Muista, että jos satunnaiselementti sijoitetaan loppuun, kuplalajittelu menettää tehokkuutensa, koska jokaisen sitä suuremman elementin on kuplittava aina ylhäältä ylöspäin. luettelon pienin osa on lopussa. Koska kussakin iteraatiossa vain suurin lajittelematon elementti asetetaan oikeaan paikkaan, kun pienin elementti on lopussa, se on vaihdettava joka kerta luettelon läpi, ja se tapaa päästä luettelon etuosaan, kunnes kaikki n iteraatioita on tapahtunut. Tässä pahimmassa tapauksessa se vie n / 2 vaihdon n iteraatiota, joten järjestys on jälleen n2.

Paras tapaus: nAverage Case: n2Worst Case: n2

Leave a Reply

Vastaa

Sähköpostiosoitettasi ei julkaista. Pakolliset kentät on merkitty *