Gruntle Software & Testing

Įterpimo rūšiavimas C++ kalba su pavyzdžiais

Autorius Stewart TristianPaskelbta Paskelbta kategorijoje Gidai

Išsamus žvilgsnis į įterpimo rūšiavimą su klasikiniais pavyzdžiais.

Įterpimo rūšiavimas - tai rūšiavimo metodas, kurį galima palyginti su tuo, kaip mes žaidžiame kortomis rankose. Panašiai, kaip į kaladę įdedame bet kurią kortą arba ją išimame, veikia ir įterpimo rūšiavimas.

Įterpimo rūšiavimo algoritmo metodas yra efektyvesnis už burbulinio rūšiavimo ir atrankinio rūšiavimo metodus, tačiau mažiau efektyvus už kitus metodus, pavyzdžiui, "Quicksort" ir "Merge sort".

Apžvalga

Taikydami įterpimo rūšiavimo metodą, pradedame nuo antrojo elemento, palyginame jį su pirmuoju elementu ir padedame jį į reikiamą vietą. Tada šį procesą atliekame su kitais elementais.

Kiekvieną elementą palyginame su visais ankstesniais elementais ir įdedame arba įterpiame elementą į reikiamą vietą. Įterpimo rūšiavimo metodas labiau tinka mažesnį elementų skaičių turintiems masyvams. Jis taip pat naudingas rūšiuojant susietus sąrašus.

Susieti sąrašai turi rodyklę į kitą elementą (viengubai susieto sąrašo atveju) ir rodyklę į ankstesnį elementą (dvigubai susieto sąrašo atveju). Todėl susietam sąrašui lengviau įgyvendinti įterpimo rūšiavimą.

Šioje pamokoje išnagrinėkime viską apie įterpimo rūšiavimą.

Bendrasis algoritmas

1 žingsnis : Pakartokite 2-5 veiksmus, kai K = 1-N-1

2 žingsnis : set temp = A[K]

3 žingsnis : rinkinys J = K - 1

4 žingsnis : Kartoti, kol temp <=A[J]

nustatyti A[J + 1] = A[J]

nustatyti J = J - 1

[vidinio ciklo pabaiga]

5 veiksmas : nustatyti A[J + 1] = temp

[ciklo pabaiga]

6 veiksmas : išeiti

Taigi, taikydami įterpimo rūšiavimo metodą, pradedame nuo antrojo elemento, nes darome prielaidą, kad pirmasis elementas visada yra surūšiuotas. Tada nuo antrojo elemento iki paskutiniojo elemento kiekvieną elementą lyginame su visais ankstesniais elementais ir pastatome tą elementą į reikiamą vietą.

Pseudokodas

Toliau pateikiamas įterpimo rūšiavimo pseudokodas. 

 procedūra insertionSort(array,N ) array - rūšiuojamas masyvas N- elementų skaičius begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array[i] freePosition = i //nustatykite laisvą vietą elementui įterpti whilefreePosition> 0 and array[freePosition -1]>insert_val do: array [freePosition] = array [freePosition -1] freePosition = freePosition -1 end while //įterpkite elementąskaičius laisvoje pozicijoje masyvas [freePosition] = insert_val end for end procedure end procedure

Pirmiau pateiktas įterpimo rūšiavimo pseudokodas, toliau šį metodą iliustruosime toliau pateiktame pavyzdyje.

Iliustracija

Rūšiuojamas masyvas yra toks:

Dabar kiekviename perėjime dabartinį elementą lyginame su visais ankstesniais elementais. Taigi pirmajame perėjime pradedame nuo antrojo elemento.

Taigi, norint visiškai surūšiuoti masyvą, kuriame yra N elementų, reikia N kartų.

Pirmiau pateiktą iliustraciją galima apibendrinti lentelės forma:

Perduoti Nerūšiuotas sąrašas palyginimas Rūšiuotas sąrašas
1 {12,3,5,10,8,1} {12,3} {3,12,5,10,8,1}
2 {3,12,5,10,8,1} {3,12,5} {3,5,12,10,8,1}
3 {3,5,12,10,8,1} {3,5,12,10} {3,5,10,12,8,1}
4 {3,5,10,12,8,1} {3,5,10,12,8} {3,5,8,10,12,1}
5 {3,5,8,10,12,1} {3,5,8,10,12,1} {1,3,5,8,10,12}
6 {} {} {1,3,5,8,10,12}

Kaip parodyta pirmiau pateiktoje iliustracijoje, pradedame nuo 2-ojo elemento, nes darome prielaidą, kad pirmasis elementas visada yra surūšiuotas. Taigi pradedame lyginti antrąjį elementą su pirmuoju ir sukeičiame pozicijas, jei antrasis elementas yra mažesnis už pirmąjį.

Šis palyginimo ir sukeitimo procesas padeda du elementus į jiems tinkamas vietas. Toliau lyginame trečiąjį elementą su ankstesniais (pirmuoju ir antruoju) elementais ir atliekame tą pačią procedūrą, kad trečiasis elementas atsidurtų tinkamoje vietoje.

Tokiu būdu kiekvieno perėjimo metu vieną elementą dedame į jo vietą. Pirmojo perėjimo metu į jo vietą dedame antrąjį elementą. Taigi apskritai, norint N elementų padėti į reikiamą vietą, reikia N-1 perėjimų.

Toliau pademonstruosime įterpimo rūšiavimo metodo įgyvendinimą C++ kalba.

C++ pavyzdys 

 #include using namespace std; int main () { int myarray[10] = { 12,4,3,1,15,45,33,21,10,2}; cout<<"\nĮvesties sąrašas yra \n"; for(int i=0;i<10;i++) { cout < ="" 
 Išvestis: 
 Įvesties sąrašas yra 
 12 4 3 1 15 45 33 21 10 2 
 Rūšiuotas sąrašas yra 
 1 2 3 4 10 12 15 21 33 45 
 Toliau pamatysime "Java" įterpimo rūšiavimo metodo įgyvendinimą. 
 "Java" pavyzdys 
 public class Main { public static void main(String[] args) { int[] myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println("Įvestas elementų sąrašas..."); for(int i=0;i<10;i++) { System.out.print(myarray[i] + " "); } for(int k=1; k=0 && temp <= myarray[j]) { myarray[j+1] = myarray[j]; j = j-1; } myarray[j+1] = temp; } System.out.println("Išrūšiuotas elementų sąrašas..."); for(inti=0;i<10;i++) { System.out.print(myarray[i] + " "); } } } } 
 Išvestis: 
 Įvesties elementų sąrašas ... 
 12 4 3 1 15 45 33 21 10 2 
 surūšiuotas elementų sąrašas ... 
 1 2 3 4 10 12 15 21 33 45 
 Abiejose realizacijose matome, kad rūšiavimą pradedame nuo 2-ojo masyvo elemento (ciklo kintamasis j = 1) ir pakartotinai lyginame dabartinį elementą su visais ankstesniais elementais, o tada rūšiuojame elementą, kad jis atsidurtų teisingoje vietoje, jei dabartinis elementas nesutampa su visais ankstesniais elementais. 
 Įterpimo rūšiavimas veikia geriausiai ir jį galima atlikti per mažiau perėjimų, jei masyvas yra iš dalies surūšiuotas. Tačiau didėjant sąrašui jo našumas mažėja. Kitas įterpimo rūšiavimo privalumas yra tas, kad jis yra stabilus rūšiavimas, t. y. išlaiko vienodų elementų tvarką sąraše. 
 Įterpimo rūšiavimo algoritmo sudėtingumo analizė 
 Iš pateikto pseudokodo ir iliustracijos matyti, kad įterpimo rūšiavimas yra efektyviausias algoritmas, palyginti su burbuliukų rūšiavimu arba atrankos rūšiavimu. Vietoj for ciklo ir esamų sąlygų jis naudoja while ciklą, kuris neatlieka jokių papildomų veiksmų, kai masyvas surūšiuotas. 
 Tačiau net jei surūšiuotą masyvą perduosime įterpimo rūšiavimo metodui, jis vis tiek vykdys išorinį for ciklą, todėl jau surūšiuotam masyvui surūšiuoti reikės n žingsnių. Dėl to geriausias įterpimo rūšiavimo laiko sudėtingumas yra tiesinė N funkcija, kur N yra elementų skaičius masyve. 
 Taigi toliau pateikiami įvairūs įterpimo rūšiavimo technikos sudėtingumo aspektai: 
 Blogiausio atvejo laiko sudėtingumas  O(n 2 ) 
 Geriausio atvejo laiko sudėtingumas  O(n) 
 Vidutinis laiko sudėtingumas  O(n 2 ) 
 Erdvės sudėtingumas  O(1) 
 Nepaisant šių sudėtingumų, vis tiek galime daryti išvadą, kad įterpimo rūšiavimas yra efektyviausias algoritmas, palyginti su kitais rūšiavimo metodais, pavyzdžiui, burbuliniu rūšiavimu ir atrankos rūšiavimu. 
 Išvada 
 Įterpimo rūšiavimas yra efektyviausias iš visų trijų iki šiol aptartų metodų. Čia darome prielaidą, kad pirmasis elementas yra surūšiuotas, tada kiekvieną elementą pakartotinai lyginame su visais ankstesniais elementais ir tada einamąjį elementą patalpiname į reikiamą vietą masyve. 
 Šioje pamokoje, aptardami įterpimo rūšiavimą, pastebėjome, kad elementus lyginame naudodami prieaugį 1, be to, jie yra gretimi. Dėl šios savybės reikia daugiau perėjimų, kad gautume surūšiuotą sąrašą. 
 Artimiausioje pamokoje aptarsime "Shell sort", kuris yra patobulintas, palyginti su atrankos rūšiavimu. 
 Atliekant "shell sort" įvedamas kintamasis, vadinamas "inkrementu" arba "tarpu", kuriuo naudodamiesi sąrašą padalijame į posričių sąrašus, kuriuose yra nesusijusių elementų, esančių vienas nuo kito. "Shell sort" reikalauja mažiau perėjimų, palyginti su "Insertion sort", be to, jis yra greitesnis. 
 Būsimose pamokose susipažinsime su dviem rūšiavimo būdais: "Quicksort" ir "Mergesort", kuriuose duomenų sąrašams rūšiuoti naudojama strategija "Skaldyk ir valdyk".
Slinkti į viršų