Ključna razlika – Razvrščanje z vstavljanjem proti razvrščanju z izbiro
Razvrščanje z vstavljanjem in razvrščanje z izborom sta dva algoritma za razvrščanje, ki se uporabljata za razvrščanje zbirke podatkov. Včasih je treba podatke urediti v določenem vrstnem redu. Algoritmi za razvrščanje so mehanizmi za razvrščanje nabora podatkov. Pri razvrščanju so podatki urejeni po numeričnem ali leksikografskem vrstnem redu. Če so podatki pravilno razvrščeni, bi bilo lažje hitreje iskati podatke. Če telefonske številke v telefonskem imeniku niso razvrščene, bi bilo težko najti določeno telefonsko številko. Na enak način, če besede v slovarju niso urejene po abecednem vrstnem redu, bi bilo zelo težko najti besede. Zato je razvrščanje koristno v vsakdanjem življenju. V računalništvu obstajajo algoritmi za razvrščanje zbirke podatkov. Dva taka algoritma sta razvrščanje z vstavljanjem in razvrščanje z izborom. Razvrščanje z vstavljanjem je algoritem za razvrščanje, ki razvršča matriko s premikanjem elementov enega za drugim. Izbirno razvrščanje je algoritem za razvrščanje, ki najde najmanjši element v nizu in zamenja element s prvim položajem, nato poišče drugi najmanjši element in ga zamenja z elementom na drugem položaju ter nadaljuje postopek, dokler ni razvrščen celoten niz. Ključna razlika med razvrščanjem z vstavljanjem in razvrščanjem izbire je, da razvrščanje z vstavljanjem primerja dva elementa hkrati, medtem ko razvrščanje izbire izbere najmanjši element iz celotne matrike in ga razvrsti.
Kaj je razvrščanje z vstavljanjem?
Razvrščanje z vstavljanjem je algoritem za razvrščanje, ki temelji na primerjavi na mestu. Pri tej metodi se matrika išče korak za korakom. Nerazvrščeni elementi se premaknejo in vstavijo v razvrščeni podseznam matrike. Algoritem razvrščanja pri vstavljanju je mogoče razložiti z naslednjim primerom.
Na primer, vzemite začetno matriko kot 77, 33, 44, 11, 88. V tem algoritmu za razvrščanje je prvi korak izbira trenutnega elementa.
Trenutni element je 77. Trenutni element se primerja z vsemi elementi na levi strani. 77 je prvi element in na levi strani ni elementov. Indeks trenutnega položaja je 0.
Nato se indeks trenutne pozicije poveča za 1. Zdaj je indeks 1, trenutni element pa 33. Če ga primerjamo z elementom na levi, je manjši od 77. Nato obe vrednosti se zamenjajo. Zdaj je 33 v indeksu 0, 77 pa v indeksu1.
Zdaj je niz 33, 77, 44, 11, 88.
Spet se indeks poveča. Indeks je 2, trenutni element pa 44. Primerjamo ga z elementi na levi strani. 44 je manj kot 77. Torej sta ti dve vrednosti zamenjani. Sedaj je niz 33, 44, 77, 11, 88. Primerjati je potrebno vse elemente na levi strani. Torej se 44 primerja s 33. 33 je manjši od 44. Teh elementov torej ni treba zamenjati.
Zdaj je niz 33, 44, 77, 11, 88.
Spet se indeks poveča. Indeks je 3, trenutni element pa 11. Primerja se z vsemi elementi na levi. 11 je manj kot 77, zato sta ti dve zamenjani. Zdaj je niz 33, 44, 11, 77, 88. Če primerjamo 11 in 44, je 11 manj kot 44. Ti dve sta torej zamenjani. Zdaj so nizi 33, 11, 44, 77, 88. Ponovno se 11 primerja s 33. 11 je manj kot 33, zato sta ti dve vrednosti zamenjani.
Zdaj je niz 11, 33, 44, 77, 88.
Povečanje indeksa bo indeks postavilo na 4. Vrednost je 88. Je višja od 77. Torej ni potrebe po zamenjavi. Končno je razvrščeni niz 11, 33, 44, 77, 88.
Slika 01: Primer razvrščanja pri vstavljanju
Izvedba razvrščanja vstavljanja je kot zgoraj. Začetna matrika je bila 77, 33, 44, 11, 88. Po razvrščanju daje izhod 11, 33, 44, 77, 88.
Kaj je razvrščanje izbire?
Razvrščanje z izbiro je algoritem za razvrščanje, ki temelji na primerjavi na mestu. Nizi so razdeljeni na odseke. Razvrščeni del je na levem koncu. Nerazvrščeni del je na desnem koncu. Najprej je treba najti najmanjšo vrednost. Nato se zamenja z levim elementom. Zdaj je ta element v razvrščeni matriki. Ta proces nadaljuje s premikanjem nerazvrščene meje polja od enega elementa v desno. Algoritem razvrščanja izbire je mogoče razložiti z naslednjim primerom.
Na primer, vzemite začetno matriko kot 77, 33, 44, 11, 88, 22. V tem algoritmu razvrščanja se najde najmanjša v matriki. Najmanjši element je 11. Zamenja se z elementom v indeksu 0 matrike.
Zdaj je niz 11, 33, 44, 77, 88, 22.
Najmanjši element je v indeksu 0, tako da je 11 zdaj razvrščen. Od preostalih elementov je najmanjši 22. Zamenja se z indeksnim elementom 1st.
Zdaj je niz 11, 22, 44, 77, 88, 33.
Elementa 11 in 22 sta že razvrščena. Od ostalih je najmanjša vrednost 33. Zamenja se z indeksnim elementom 2nd.
Zdaj je niz 11, 22, 33, 77, 88, 44.
Elementi 11, 22 in 33 so že razvrščeni. Od ostalih je najmanjša vrednost 44. Zamenja se z elementom indeksa 3rd.
Zdaj je niz 11, 22, 33, 44, 88, 66.
Elementi 11, 22, 33, 44 so že razvrščeni. Preostala elementa sta 88 in 66. Element 66 je zamenjan z indeksnim elementom 4th.
Zdaj je niz 11, 22, 33, 44, 66, 88.
To je razvrščena matrika z algoritmom razvrščanja izbire.
Slika 02: Primer razvrščanja izbire
Izvedba razvrščanja vstavljanja je kot zgoraj. Začetna matrika je bila 77, 33, 44, 11, 88. Po razvrščanju daje izhod 11, 33, 44, 77, 88.
Kakšna je podobnost med razvrščanjem z vstavljanjem in razvrščanjem z izbiro?
Razvrščanje z vstavljanjem in razvrščanje z izbiro sta algoritma za razvrščanje
Kakšna je razlika med razvrščanjem z vstavljanjem in razvrščanjem z izbiro?
Razvrščanje vstavljanja v primerjavi z razvrščanjem izbire |
|
| Razvrščanje z vstavljanjem je algoritem za razvrščanje, ki razvršča matriko s premikanjem elementov enega za drugim. | Izbirno razvrščanje je algoritem za razvrščanje, ki najde najmanjši element v matriki in zamenja element s prvim položajem, nato poišče drugi najmanjši element in ga zamenja z elementom na drugem položaju ter nadaljuje postopek do celotno polje je razvrščeno. |
| Proces | |
| Razvrščanje z vstavljanjem je razvrščanje podseznama s primerjavo dveh elementov, dokler ni razvrščeno celotno polje. | Izbirno razvrščanje izbere najmanjši element in ga zamenja s prvim položajem, znova izbere minimum za ostale in ga zamenja z drugim položajem ter nadaljuje ta postopek do konca. |
| Stabilnost | |
| Razvrščanje z vstavljanjem je stabilen algoritem za razvrščanje. | Razvrščanje izbire ni stabilen algoritem za razvrščanje. |
Povzetek – Razvrstitev vstavljanja proti razvrščanju izbire
Včasih je potrebno razvrstiti podatke. V računalništvu obstajajo algoritmi za razvrščanje podatkov. Ta članek je obravnaval dva algoritma za razvrščanje, in sicer razvrščanje z vstavljanjem in razvrščanje z izbiro. Razvrščanje z vstavljanjem je algoritem za razvrščanje, ki razvršča matriko s premikanjem elementov enega za drugim. Izbirno razvrščanje je algoritem za razvrščanje, ki najde najmanjši element v nizu in zamenja element s prvim položajem, nato poišče drugi najmanjši element in ga zamenja z elementom na drugem položaju ter nadaljuje postopek, dokler ni razvrščen celoten niz. Razlika med razvrščanjem z vstavljanjem in razvrščanjem po izboru je v tem, da razvrščanje z vstavljanjem primerja dva elementa hkrati, medtem ko razvrščanje po izboru izbere najmanjši element iz celotne matrike in ga razvrsti.
Prenesite PDF za Razvrščanje vstavljanja v primerjavi z razvrščanjem izbire
Različico PDF tega članka lahko prenesete in jo uporabite za namene brez povezave v skladu z opombo o citiranju. Tukaj prenesite različico PDF: Razlika med razvrščanjem vstavljanja in razvrščanjem izbire
