Erinevus mullide sortimise ja sisestamise sortimise vahel

Mullide sortimine ja sisestamise 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. Sisestus sortimine on ka sortimisalgoritm, mis toimib sisestades sisendloendisse elemendi juba sorteeritud loendis õigesse kohta. Seda protsessi rakendatakse korduvalt, kuni loend on sorteeritud.

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 sisestamise sortimine?

Sisestussorteerimine on veel üks sortimisalgoritm, mis toimib sisestusloendi elemendi lisamisega loendi õigesse kohta (see on juba sorteeritud). Seda protsessi rakendatakse korduvalt, kuni loend on sorteeritud. Sisestussortimisel sorteeritakse kohapeal. Seetõttu sorteeritakse pärast algoritmi i-ndat iteratsiooni esimesed i + 1 kirjed loendis ja ülejäänud loend sorteerimata. Igal iteratsioonil võetakse esimene sort nimekirja sortimata osas ja sisestatakse see loendi sorteeritud sektsiooni õigesse kohta. Sisestussortimisel on juhtumi ajaline keerukus O (n2). Seetõttu ei sobi sisestussorteerimine ka suurte nimekirjade sorteerimiseks.

Mis vahe on mullide sortimisel ja sisestamisel sortimisel?

Ehkki nii mullide sortimise kui ka sisestamise sortimise algoritmidel on juhtumi ajaline keerukus keskmiselt O (n2), on mullide sortimine peaaegu alati sisestussorteerimise korral parem. 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. Samuti on olemas sisestussorteerimise variant, mida nimetatakse kestasorteerimiseks, mille ajaline keerukus on O (n3 / 2), mis võimaldaks seda praktiliselt kasutada. Lisaks on sisestussortimine väga tõhus peaaegu peaaegu sorteeritud loendite sortimiseks, võrreldes mullide sortimisega.