Erinevus mullide sortimise ja valiku sortimise vahel

Mullide sortimine vs valiku sortimine

Mullide sortimine on sortimisalgoritm, mis toimib korduvalt sorteeritavat loendit läbides, kõrvutades külgnevate elementide paari. Kui paar elementi on vales järjekorras, vahetatakse need omavahel õiges järjekorras. Seda läbimist korratakse, kuni edasisi vahetusi pole vaja. Valiku sortimine on ka sortimisalgoritm, mis algab nimekirjast minimaalse elemendi leidmisega ja esimese elemendiga vahetamisega. Seda protsessi korratakse ülejäänud nimekirja osas, asetades vahetatud elemendid järjekorda.

Mis on mullide sortimine?

Mullide sortimine on sortimisalgoritm, mis toimib korduvalt sorteeritavat loendit läbides, kõrvutades külgnevate elementide paari. Kui paar elementi on vales järjekorras, vahetatakse need omavahel õiges järjekorras. Seda läbimist korratakse, kuni täiendavaid vahetusi pole vaja (see tähendab, et loend on sorteeritud). Kuna loendi väiksemad elemendid tõusevad tippu, kui mull pinnale kerkib, antakse sellele nimi mullide sortimine. Mullide sortimine on väga lihtne sortimisalgoritm, kuid selle n-elemendiga loendi sortimisel on juhtumi ajaline keerukus keskmiselt O (n2). Seetõttu ei sobi mullide sortimine suure hulga elementidega loendite sortimiseks. Kuid lihtsuse tõttu õpetatakse mullide sortimist algoritmide tutvustamisel.

Mis on valiku sortimine?

Valiku sortimine on ka teine ​​sortimisalgoritm, mis algab nimekirjast minimaalse elemendi leidmisega ja esimese elemendiga vahetamisega. Seejärel leitakse minimaalne element nimekirja ülejäänud osast (teisest elemendist kuni viimase elemendini loendis) ja vahetatakse see teise elemendiga. Seda protsessi korratakse ülejäänud nimekirja osas, asetades vahetatud elemendid järjekorda. Nii et sortimise valimisel jaguneb algoritmi mis tahes etapis loend kaheks osaks, kus üks osa sisaldab sorteeritud elemente ja teine ​​osa sorteerimata elemente. Algoritmi edenedes kasvab sorteeritud loend vasakult paremale. Valiku sortimisel on ka juhtumi ajaline keerukus O (n2). Seetõttu ei sobi see ka suurte nimekirjade sorteerimiseks.

Mis vahe on mullide sortimisel ja valiku sortimisel??

Ehkki nii mullide sortimise kui ka valiku sortimise algoritmidel on juhtumite ajaline keerukus keskmiselt O (n2), on mullide sortimine peaaegu alati valiku sorteerimisega edestatud. Selle põhjuseks on kahe algoritmi jaoks vajalike vahetustehingute arv (mullide sorteerimine vajab rohkem vahetustehinguid). Kuid mulli sortimise lihtsuse tõttu on selle koodi suurus väga väike. Stabiilsus on nende kahe algoritmi teine ​​erinevus. Stabiilne sortimisalgoritm on sortimisalgoritm, mis säilitab kirjete järjekorra, kui loend sisaldab võrdse väärtusega elemente. Selles mõttes ei ole valiku sortimine stabiilne algoritm, samas kui mullide sortimine on stabiilne algoritm.