Toinen merkittävä ero näiden kahden välillä on se, että kuplamajoitus on vakaa algoritmi, kun taas valinnan lajittelu on epävakaa algoritmi. Algoritmin katsotaan olevan tasaisia elementtejä, joilla on sama avain, samassa järjestyksessä kuin ne olivat tapahtuneet ennen lajittelua luettelossa tai ryhmässä. Yleensä vakaimmat ja nopeat algoritmit käyttävät lisämuistia.
Vertailukaavio
| Vertailun perusteet | Bubble sort | Valinta lajitellaan |
|---|---|---|
| perustiedot | Vierekkäistä elementtiä verrataan ja vaihdetaan | Suurin elementti valitaan ja vaihdetaan viimeisen elementin kanssa (nousevassa järjestyksessä). |
| Paras tapaustilan monimutkaisuus | Päällä) | O (n 2 ) |
| tehokkuus | tehoton | Parannettu tehokkuus verrattuna kuplan lajitteluun |
| Vakaa | Joo | Ei |
| Menetelmä | vaihtamalla | Valinta |
| Nopeus | Hidas | Nopea verrattuna kuplan lajitteluun |
Määritelmä Bubble Sort
Bubble sort on yksinkertaisin iteratiivinen algoritmi vertaamalla kutakin kohdetta tai elementtiä sen vieressä olevan kohteen kanssa ja vaihtamalla niitä tarvittaessa. Yksinkertaisesti sanottuna se vertaa luettelon ensimmäistä ja toista elementtiä ja vaihtaa sen, elleivät ne ole tietyssä järjestyksessä. Vastaavasti toista ja kolmatta elementtiä verrataan ja vaihdetaan, ja tämä vertailu ja vaihto tapahtuu luettelon loppuun. Vertailujen lukumäärä ensimmäisessä iteroinnissa on n-1, jossa n on ryhmän elementtejä. Suurin elementti olisi n: nnessä asemassa ensimmäisen iteroinnin jälkeen. Jokaisen iteraation jälkeen vertailujen määrä pienenee ja viimeisessä iteroinnissa tapahtuu vain yksi vertailu.
Tämä algoritmi on hitain lajittelualgoritmi. Bubble-lajittelun paras tapa-kompleksisuus (kun lista on järjestyksessä) on järjestyksessä n ( O (n) ), ja pahimmassa tapauksessa monimutkaisuus on O (n2) . Parhaassa tapauksessa se on järjestyksessä n, koska se vain vertaa elementtejä eikä vaihda niitä. Tämä tekniikka vaatii myös lisätilaa väliaikaisen muuttujan tallentamiseksi.
Valinnan lajittelu
Valintalajittelu on saavuttanut hieman paremman suorituskyvyn ja on tehokasta kuin kuplan lajittelualgoritmi. Oletetaan, että haluamme järjestää taulukon nousevassa järjestyksessä, niin se toimii löytämällä suurimman elementin ja vaihtamalla sen viimeiseen elementtiin ja toistamalla seuraavan prosessin aliryhmissä, kunnes koko lista on lajiteltu.
Bubble Sort ja Selection lajittelevat tärkeimmät erot
- Kuplan lajittelussa kukin elementti ja sen viereinen elementti verrataan ja vaihdetaan tarvittaessa. Toisaalta valinta lajittelu toimii valitsemalla elementti ja vaihtamalla kyseisen elementin viimeiseen elementtiin. Valittu elementti voi olla suurin tai pienin riippuen järjestyksestä eli nousevasta tai laskevasta.
- Pahimmassa tapauksessa monimutkaisuus on sama molemmissa algoritmeissa, eli O (n2), mutta paras monimutkaisuus on erilainen. Bubble lajittelu kestää n ajan, kun taas valinta lajittelee kuluttaa n2: n järjestystä.
- Bubble sort on vakaa algoritmi, sitä vastoin valinta lajittelu on epävakaa.
- Valintalajittelualgoritmi on nopea ja tehokas verrattuna hitaaseen ja tehottomaan kuplatyyppiin.
johtopäätös
Bubble-lajittelualgoritmia pidetään yksinkertaisimpana ja tehottomana algoritmina, mutta valinta lajittelualgoritmi on tehokas verrattuna kuplan lajitteluun. Bubble sort kuluttaa myös lisää tilaa väliaikaisen muuttujan tallentamiseen ja tarvitsee enemmän vaihtosopimuksia.
