Mulli sortimine vs valiksortimine
Mulli sortimine on sortimisalgoritm, mis toimib järjestatava loendi korduv alt läbikäimisel, võrreldes kõrvuti asetsevate elementide paare. Kui elementide paar on vales järjekorras, vahetatakse need õigesse järjekorda. Seda läbimist korratakse seni, kuni edasisi vahetusi pole vaja. Valiku sortimine on ka sortimisalgoritm, mis alustab loendist minimaalse elemendi leidmisest ja vahetamisest esimese elemendiga. Seda protsessi korratakse ülejäänud loendi jaoks, asetades vahetatud elemendid järjekorda.
Mis on mullsorteerimine?
Mulli sortimine on sortimisalgoritm, mis toimib järjestatava loendi korduv alt läbikäimisel, võrreldes kõrvuti asetsevate elementide paare. Kui elementide paar on vales järjekorras, vahetatakse need õigesse järjekorda. Seda läbimist korratakse seni, kuni enam vahetusi pole vaja (mis tähendab, et loend on sorteeritud). Kuna loendis olevad väiksemad elemendid tulevad mulli pinnale tulemisel ülaossa, antakse sellele nimi mulli sortimine. Mullsorteerimine on väga lihtne sortimisalgoritm, kuid n elemendiga loendi sortimisel on selle keskmine juhtumiaja keerukus O(n2). Seetõttu ei sobi mullsorteerimine suure hulga elementidega loendite sortimiseks. Kuid selle lihtsuse tõttu õpetatakse mullide sortimist algoritmide sissejuhatuse ajal.
Mis on valiku sortimine?
Valimise sortimine on ka teine sortimisalgoritm, mis algab loendist minimaalse elemendi leidmisest ja selle vahetamisest esimese elemendiga. Seejärel leitakse loendi ülejäänud osast minimaalne element (teisest elemendist kuni loendi viimase elemendini) ja vahetatakse teise elemendiga. Seda protsessi korratakse ülejäänud loendi jaoks, asetades vahetatud elemendid järjekorda. Nii et valiku sortimisel jagatakse loend igas algoritmi etapis kaheks osaks, millest üks sisaldab sorteeritud elemente ja teine osa sisaldab sortimata elemente. Algoritmi edenedes kasvab sorteeritud loend vasakult paremale. Valiku sorteerimisel on ka juhtumi keskmine keerukus O(n2). Seetõttu ei sobi see ka suurte loendite sortimiseks.
Mis vahe on mullsortimisel ja valiksortimisel?
Kuigi nii mullide sortimise kui ka valiku sortimise algoritmide juhtumite keskmine keerukus on O(n2), edestab mullide sortimine peaaegu alati valiku sortimist. See on tingitud kahe algoritmi jaoks vajalike vahetuste arvust (mulli sorteerimine vajab rohkem vahetustehinguid). Kuid mulli sortimise lihtsuse tõttu on selle koodi suurus väga väike. Stabiilsus on veel üks erinevus nende kahe algoritmi vahel. 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 mulli sortimine on stabiilne algoritm.
