Gruntle Software & Testing

Ievietošanas šķirošana C++ ar piemēriem

Autors Stewart TristianPublicēts Publicēts kategorijā Ceļveži

Padziļināts skatījums uz iestarpināšanas šķirošanu ar klasiskiem piemēriem.

Ievietošanas šķirošana ir šķirošanas paņēmiens, ko var aplūkot līdzīgi kā mēs spēlējam kārtis ar rokām. Līdzīgi kā mēs ievietojam jebkuru kārti kāršu komplektā vai izņemam to, līdzīgi darbojas arī ievietošanas šķirošana.

Ievietošanas šķirošanas algoritma metode ir efektīvāka par burbuļveida šķirošanas un atlases šķirošanas metodēm, bet ir mazāk efektīva nekā citas metodes, piemēram, Quicksort un Merge sort.

Pārskats

Ievietošanas šķirošanas tehnikā mēs sākam ar otro elementu, salīdzinām to ar pirmo elementu un ievietojam to pareizā vietā. Pēc tam šo procesu veicam arī nākamajiem elementiem.

Mēs salīdzinām katru elementu ar visiem iepriekšējiem elementiem un ievietojam vai ievietojam elementu tā pareizajā pozīcijā. Ievietošanas šķirošanas paņēmiens ir lietderīgāks masīviem ar mazāku elementu skaitu. Tas ir noderīgs arī saistīto sarakstu šķirošanai.

Saistītajos sarakstos ir rādītājs uz nākamo elementu (vienlaidu saraksta gadījumā) un rādītājs arī uz iepriekšējo elementu (divkārši saistītā saraksta gadījumā). Tādējādi ir vieglāk īstenot ievietošanas šķirošanu saistītajiem sarakstiem.

Šajā pamācībā izpētīsim visu par iestarpināšanas šķirošanu.

Vispārīgais algoritms

1. solis : Atkārtojiet 2. līdz 5. darbību K = 1 līdz N-1.

2. solis : set temp = A[K]

3. solis : kopa J = K - 1

4. solis : Atkārtot, kamēr temp <=A[J]

komplekts A[J + 1] = A[J]

J = J - 1

[iekšējās cilpas beigas]

5. solis : komplekts A[J + 1] = temp

[cilpas beigas]

6. solis : izeja

Tādējādi ievietošanas šķirošanas paņēmienā mēs sākam ar otro elementu, jo pieņemam, ka pirmais elements vienmēr ir sakārtots. Tad no otrā elementa līdz pēdējam elementam mēs salīdzinām katru elementu ar visiem tā iepriekšējiem elementiem un novietojam šo elementu pareizajā pozīcijā.

Pseidokods

Ievietošanas šķirošanas pseidokods ir dots tālāk. 

 procedūra insertionSort(array,N ) array - šķirojamais masīvs N- elementu skaits begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array[i] freePosition = i //lokalizēt brīvu pozīciju elementa ievietošanai whilefreePosition> 0 and array[freePosition -1]>insert_val do: array [freePosition] = array [freePosition -1] freePosition = freePosition -1 end while //ievietotnumurs brīvajā pozīcijā masīvs [freePosition] = insert_val end for end procedure end procedure

Iepriekš ir dots pseidokods Insertion sort, bet tālāk mēs ilustrēsim šo paņēmienu nākamajā piemērā.

Ilustrācija

Šķirotais masīvs ir šāds:

Tagad katrā piegājienā mēs salīdzinām pašreizējo elementu ar visiem iepriekšējiem elementiem. Tātad pirmajā piegājienā mēs sākam ar otro elementu.

Tādējādi, lai pilnībā sakārtotu masīvu, kurā ir N elementu, mums ir nepieciešams N skaits piegājienu.

Iepriekš minēto ilustrāciju var apkopot tabulas veidā:

Pass Nesašķirots saraksts salīdzinājums Kārtotais saraksts
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}

Kā parādīts iepriekšējā attēlā, mēs sākam ar 2. elementu, jo pieņemam, ka pirmais elements vienmēr ir sakārtots. Tātad mēs sākam ar otrā elementa salīdzināšanu ar pirmo elementu un apmainām pozīciju, ja otrais elements ir mazāks par pirmo.

Šis salīdzināšanas un apmainīšanas process novieto divus elementus to pareizajās vietās. Tālāk mēs salīdzinām trešo elementu ar tā iepriekšējiem (pirmo un otro) elementiem un veicam to pašu procedūru, lai novietotu trešo elementu pareizajā vietā.

Šādā veidā katrā gājienā mēs novietojam vienu elementu tā vietā. Pirmajā gājienā mēs novietojam otro elementu tā vietā. Tādējādi kopumā, lai novietotu N elementu to pareizajā vietā, mums ir nepieciešami N-1 gājieni.

Tālāk mēs demonstrēsim ievietošanas šķirošanas tehnikas implementāciju C++ valodā.

C++ piemērs 

 #include using namespace std; int main () { int myarray[10] = { 12,4,3,1,15,45,33,21,10,2}; cout<<"\nIevades saraksts ir \n"; for(int i=0;i<10;i++) { cout < ="" 
 Izvades rezultāts: 
 Ievades saraksts ir 
 12 4 3 1 15 45 33 21 10 2 
 Sarindots saraksts ir 
 1 2 3 4 10 12 15 21 33 45 
 Tālāk apskatīsim Ievietošanas šķirošanas metodes Java implementāciju. 
 Java piemērs 
 publiskā klase Main { public static void main(String[] args) { int[] myarray = {12,4,3,3,1,15,45,33,21,10,2}; System.out.println("Ievadā elementu saraksts ..."); 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("Izšķirtu elementu saraksts ..."); for(inti=0;i<10;i++) { System.out.print(myarray[i] + " "); } } } } } 
 Izvades rezultāts: 
 Ievades elementu saraksts ... 
 12 4 3 1 15 45 33 21 10 2 
 sakārtots elementu saraksts ... 
 1 2 3 4 10 12 15 21 33 45 
 Abās implementācijās redzams, ka mēs sākam šķirošanu no masīva 2. elementa (cikla mainīgais j = 1) un atkārtoti salīdzinām pašreizējo elementu ar visiem iepriekšējiem elementiem un pēc tam šķirojam elementu, lai to novietotu pareizajā pozīcijā, ja pašreizējais elements nav sakārtots ar visiem iepriekšējiem elementiem. 
 Ievietošanas šķirošana darbojas vislabāk, un to var pabeigt ar mazāku skaitu piegājienu, ja masīvs ir daļēji sakārtots. Taču, pieaugot sarakstam, tās veiktspēja samazinās. Vēl viena ievietošanas šķirošanas priekšrocība ir tā, ka tā ir stabila šķirošana, kas nozīmē, ka tā saglabā vienādu elementu kārtību sarakstā. 
 Ievietošanas šķirošanas algoritma sarežģītības analīze 
 No pseidokoda un ilustrācijas iepriekš redzams, ka ievietošanas šķirošana ir efektīvākais algoritms, salīdzinot ar burbuļveida šķirošanu vai atlases šķirošanu. Tā vietā, lai izmantotu for cilpu un pašreizējos nosacījumus, tiek izmantota while cilpa, kas neveic papildu darbības, kad masīvs ir sakārtots. 
 Tomēr, pat ja mēs nododam sakārtotu masīvu iestarpināšanas šķirošanas metodei, tā joprojām izpildīs ārējo for cilpu, tādējādi jau sakārtota masīva sakārtošanai būs nepieciešams n soļu skaits. Tas padara iestarpināšanas šķirošanas labāko laika sarežģītību par lineāru funkciju no N, kur N ir elementu skaits masīvā. 
 Tādējādi turpmāk ir norādītas dažādas sarežģītības iestarpināšanas šķirošanas tehnikai: 
 Sliktākā gadījuma laika sarežģītība  O(n 2 ) 
 Labākā gadījuma laika sarežģītība  O(n) 
 Vidējā laika sarežģītība  O(n 2 ) 
 Kosmosa sarežģītība  O(1) 
 Neraugoties uz šīm sarežģītībām, mēs joprojām varam secināt, ka Insertion sort ir visefektīvākais algoritms, salīdzinot ar citām šķirošanas metodēm, piemēram, Bubble sort un Selection sort. 
 Secinājums 
 Ievietošanas šķirošana ir visefektīvākā no visām trim līdz šim aplūkotajām metodēm. Šeit mēs pieņemam, ka pirmais elements ir sakārtots, un pēc tam katru elementu atkārtoti salīdzinām ar visiem iepriekšējiem elementiem un pēc tam novietojam pašreizējo elementu tā pareizajā pozīcijā masīvā. 
 Šajā pamācībā, aplūkojot Insertion sort, mēs pamanījām, ka mēs salīdzinām elementus, izmantojot inkrementu 1, kā arī tie ir blakusesoši. Šī īpašība rada nepieciešamību pēc vairāk gājieniem, lai iegūtu sakārtotu sarakstu. 
 Nākamajā pamācībā mēs aplūkosim "Shell sort", kas ir uzlabojums salīdzinājumā ar Atlases šķirošanu. 
 Šķirošanā ar čaulu mēs ieviešam mainīgo, ko sauc par "inkrementu" vai "atstarpi", ar kura palīdzību mēs sadalām sarakstu apakšsarakstos, kuros ir nesaskanīgi elementi, kas atrodas "atstarpē" cits no cita. Salīdzinot ar iestarpināšanas šķirošanu, čaulu šķirošanai ir nepieciešams mazāk gājienu, un tā ir arī ātrāka. 
 Turpmākajās pamācībās mēs iepazīsimies ar divām šķirošanas metodēm - "Quicksort" un "Mergesort", kurās datu sarakstu šķirošanai tiek izmantota stratēģija "Sadal un valdi".
Ritināt uz augšu