Võtmete erinevus – sisestuse sortimine vs valiku sortimine
Sisestamise sortimine ja valiku sortimine on kaks sortimisalgoritmi, mida kasutatakse andmekogu sortimiseks. Mõnikord on vaja andmeid järjestada kindlas järjekorras. Sorteerimisalgoritmid on mehhanismid andmete kogumi sortimiseks. Sorteerimisel järjestatakse andmed numbrilise või leksikograafilise järjekorra järgi. Kui andmed on õigesti sorteeritud, siis oleks lihtne andmeid kiiremini otsida. Kui telefoninumbrid telefonikataloogis ei ole järjestatud, on konkreetset telefoninumbrit raske leida. Samamoodi oleks sõnu väga raske leida, kui sõnaraamatus ei ole sõnu järjestatud tähestikulises järjekorras. Seetõttu on sorteerimine igapäevaelus kasulik. Arvutiteaduses on andmekogu sortimiseks olemas sortimisalgoritmid. Kaks sellist algoritmi on sisestamise sortimine ja valiku sortimine. Sisestamise sortimine on sortimisalgoritm, mis sorteerib massiivi elemente ükshaaval nihutades. Valiku sortimine on sortimisalgoritm, mis leiab massiivi väikseima elemendi ja vahetab elemendi esimese positsiooniga, seejärel leiab suuruselt teise elemendi ja vahetab selle teises positsioonis oleva elemendiga ning jätkab protsessi kuni kogu massiiv on sorteeritud. Peamine erinevus sisestussortimise ja valiku sortimise vahel on see, et sisestussortimine võrdleb kahte elementi korraga, samas kui valiku sortimine valib minimaalse elemendi kogu massiivist ja sorteerib selle.
Mis on sisestuse sortimine?
Sisestamise sortimine on võrdluspõhine sortimisalgoritm. Selle meetodi puhul otsitakse massiivist samm-sammult. Sorteerimata üksused teisaldatakse ja lisatakse massiivi sorteeritud alamloendisse. Sisestuse sortimise algoritmi saab selgitada järgmise näite abil.
Näiteks võtke algmassiiviks 77, 33, 44, 11, 88. Selle sorteerimisalgoritmi puhul on esimene samm praeguse elemendi valimine.
Praegune element on 77. Praegust elementi võrreldakse kõigi vasakpoolses servas olevate elementidega. 77 on esimene element ja vasakul küljel pole ühtegi elementi. Praeguse positsiooni indeks on 0.
Seejärel suurendatakse praeguse asukoha indeksit 1 võrra. Nüüd on indeks 1 ja praegune element on 33. Kui võrrelda seda vasakpoolse elemendiga, on see väiksem kui 77. Siis on mõlemad väärtused vahetatakse. Nüüd on 33 indeksis 0 ja 77 indeksis 1.
Nüüd on massiiv 33, 77, 44, 11, 88.
Jällegi suurendatakse indeksit. Indeks on 2 ja praegune element on 44. Seda võrreldakse vasakpoolses servas olevate elementidega. 44 on väiksem kui 77. Seega need kaks väärtust vahetatakse. Nüüd on massiiv 33, 44, 77, 11, 88. Kõiki vasakpoolseid elemente on vaja võrrelda. Nii et 44 võrreldakse 33-ga. 33 on väiksem kui 44. Nii et neid elemente pole vaja vahetada.
Nüüd on massiiv 33, 44, 77, 11, 88.
Jällegi suurendatakse indeksit. Indeks on 3 ja praegune element on 11. Seda võrreldakse kõigi vasakpoolsete elementidega. 11 on väiksem kui 77, nii et need kaks on vahetatud. Nüüd on massiiv 33, 44, 11, 77, 88. Võrreldes 11 ja 44, on 11 väiksem kui 44. Nii et need kaks on vahetatud. Nüüd on massiivid 33, 11, 44, 77, 88. Jällegi võrreldakse 11-ga 33. 11 on väiksem kui 33, nii et need kaks väärtust vahetatakse.
Nüüd on massiiv 11, 33, 44, 77, 88.
Indeksi suurendamine muudab indeksi 4-ni. Väärtus on 88. See on suurem kui 77. Seega pole vaja vahetada. Lõpuks on sorteeritud massiiv 11, 33, 44, 77, 88.
Joonis 01: Sisestuse sortimise näide
Sisestussortimise rakendamine on ül altoodud. Esialgne massiiv oli 77, 33, 44, 11, 88. Pärast sorteerimist annab see väljundi 11, 33, 44, 77, 88.
Mis on valiku sortimine?
Valimise sortimine on kohapealne võrdluspõhine sortimisalgoritm. Massiivid on jagatud osadeks. Sorteeritud osa on vasakpoolses otsas. Sorteerimata osa on paremas otsas. Esiteks tuleks leida väikseim väärtus. Seejärel vahetatakse see vasakpoolse elemendiga. Nüüd on see element sorteeritud massiivis. See protsess jätkab sortimata massiivi piiri liigutamist ühest elemendist paremale. Valiku sortimise algoritmi saab selgitada järgmise näitega.
Võtke näiteks algmassiiviks 77, 33, 44, 11, 88, 22. Selles sorteerimisalgoritmis leitakse massiivi väikseim. Väikseim element on 11. See vahetatakse massiivi 0-indeksi elemendiga.
Nüüd on massiiv 11, 33, 44, 77, 88, 22.
Kõige väiksem element on indeksis 0, seega 11 on nüüd sorteeritud. Ülejäänud elementidest on väikseim 22. See asendatakse indeksielemendiga 1st.
Nüüd on massiiv 11, 22, 44, 77, 88, 33.
Elemendid 11 ja 22 on juba sorteeritud. Ülejäänutest on väikseim väärtus 33. See asendatakse indeksielemendiga 2nd.
Nüüd on massiiv 11, 22, 33, 77, 88, 44.
Elemendid 11, 22 ja 33 on juba sorteeritud. Ülejäänutest on väikseim väärtus 44. See asendatakse indeksielemendiga 3rd.
Nüüd on massiiv 11, 22, 33, 44, 88, 66.
Elemendid 11, 22, 33, 44 on juba sorteeritud. Ülejäänud elemendid on 88 ja 66. Element 66 asendatakse indeksi elemendiga 4th.
Nüüd on massiiv 11, 22, 33, 44, 66, 88.
See on sorteeritud massiiv, mis kasutab valiku sortimisalgoritmi.
Joonis 02: Valiku sortimise näide
Sisestussortimise rakendamine on ül altoodud. Esialgne massiiv oli 77, 33, 44, 11, 88. Pärast sorteerimist annab see väljundi 11, 33, 44, 77, 88.
Milline on sisestussortimise ja valikusortimise sarnasus?
Nii sisestussortimine kui ka valiku sortimine on sortimisalgoritmid
Mis vahe on sisestussortimisel ja valikusortimisel?
Sisestuse sortimine vs valikusordimine |
|
| Sisestamise sortimine on sortimisalgoritm, mis sorteerib massiivi elemente ükshaaval nihutades. | Valimise sortimine on sortimisalgoritm, mis leiab massiivi väikseima elemendi ja vahetab elemendi esimese positsiooniga, seejärel leiab suuruselt teise elemendi ja vahetab selle teises positsioonis oleva elemendiga ning jätkab protsessi kuni kogu massiiv on sorteeritud. |
| Töötlemine | |
| Sisestussortimise eesmärk on sortida alamloendit, võrreldes kahte elementi, kuni kogu massiiv on sorteeritud. | Valimise sortimine valib minimaalse elemendi ja vahetab selle esimese positsiooniga, valige uuesti miinimum ülejäänute jaoks ja vahetage see teise positsiooniga ning jätkake seda protsessi lõpuni. |
| Stabiilsus | |
| Sisestamise sortimine on stabiilne sortimisalgoritm. | Valimise sortimine ei ole stabiilne sortimisalgoritm. |
Kokkuvõte – sisestuse sortimine vs valik sortimine
Mõnikord on vaja andmeid sortida. Arvutiteaduses on andmete sortimiseks algoritmid. Selles artiklis käsitleti kahte sortimisalgoritmi, milleks on sisestamise sortimine ja valiku sortimine. Sisestamise sortimine on sortimisalgoritm, mis sorteerib massiivi elemente ükshaaval nihutades. Valiku sortimine on sortimisalgoritm, mis leiab massiivi väikseima elemendi ja vahetab elemendi esimese positsiooniga, seejärel leiab suuruselt teise elemendi ja vahetab selle teises positsioonis oleva elemendiga ning jätkab protsessi kuni kogu massiiv on sorteeritud. Sisestussortimise ja valiku sortimise erinevus seisneb selles, et sisestussortimine võrdleb kahte elementi korraga, samas kui valiku sortimine valib kogu massiivist minimaalse elemendi ja sorteerib selle.
Laadige PDF-fail alla jaotisest Sisestussortimine vs valiksortimine
Saate alla laadida selle artikli PDF-versiooni ja kasutada seda võrguühenduseta kasutamiseks vastav alt tsitaadi märkusele. Laadige PDF-versioon alla siit: Erinevused sisestuse ja valiku sortimise vahel
