Raktų skirtumas – įterpimo rūšiavimas ir pasirinkimo rūšiavimas
Įterpimo rūšiavimas ir pasirinkimo rūšiavimas yra du rūšiavimo algoritmai, naudojami duomenų rinkiniui rūšiuoti. Kartais reikia sutvarkyti duomenis tam tikra tvarka. Rūšiavimo algoritmai yra mechanizmai, skirti rūšiuoti duomenų rinkinį. Rūšiuojant duomenys išdėstomi skaitine arba leksikografine tvarka. Jei duomenys yra tinkamai surūšiuoti, duomenų paieška būtų greitesnė. Jei telefonų numeriai telefonų knygoje nėra surūšiuoti, būtų sunku rasti konkretų telefono numerį. Lygiai taip pat, jei žodžiai žodyne nėra išdėstyti abėcėlės tvarka, būtų labai sunku rasti žodžius. Todėl rūšiavimas yra naudingas kasdieniame gyvenime. Kompiuterių moksle yra rūšiavimo algoritmai, skirti rūšiuoti duomenų rinkinį. Du tokie algoritmai yra įterpimo rūšiavimas ir pasirinkimo rūšiavimas. Įterpimo rūšiavimas yra rūšiavimo algoritmas, kuris rūšiuoja masyvą perkeldamas elementus po vieną. Pasirinkimo rūšiavimas yra rūšiavimo algoritmas, kuris suranda mažiausią masyvo elementą ir pakeičia elementą su pirmąja pozicija, tada suranda antrą mažiausią elementą ir keičia jį su antroje pozicijoje esančiu elementu ir tęsia procesą, kol visas masyvas bus surūšiuotas.. Pagrindinis skirtumas tarp įterpimo rūšiavimo ir pasirinkimo rūšiavimo yra tas, kad įterpimo rūšiavimas lygina du elementus vienu metu, o pasirinkimo rūšiavimas parenka minimalų elementą iš viso masyvo ir jį surūšiuoja.
Kas yra įterpimo rūšiavimas?
Įterpimo rūšiavimas yra vietoje palyginimu pagrįstas rūšiavimo algoritmas. Šiuo metodu masyve ieškoma žingsnis po žingsnio. Nerūšiuoti elementai perkeliami ir įterpiami į surūšiuotą masyvo posąrašį. Įterpimo rūšiavimo algoritmą galima paaiškinti naudojant šį pavyzdį.
Pavyzdžiui, imkite pradinį masyvą kaip 77, 33, 44, 11, 88. Taikant šį rūšiavimo algoritmą pirmiausia reikia pasirinkti esamą elementą.
Dabartinis elementas yra 77. Dabartinis elementas lyginamas su visais elementais kairėje pusėje. 77 yra pirmasis elementas, o kairėje pusėje elementų nėra. Dabartinės padėties indeksas yra 0.
Tada dabartinės padėties indeksas padidinamas 1. Dabar indeksas yra 1, o dabartinis elementas yra 33. Lyginant jį su elementu kairėje, jis yra mažesnis nei 77. Tada abi šios reikšmės yra sukeisti. Dabar 33 yra indekse 0, o 77 yra 1 indekse.
Dabar masyvas yra 33, 77, 44, 11, 88.
Vėlgi indeksas padidinamas. Indeksas yra 2, o dabartinis elementas yra 44. Jis lyginamas su elementais kairėje pusėje. 44 yra mažesnis nei 77. Taigi šios dvi reikšmės sukeičiamos. Dabar masyvas yra 33, 44, 77, 11, 88. Būtina palyginti visus elementus kairėje. Taigi, 44 lyginamas su 33. 33 yra mažesnis nei 44. Taigi tų elementų keisti nereikia.
Dabar masyvas yra 33, 44, 77, 11, 88.
Vėlgi indeksas padidinamas. Indeksas yra 3, o dabartinis elementas yra 11. Jis lyginamas su visais elementais kairėje. 11 yra mažesnis nei 77, todėl tie du yra sukeisti. Dabar masyvas yra 33, 44, 11, 77, 88. Lyginant 11 ir 44, 11 yra mažesnis nei 44. Taigi tie du yra sukeisti. Dabar masyvai yra 33, 11, 44, 77, 88. Vėlgi 11 lyginamas su 33. 11 yra mažesnis nei 33, todėl šios dvi reikšmės yra sukeistos.
Dabar masyvas yra 11, 33, 44, 77, 88.
Padidinus indeksą, indeksas bus 4. Reikšmė yra 88. Ji didesnė nei 77. Taigi, keisti nereikia. Galiausiai surūšiuotas masyvas yra 11, 33, 44, 77, 88.
01 pav.: įterpimo rūšiavimo pavyzdys
Įterpimo rūšiavimas įgyvendinamas taip, kaip nurodyta aukščiau. Pradinis masyvas buvo 77, 33, 44, 11, 88. Surūšiavus gaunama išvestis 11, 33, 44, 77, 88.
Kas yra atrankos rūšiavimas?
Pasirinkimo rūšiavimas yra palyginimu pagrįstas rūšiavimo algoritmas. Masyvai suskirstyti į dalis. Išrūšiuota dalis yra kairiajame gale. Nerūšiuota dalis yra dešiniajame gale. Pirmiausia reikia rasti mažiausią vertę. Tada jis pakeičiamas kairiuoju elementu. Dabar šis elementas yra surūšiuotame masyve. Šis procesas tęsia nerūšiuotos masyvo ribos perkėlimą iš vieno elemento į dešinę. Pasirinkimo rūšiavimo algoritmą galima paaiškinti naudojant šį pavyzdį.
Pavyzdžiui, imkite pradinį masyvą kaip 77, 33, 44, 11, 88, 22. Šiame rūšiavimo algoritme randamas mažiausias masyve. Mažiausias elementas yra 11. Jis pakeičiamas masyvo indekso 0 elementu.
Dabar masyvas yra 11, 33, 44, 77, 88, 22.
Mažiausias elementas yra indekse 0, todėl 11 dabar surūšiuotas. Iš kitų elementų mažiausias yra 22. Jis pakeičiamas 1st indekso elementu.
Dabar masyvas yra 11, 22, 44, 77, 88, 33.
11 ir 22 elementai jau surūšiuoti. Iš visų kitų, mažiausia reikšmė yra 33. Ji pakeičiama indekso elementu 2nd.
Dabar masyvas yra 11, 22, 33, 77, 88, 44.
11, 22 ir 33 elementai jau surūšiuoti. Iš visų kitų, mažiausia reikšmė yra 44. Ji pakeičiama indekso elementu 3rd.
Dabar masyvas yra 11, 22, 33, 44, 88, 66.
11, 22, 33, 44 elementai jau surūšiuoti. Likę elementai yra 88 ir 66. Elementas 66 pakeičiamas 4th indekso elementu.
Dabar masyvas yra 11, 22, 33, 44, 66, 88.
Tai surūšiuotas masyvas naudojant pasirinkimo rūšiavimo algoritmą.
02 pav. Pasirinkimo rūšiavimo pavyzdys
Įterpimo rūšiavimas įgyvendinamas taip, kaip nurodyta aukščiau. Pradinis masyvas buvo 77, 33, 44, 11, 88. Surūšiavus gaunama išvestis 11, 33, 44, 77, 88.
Koks yra įterpimo rūšiavimo ir pasirinkimo rūšiavimo panašumas?
Ir įterpimo rūšiavimas, ir pasirinkimo rūšiavimas yra rūšiavimo algoritmai
Kuo skiriasi įterpimo rūšiavimas ir pasirinkimo rūšiavimas?
Įterpimo rūšiavimas prieš pasirinkimo rūšiavimą |
|
| Įterpimo rūšiavimas yra rūšiavimo algoritmas, kuris rūšiuoja masyvą perkeldamas elementus po vieną. | Pasirinkimo rūšiavimas yra rūšiavimo algoritmas, kuris suranda mažiausią elementą masyve ir pakeičia elementą su pirmąja pozicija, tada suranda antrą mažiausią elementą ir sukeičia jį su antroje pozicijoje esančiu elementu ir tęsia procesą iki visas masyvas surūšiuotas. |
| Procesas | |
| Įterpimo rūšiavimas yra skirtas rūšiuoti antrinį sąrašą lyginant du elementus, kol bus surūšiuotas visas masyvas. | Atrankos rūšiavimas parenka minimalų elementą ir sukeičia jį į pirmą vietą, vėl pasirinkite mažiausią likusiai vietai ir sukeiskite į antrąją vietą ir tęskite šį procesą iki pabaigos. |
| Stabilumas | |
| Įterpimo rūšiavimas yra stabilus rūšiavimo algoritmas. | Pasirinkimo rūšiavimas nėra stabilus rūšiavimo algoritmas. |
Santrauka – įterpimo rūšiavimas prieš pasirinkimo rūšiavimą
Kartais reikia rūšiuoti duomenis. Kompiuterių moksle yra duomenų rūšiavimo algoritmai. Šiame straipsnyje aptariami du rūšiavimo algoritmai, kurie yra įterpimo rūšiavimas ir pasirinkimo rūšiavimas. Įterpimo rūšiavimas yra rūšiavimo algoritmas, kuris rūšiuoja masyvą perkeldamas elementus po vieną. Pasirinkimo rūšiavimas yra rūšiavimo algoritmas, kuris suranda mažiausią masyvo elementą ir pakeičia elementą su pirmąja pozicija, tada suranda antrą mažiausią elementą ir keičia jį su antroje pozicijoje esančiu elementu ir tęsia procesą, kol visas masyvas bus surūšiuotas.. Skirtumas tarp įterpimo rūšiavimo ir pasirinkimo rūšiavimo yra tas, kad įterpimo rūšiavimas lygina du elementus vienu metu, o pasirinkimo rūšiavimas parenka minimalų elementą iš viso masyvo ir jį surūšiuoja.
Atsisiųskite įterpimo rūšiavimo ir pasirinkimo rūšiavimo PDF failą
Galite atsisiųsti šio straipsnio PDF versiją ir naudoti ją neprisijungus, kaip nurodyta citatos pastaboje. Atsisiųskite PDF versiją čia: Skirtumas tarp įterpimo rūšiavimo ir pasirinkimo rūšiavimo
