Mulli sortimine vs sisestussortimine
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. Sisestamise sortimine on ka sortimisalgoritm, mis toimib sisendloendi elemendi sisestamisega juba sorteeritud loendis õigesse kohta. Seda protsessi rakendatakse korduv alt, kuni loend on sorteeritud.
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 juhtumite keskmine keerukus O(n2). Sellest tulenev alt ei sobi mullsorteerimine suure hulga elementidega loendite sortimiseks. Kuid selle lihtsuse tõttu õpetatakse mullide sortimist algoritmide sissejuhatuse ajal.
Mis on sisestuse sortimine?
Sisestamise sortimine on teine sortimisalgoritm, mis toimib sisendloendi elemendi sisestamisega loendis õigesse kohta (mis on juba sorteeritud). Seda protsessi rakendatakse korduv alt, kuni loend on sorteeritud. Sisestussortimisel toimub sorteerimine kohapeal. Seetõttu sorteeritakse pärast algoritmi i-ndat iteratsiooni esimesed i+1 kirjed loendis ja ülejäänud loend jäetakse sorteerimata. Igal iteratsioonil võetakse loendi sortimata osa esimene element ja lisatakse see loendi sorteeritud jaotise õigesse kohta. Sisestussortimise keskmine juhtumiaja keerukus on O(n2). Seetõttu ei sobi sisestussortimine ka suurte loendite sortimiseks.
Mis vahe on mullsortimisel ja sisestussortimisel?
Kuigi nii mulli sortimise kui ka sisestamise sortimise algoritmide juhtumite keskmine keerukus on O(n2), edestab mullide sortimine peaaegu kogu aeg sisestussortimist. 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. Samuti on olemas sisestussortimise variant nimega shell sort, mille ajaline keerukus on O(n3/2), mis võimaldaks seda praktiliselt kasutada. Lisaks on sisestussortimine mulli sortimisega võrreldes väga tõhus peaaegu sorteeritud loendite sortimiseks.
