Meny

Insättningssortering i C ++ med exempel

insertion sort c with examples

Prova Vårt Instrument För Att Eliminera Problem

En djupgående titt på insättningssortering med klassiska exempel.

Insättningssortering är en sorteringsteknik som kan ses på ett sätt som vi spelar kort till hands. Sättet vi sätter in vilket kort som helst i ett kort eller tar bort det, sorterar insättningen på ett liknande sätt.

Införingssorteringsalgoritmtekniken är effektivare än teknik för sortering av bubblor och urval men är mindre effektiv än de andra teknikerna som Quicksort och Merge sort.

=> Kolla in de bästa C ++ träningsövningarna här.

INSÄTTNINGSSORTERING

Vad du kommer att lära dig:

Översikt

I insättningssorteringstekniken börjar vi från det andra elementet och jämför det med det första elementet och placerar det på rätt plats. Sedan utför vi denna process för de efterföljande elementen.

Vi jämför varje element med alla dess tidigare element och placerar eller sätter in elementet i rätt läge. Insättningssorteringsteknik är mer genomförbar för matriser med ett mindre antal element. Det är också användbart för att sortera länkade listor.

enkel sorteringsalgoritm c ++

Länkade listor har en pekare till nästa element (i fallet med en enstaka länkad lista) och en pekare till föregående element också (i fallet med en dubbelt länkad lista). Därför blir det lättare att implementera insättningssortering för en länkad lista.

Låt oss utforska allt om insättningssortering i den här handledningen.

Allmän algoritm

Steg 1 : Upprepa steg 2 till 5 för K = 1 till N-1
Steg 2 : ställa in temp = A (K)
Steg 3 : ställ in J = K - 1
Steg 4 : Upprepa medan temp<=A(J)
sätt A (J + 1) = A (J)
ställ in J = J - 1
(slutet av den inre slingan)
Steg 5 : ställ in A (J + 1) = temp
(slutet av slingan)
Steg 6 : utgång

Således, i insättningssorteringstekniken, börjar vi från det andra elementet eftersom vi antar att det första elementet alltid är sorterat. Sedan från det andra elementet till det sista elementet jämför vi varje element med alla dess tidigare element och sätter det elementet i rätt position.

Pseudokod

Pseudokoden för sorteringssortering ges nedan.

procedure insertionSort(array,N ) array – array to be sorted N- number of elements 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 the number at free position array (freePosition) = insert_val end for end procedure

Ovanstående är pseudokoden för insättningssortering. Därefter illustrerar vi denna teknik i följande exempel.

Illustration

Matrisen som ska sorteras är som följer:

array som ska sorteras

Nu för varje pass jämför vi det aktuella elementet med alla dess tidigare element. Så i det första passet börjar vi med det andra elementet.

Insättningssortering - Illustration

Således kräver vi N antal passeringar för att helt sortera en matris som innehåller N antal element.

Ovanstående illustration kan sammanfattas i tabellform:

PasseraOsorterad listajämförelseSorterad lista
ett{12,3,5,10,8,1}{12.3}{3,12,5,10,8,1}
två{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}

Som visas i ovanstående illustration börjar vi med 2ndelement eftersom vi antar att det första elementet alltid sorteras. Så vi börjar med att jämföra det andra elementet med det första och byta position om det andra elementet är mindre än det första.

Denna jämförelse- och bytesprocess placerar två element på sina rätta platser. Därefter jämför vi det tredje elementet med dess tidigare (första och andra) element och utför samma procedur för att placera det tredje elementet på rätt plats.

På detta sätt placerar vi ett element på varje plats för varje pass. För det första passet placerar vi det andra elementet på sin plats. För att placera N-element på sin rätta plats behöver vi alltså N-1-pass.

Därefter kommer vi att demonstrera införandet av sorteringsteknik i C ++ - språk.

C ++ Exempel

#include using namespace std; int main () { int myarray(10) = { 12,4,3,1,15,45,33,21,10,2}; cout<<' Input list is '; for(int i=0;i<10;i++) { cout <

Produktion:

c ++ slumpmässigt tal mellan 0 och 10

Ingångslistan är

12 4 3 1 15 45 33 21 10 2

Sorterad lista är

1 2 3 4 10 12 15 21 33 45

Därefter kommer vi att se Java-implementeringen av insättningssorteringstekniken.

Java-exempel

public class Main { public static void main(String() args) { int() myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println('Input list of elements ...'); 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(' sorted list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray(i) + ' '); } } }

Produktion:

Inmatningslista med element ...

12 4 3 1 15 45 33 21 10 2

sorterad lista över element ...

1 2 3 4 10 12 15 21 33 45

I båda implementeringarna kan vi se att vi börjar sortera från 2ndelement i matrisen (loopvariabel j = 1) och jämför upprepade gånger det aktuella elementet med alla dess tidigare element och sortera sedan elementet för att placera det i rätt position om det aktuella elementet inte är i ordning med alla dess tidigare element.

Insättningssortering fungerar bäst och kan slutföras i färre pass om matrisen är delvis sorterad. Men när listan blir större minskar dess prestanda. En annan fördel med insättningssortering är att det är en stabil sortering vilket innebär att den bibehåller ordningen på lika element i listan.

Komplexitetsanalys av införingssorteringsalgoritmen

Från pseudokoden och illustrationen ovan är insättningssortering den effektiva algoritmen jämfört med bubblasortering eller urvalsortering. Istället för att använda för loop och nuvarande förhållanden använder den en while-loop som inte utför några extra steg när arrayen sorteras.

Men även om vi skickar den sorterade matrisen till insättningssorteringstekniken kommer den fortfarande att köra den yttre för slingan, vilket kräver ett antal steg för att sortera en redan sorterad matris. Detta gör att insättningens bästa tidskomplexitet sorterar en linjär funktion av N där N är antalet element i matrisen.

standardgateway inte tillgängligt Windows 7

Således ges de olika komplexiteten för insättningssorteringsteknik nedan:

Värsta fallets tidskomplexitetO (n 2)
Komplexitet i bästa fallPå)
Genomsnittlig tidskomplexitetO (n 2)
RymdkomplexitetO (1)

Trots dessa komplexiteter kan vi fortfarande dra slutsatsen att insättningssortering är den mest effektiva algoritmen jämfört med andra sorteringstekniker som Bubblesortering och Selektionssortering.

Slutsats

Insättningssortering är den effektivaste av alla tre tekniker som diskuterats hittills. Här antar vi att det första elementet sorteras och sedan jämför varje element upprepade gånger med alla dess tidigare element och placerar sedan det aktuella elementet i sin rätta position i matrisen.

I denna handledning har vi, när vi diskuterar insättningssortering, märkt att vi jämför elementen med ett steg på 1 och de är också angränsande. Den här funktionen resulterar i att det krävs fler pass för att få den sorterade listan.

I vår kommande handledning kommer vi att diskutera ”Shell sort” vilket är en förbättring jämfört med Selection sort.

I skalsortering introducerar vi en variabel som kallas 'inkrement' eller en 'gap' med vilken vi delar upp listan i underlistor som innehåller icke-sammanhängande element som 'gap' från varandra. Skalsortering kräver färre pass jämfört med insättningssortering och är också snabbare.

I våra framtida handledning kommer vi att lära oss om två sorteringstekniker, 'Quicksort' och 'Mergesort' som använder 'Divide and conquer' -strategi för att sortera datalistor.

=> Se upp för nybörjare C ++ träningsguide här.

Rekommenderad läsning

^