Druga velika razlika med obema je, da je sortiranje mehurčkov stabilen algoritem, medtem ko je vrsta razvrščanja nestabilen algoritem. Šteje se, da je algoritem stabilen element z istim ključem, ki se pojavlja v istem vrstnem redu, kot so se pojavili pred sortiranjem na seznamu ali matriki. Na splošno najbolj stabilni in hitri algoritmi uporabljajo dodaten pomnilnik.
Primerjalna tabela
| Podlaga za primerjavo | Bubble sort | Izbira vrste |
|---|---|---|
| Osnovno | Sosednji element se primerja in zamenja | Največji element se izbere in zamenja z zadnjim elementom (v primeru naraščajočega reda). |
| Najboljša časovna zapletenost | O (n) | O (n 2 ) |
| Učinkovitost | Neučinkovit | Izboljšana učinkovitost v primerjavi z razvrščanjem mehurčkov |
| Stabilno | Da | Ne |
| Metoda | Izmenjava | Izbira |
| Hitrost | Počasi | Hitro v primerjavi z balonom |
Definicija Bubble Sort
Razvrščanje mehurčkov je najpreprostejši iterativni algoritem, ki deluje tako, da primerja vsak element ali element z elementom ob njem in ga po potrebi zamenja. S preprostimi besedami primerja prvi in drugi element seznama in ga zamenja, razen če sta izven posebnega vrstnega reda. Podobno se primerjata in zamenjujeta drugi in tretji element, ki se nato primerja in zamenja na konec seznama. Število primerjav v prvi iteraciji je n-1, kjer je n število elementov v matriki. Največji element bi bil na prvem mestu po prvi ponovitvi. Po vsaki ponovitvi se število primerjav zmanjša, ob zadnji ponovitvi pa se izvede le ena primerjava.
Ta algoritem je najpočasnejši algoritem za razvrščanje. Najboljša zapletenost primera (ko je seznam v vrstnem redu) sorte Bubble je od n ( O (n) ), najslabša pa je O (n2) . V najboljšem primeru je red n, ker le primerja elemente in jih ne zamenja. Ta tehnika zahteva tudi dodaten prostor za shranjevanje začasne spremenljivke.
Opredelitev sortne vrste
Izbor sort je dosegel nekoliko boljše zmogljivosti in je učinkovit kot algoritem razvrščanja. Recimo, da želimo razvrstiti matriko v naraščajočem vrstnem redu, potem deluje tako, da najdemo največji element in ga zamenjamo z zadnjim elementom, in ponovimo naslednji proces na podarjih, dokler ne razvrstimo celotnega seznama.
Razlike med ključi med razvrščanjem in razvrščanjem izbire
- Pri razvrščanju mehurčkov se vsak element in njegov sosednji element po potrebi primerjata in zamenjujeta. Po drugi strani pa sortna sorta deluje tako, da izbere element in zamenja ta element z zadnjim elementom. Izbrani element je lahko največji ali najmanjši, odvisno od naročila, to je, naraščajoče ali padajoče.
- Najslabša zapletenost je pri obeh algoritmih enaka, tj. O (n2), vendar je najboljša kompleksnost drugačna. Razvrščanje v obliki mehurčkov traja od n časa, medtem ko vrsta izbire porabi red n2 časa.
- Razvrščanje mehurčkov je stabilen algoritem, nasprotno pa je sortna vrsta nestabilna.
- Izbirni algoritem je hiter in učinkovit v primerjavi z razporeditvijo mehurčkov, ki je zelo počasen in neučinkovit.
Zaključek
Algoritem za razvrščanje mehurčkov se šteje za najbolj preprost in neučinkovit algoritem, vendar je algoritem razvrščanja uspešen v primerjavi z razvrščanjem mehurčkov. Bubble sort tudi porabi dodaten prostor za shranjevanje začasne spremenljivke in potrebuje več zamenjav.
