Vsebina

• Primerjalna tabela
• Opredelitev vrste Bubble Sort
• Opredelitev vrste izbire
• Zaključek

Razvrščanje je ena glavnih nalog v računalniških programih, pri katerih so elementi matrike razporejeni v določenem vrstnem redu. Razvrščanje olajša iskanje. Razporeditev mehurčkov in izbira so algoritmi za razvrščanje, ki jih je mogoče razlikovati z metodami, ki jih uporabljajo za razvrščanje. Razporeditev mehurčkov v bistvu izmenja elemente, medtem ko izbira razvršča sortiranje z izbiro elementa.

Druga pomembna razlika med obema je, da je vrsta mehurčkov stabilen algoritem, medtem ko je izbira sorta nestabilen algoritem. Za algoritem velja, da so elementi z enakim ključem enaki kot v enakem vrstnem redu, kot so se pojavili pred razvrščanjem na seznamu ali matriki. Na splošno večina stabilnih in hitrih algoritmov uporablja dodatni pomnilnik.

1. Primerjalna tabela
2. Opredelitev
3. Ključne razlike
4. Zaključek

Primerjalna tabela

Osnove za primerjavo	Vrsta mehurčkov	Izbor izbire
Osnovni	Sosednji element primerjamo in zamenjamo	Največji element je izbran in zamenjan z zadnjim elementom (v primeru naraščajočega vrstnega reda).
Najboljša časovna zapletenost	O (n)	O (n2)
Učinkovitost	Neučinkovit	Izboljšana učinkovitost v primerjavi z vrstami mehurčkov
Stabilno	Da	Ne
Metoda	Izmenjava	Izbor
Hitrost	Počasi	Hitro kot v primerjavi z mehurčki

Opredelitev vrste Bubble Sort

Vrsta mehurčkov je najpreprostejši iterativni algoritem, ki primerja vsak element ali element s postavko poleg njega in jih po potrebi zamenja. Z enostavnimi besedami primerja prvi in ​​drugi element seznama in ga zamenja, razen če ni v določenem vrstnem redu. Podobno se primerjata in zamenjata drugi in tretji element, to primerjanje in zamenjava pa se nadaljuje na koncu seznama. Število primerjav v prvi iteraciji je n-1, kjer je n številčni elementi v matriki. Po prvem iteraciji bi bil največji element na n. Po vsaki iteraciji se število primerjav zmanjšuje in končno se izvede samo ena primerjava.

Ta algoritem je najpočasnejši algoritem razvrščanja. Najboljša zapletenost primerov (ko je seznam urejen) sorte Bubble je vrstnega reda n (O (n)), najslabši primer pa je O (n²). V najboljšem primeru je vrstnega reda n, ker elemente le primerja in jih ne zamenja. Ta tehnika zahteva tudi dodaten prostor za shranjevanje začasne spremenljivke.

Opredelitev vrste izbire

Izbor izbire je dosegel nekoliko boljše delovanje in je učinkovitejši od algoritma za razvrščanje mehurčkov. Recimo, da želimo razporediti matriko v naraščajočem vrstnem redu, nato pa deluje tako, da poišče največji element in ga zamenja z zadnjim elementom ter ponovimo naslednji postopek v podračunih, dokler ni urejen celoten seznam.

Pri izbiri razvrščeni in nesortirani niz ne vpliva na nič in porabi vrstni red n² (O (n²)) tako v najboljšem kot v najslabšem primeru. Razvrščanje izbire je hitrejše od razvrščanja z mehurčki.

1. Pri razvrščanju mehurčkov se vsak element in njegov sosednji element primerjata in po potrebi zamenjata. Po drugi strani izbira razvrščanje deluje tako, da izbere element in zamenja ta določen element z zadnjim elementom. Izbrani element je lahko največji ali najmanjši, odvisno od vrstnega reda, tj. Naraščajočega ali padajočega.
2. Najhujša zapletenost je v obeh algoritmih enaka, to je O (n²), vendar je najboljša zapletenost drugačna. Razporeditev mehurčkov traja n čas, medtem ko sorta izbira porabi n² čas.
3. Razvrščanje mehurčkov je stabilen algoritem, v nasprotju s tem je izbira razvrstitev nestabilna.
4. Izbirni algoritem razvrščanja je hiter in učinkovit v primerjavi z razvrščanjem mehurčkov, ki je zelo počasen in neučinkovit.

Zaključek

Algoritem razvrščanja mehurčkov velja za najbolj preprost in neučinkovit algoritem, vendar je algoritem izbire razvrščanja učinkovit v primerjavi z razvrščanjem mehurčkov. Različica mehurčkov porabi tudi dodaten prostor za shranjevanje začasnih spremenljivk in potrebuje več zamenjav.