Razlika med razvrstitvijo mehurčkov in vstavitvijo

Razporeditev mehurčkov in Razvrsti vstavljanje

Razporeditev mehurčkov je algoritem za razvrščanje, ki deluje tako, da gre skozi seznam, ki ga je treba večkrat sortirati, medtem ko primerja par sosednjih elementov. Če je par elementov v napačnem vrstnem redu, jih zamenjate tako, da jih postavite v pravilen vrstni red. Ta prelet se ponavlja, dokler ni treba zamenjati. Vstavitvena razvrstitev je tudi algoritem razvrščanja, ki deluje tako, da element v vhodni seznam vstavi v pravilen položaj na seznamu, ki je že razvrščen. Ta postopek se uporablja večkrat, dokler se seznam ne razvrsti.

Kaj je sorta mehurčkov?

Razporeditev mehurčkov je algoritem za razvrščanje, ki deluje tako, da gre skozi seznam, ki ga je treba večkrat sortirati, medtem ko primerja par sosednjih elementov. Če je par elementov v napačnem vrstnem redu, jih zamenjate tako, da jih postavite v pravilen vrstni red. Ta prelet se ponavlja, dokler ni potrebnih nadaljnjih zamenjav (kar pomeni, da je seznam razvrščen). Ker manjši elementi na seznamu pridejo na vrh, ko mehurček pride na površino, mu damo ime vrsta mehurčkov. Razporeditev mehurčkov je zelo preprost algoritem razvrščanja, vendar ima pri razvrščanju seznama z n elementi povprečno časovno zapletenost O (n2). Zaradi tega razvrstitev mehurčkov ni primerna za razvrščanje seznamov z velikim številom elementov. Toda zaradi svoje preprostosti se med uvodoma v algoritme naučijo razvrščanja mehurčkov.

Kaj je vrsta razvrščanja?

Vstavljanje vrstice je še en algoritem razvrščanja, ki deluje tako, da element v vhodni seznam vstavi v pravilen položaj na seznamu (ki je že razvrščen). Ta postopek se uporablja večkrat, dokler se seznam ne razvrsti. Pri vstavljanju se sortiranje izvede na mestu. Zato bodo po i iteraciji algoritma prvi vnosi i + 1 na seznamu razvrščeni, preostali pa na seznamu. Ob vsaki ponovitvi bo prvi element v neortiziranem delu seznama in vstavljen na pravilno mesto v razvrščenem delu seznama. Vstavljanje vrste ima povprečno časovno zapletenost O (n2). Zaradi tega vrsta vstavljanja ni primerna za razvrščanje velikih seznamov.

Kakšna je razlika med razvrstitvijo mehurčkov in vstavitvijo?

Čeprav imata tako algoritmi razvrščanja mehurčkov kot sortiranje vlogov povprečne časovne zapletenosti O (n2), je razvrstitev mehurčkov skoraj ves čas večja kot pri vstavljanju. To je posledica števila zamenjav, potrebnih v obeh algoritmih (vrste mehurčkov potrebujejo več izmenjav). Toda zaradi enostavnosti razvrščanja mehurčkov je njegova velikost kode zelo majhna. Obstaja tudi različica vrste vstavljanja, imenovana sorta lupine, ki ima časovno zapletenost O (n3 / 2), kar bi omogočilo njeno praktično uporabo. Poleg tega je sortiranje vstavljanja zelo učinkovito za razvrščanje "skoraj razvrščenih" seznamov v primerjavi z razvrstitvijo mehurčkov.