Gruntle Software & Testing

Sisestamine Sorteerimine C + + koos näidetega

Autor Stewart TristianPostitatud Postitatud kategoorias Juhendid

Põhjalik ülevaade sisestamise sorteerimisest klassikaliste näidetega.

Sisestussorteerimine on sorteerimistehnika, mida võib vaadelda nii, et me mängime kaardid käes. Nii nagu me sisestame mis tahes kaardi pakki või eemaldame selle, töötab sisestussorteerimine sarnaselt.

Insertion sorteerimise algoritmi tehnika on tõhusam kui Bubble sort ja Selection sort tehnika, kuid on vähem tõhus kui teised tehnikad nagu Quicksort ja Merge sort.

Ülevaade

Sisestussorteerimise tehnikas alustame teisest elemendist ja võrdleme seda esimese elemendiga ning paigutame selle õigesse kohta. Seejärel teostame seda protsessi järgmiste elementide puhul.

Võrdleme iga elementi kõigi eelnevate elementidega ja asetame või sisestame elemendi õigesse kohta. Sisestussorteerimise tehnika on otstarbekam väiksema arvu elementidega massiividel. See on kasulik ka seotud loendite sorteerimisel.

Seotud loenditel on osuti järgmisele elemendile (ühekordselt seotud loendi puhul) ja osuti ka eelmisele elemendile (kahekordselt seotud loendi puhul). Seega on seotud loendi puhul lihtsam rakendada sisestamise sorteerimist.

Uurime selles õpetuses kõike Insertion sorteerimise kohta.

Üldine algoritm

1. samm : Korrake samme 2 kuni 5, kui K = 1 kuni N-1.

2. samm : set temp = A[K]

3. samm : J = K - 1

4. samm : Repeat while temp <=A[J]

komplekt A[J + 1] = A[J]

määrata J = J - 1

[sisemise tsükli lõpp]

5. samm : komplekt A[J + 1] = temp

[ring lõppeb]

6. samm : exit

Seega alustame sisestussorteerimise tehnikas teisest elemendist, kuna eeldame, et esimene element on alati sorteeritud. Seejärel teisest elemendist kuni viimase elemendini võrdleme iga elementi kõigi eelnevate elementidega ja asetame selle elemendi õigesse positsiooni.

Pseudokood

Pseudokood sisestussorteerimiseks on esitatud allpool. 

 protseduur insertionSort(array,N ) array - sorteeritav array N- elementide arv begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array[i] freePosition = i //locate free position to insert the element whilefreePosition> 0 and array[freePosition -1]>insert_val do: array [freePosition] = array [freePosition -1] freePosition = freePosition -1 end while //insert thenumber vabas positsioonis array [freePosition] = insert_val end for end procedure

Ülaltoodud on pseudokood Insertion sorteerimiseks, järgmisena illustreerime seda tehnikat järgmises näites.

Illustratsioon

Sorteeritav massiivi on järgmine:

Nüüd võrdleme iga käigu puhul praegust elementi kõigi eelnevate elementidega. Seega alustame esimeses käigus teisest elemendist.

Seega vajame N arvu läbikäike, et sorteerida täielikult N arvu elemente sisaldav massiivi.

Ülaltoodud illustratsiooni võib kokku võtta tabeli kujul:

Pass Sorteerimata nimekiri võrdlus Sorteeritud nimekiri
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}

Nagu ülaltoodud joonisel näidatud, alustame 2. elemendist, kuna eeldame, et esimene element on alati sorteeritud. Seega alustame teise elemendi võrdlemisega esimese elemendiga ja vahetame positsiooni, kui teine element on väiksem kui esimene.

See võrdlemise ja vahetamise protsess paigutab kaks elementi oma õigetele kohtadele. Seejärel võrdleme kolmandat elementi oma eelnevate (esimese ja teise) elementidega ja teostame sama protseduuri, et paigutada kolmas element õigele kohale.

Sel viisil paigutame iga läbimise korral ühe elemendi oma kohale. Esimese läbimise korral paigutame teise elemendi oma kohale. Seega üldiselt vajame N elemendi õigele kohale paigutamiseks N-1 läbimist.

Järgnevalt demonstreerime Insertion sorteerimise tehnika rakendamist C++ keeles.

C++ näide 

 #include using namespace std; int main () { int myarray[10] = { 12,4,3,1,15,45,33,21,10,2}; cout<<"\nInput list is \n"; for(int i=0;i<10;i++) { cout < ="" 
 Väljund: 
 Sisendnimekiri on 
 12 4 3 1 15 45 33 21 10 2 
 Sorteeritud nimekiri on 
 1 2 3 4 10 12 15 21 33 45 
 Järgnevalt näeme Insertion sorteerimise tehnika Java implementatsiooni. 
 Java näide 
 public class Main { public static void main(String[] args) { int[] myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println("Sisestatud elementide nimekiri ..."); 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("\sortitud elementide nimekiri ..."); for(inti=0;i<10;i++) { System.out.print(myarray[i] + " "); } } } 
 Väljund: 
 Elementide sisendnimekiri ... 
 12 4 3 1 15 45 33 21 10 2 
 sorteeritud elementide nimekiri ... 
 1 2 3 4 10 12 15 21 33 45 
 Mõlemas rakenduses näeme, et alustame sorteerimist massiivi 2. elemendist (tsükli muutuja j = 1) ja võrdleme korduvalt praegust elementi kõigi eelnevate elementidega ning seejärel sorteerime elemendi õigesse kohta, kui praegune element ei ole järjekorras kõigi eelnevate elementidega. 
 Insertion sorteerimine töötab kõige paremini ja seda saab teha vähemate käikudega, kui massiiv on osaliselt sorteeritud. Kuid kui nimekiri kasvab suuremaks, väheneb selle jõudlus. Insertion sorteerimise teine eelis on see, et see on Stable sort, mis tähendab, et see säilitab võrdsete elementide järjekorra nimekirjas. 
 Insertioni sorteerimise algoritmi keerukusanalüüs 
 Pseudokoodist ja ülaltoodud illustratsioonist nähtub, et sisestussorteerimine on efektiivsem algoritm, kui seda võrrelda mullasorteerimise või valikusorteerimisega. Selle asemel, et kasutada for-silmust ja olemasolevaid tingimusi, kasutatakse while-silmust, mis ei tee enam mingeid täiendavaid samme, kui massiiv on sorteeritud. 
 Kuid isegi kui me anname sorteeritud massiivi üle Insertion sort tehnikale, täidab see ikkagi välise for-silmuse, nõudes seega n sammu, et sorteerida juba sorteeritud massiivi. See muudab insertion sort tehnika parima ajakomplekssuse lineaarseks funktsiooniks N, kus N on massiivi elementide arv. 
 Seega on allpool esitatud Insertion sorteerimise tehnika erinevad keerukused: 
 Halvimal juhul ajaline keerukus  O(n 2 ) 
 Parimal juhul ajaline keerukus  O(n) 
 Keskmine ajaline keerukus  O(n 2 ) 
 Ruumi keerukus  O(1) 
 Vaatamata nendele keerukustele võime siiski järeldada, et Insertion sort on kõige tõhusam algoritm võrreldes teiste sorteerimistehnikatega nagu Bubble sort ja Selection sort. 
 Kokkuvõte 
 Sisestussorteerimine on seni käsitletud kolmest tehnikast kõige tõhusam. Siin eeldame, et esimene element on sorteeritud ja seejärel võrdleme iga elementi korduvalt kõigi eelnevate elementidega ning seejärel paigutame praeguse elemendi õigesse kohta massiivi. 
 Selles õpiobjektis, kui me arutasime Insertion sorteerimist, oleme märganud, et me võrdleme elemente, kasutades juurdekasvu 1 ja ka need on külgnevad. Selle omaduse tulemuseks on, et sorteeritud loendi saamiseks on vaja rohkem läbikäike. 
 Järgmises õpetuses arutame "Shell sorteerimist", mis on täiustatud võrreldes Selection sorteerimisega. 
 Shell sorteerimise puhul võtame kasutusele muutuja, mida tuntakse kui "inkrement" või "vahe", mille abil jagame loendi alamlistideks, mis sisaldavad mitte-ühesuguseid elemente, mis on üksteisest "vahega". Shell sorteerimine nõuab vähem läbikäike võrreldes Insertion sorteerimisega ja on ka kiirem. 
 Meie tulevastes õpetustes tutvume kahe sorteerimistehnikaga, "Quicksort" ja "Mergesort", mis kasutavad "Jaga ja valitse" strateegiat andmete loendite sorteerimiseks.
Keri üles