Meny

Innsettingssortering i C ++ med eksempler

  • Hoved
  • Annen
  • Innsettingssortering i C ++ med eksempler

insertion sort c with examples

Prøv Instrumentet Vårt For Å Eliminere Problemer

En grundig titt på innsettingssortering med klassiske eksempler.

Innsettingssortering er en sorteringsteknikk som kan sees på en måte som vi spiller kort for hånden. Måten vi setter inn et hvilket som helst kort i et kort eller fjerner det, sorterer innsetting fungerer på en lignende måte.

Sorteringsalgoritmeteknikk er mer effektiv enn sorteringsteknikker for sortering og utvalg, men er mindre effektiv enn de andre teknikkene som Quicksort og Merge sort.

=> Sjekk ut de beste C ++ opplæringsveiledningene her.

INNFØRINGSSORT

Hva du vil lære:

Oversikt

I innsettingssorteringsteknikken starter vi fra det andre elementet og sammenligner det med det første elementet og setter det på et riktig sted. Deretter utfører vi denne prosessen for de påfølgende elementene.

Vi sammenligner hvert element med alle dets tidligere elementer og setter eller setter inn elementet i riktig posisjon. Sorteringsteknikk for innsetting er mer gjennomførbar for matriser med et mindre antall elementer. Det er også nyttig for å sortere koblede lister.

jeg vil være en produkttester

Koblede lister har en peker til neste element (i tilfelle en enkeltkoblet liste) og en peker til det forrige elementet også (i tilfelle en dobbeltkoblet liste). Derfor blir det lettere å implementere innsettingssortering for en koblet liste.

La oss utforske alt om innsettingssortering i denne opplæringen.

Generell algoritme

Trinn 1 : Gjenta trinn 2 til 5 for K = 1 til N-1
Steg 2 : set temp = A (K)
Trinn 3 : sett J = K - 1
Trinn 4 : Gjenta mens temp<=A(J)
sett A (J + 1) = A (J)
sett J = J - 1
(slutten av indre sløyfe)
Trinn 5 : sett A (J + 1) = temp
(end of loop)
Trinn 6 : exit

I innsettingssorteringsteknikken starter vi således fra det andre elementet ettersom vi antar at det første elementet alltid er sortert. Så fra det andre elementet til det siste elementet, sammenligner vi hvert element med alle dets tidligere elementer og setter elementet i riktig posisjon.

Pseudokode

Pseudokoden for sortering av innsetting er gitt nedenfor.

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

Ovenfor er pseudokoden for sortering av innsetting, neste vil vi illustrere denne teknikken i følgende eksempel.

Illustrasjon

Matrisen som skal sorteres er som følger:

matrise som skal sorteres

Nå for hvert pass, sammenligner vi det nåværende elementet med alle dets tidligere elementer. Så i første omgang begynner vi med det andre elementet.

Insertion Sort - Illustrasjon

Dermed krever vi N antall passeringer for å fullstendig sortere en matrise som inneholder N antall elementer.

Illustrasjonen ovenfor kan oppsummeres i tabellform:

SendeUsortert listesammenligningSortert liste
1{12,3,5,10,8,1}{12.3}{3,12,5,10,8,1}
to{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 vist i illustrasjonen ovenfor, begynner vi med 2ndelement da vi antar at det første elementet alltid er sortert. Så vi begynner med å sammenligne det andre elementet med det første og bytter posisjon hvis det andre elementet er mindre enn det første.

Denne sammenligningen og bytteprosessen plasserer to elementer på sine rette steder. Deretter sammenligner vi det tredje elementet med det forrige (første og andre) elementet og utfører samme prosedyre for å plassere det tredje elementet på riktig sted.

tidskort-app for iPhone og Android

På denne måten plasserer vi ett element på hvert sted for hvert pass. For det første passet plasserer vi det andre elementet på sin plass. Således, generelt, for å plassere N-elementer på riktig sted, trenger vi N-1-passeringer.

Deretter vil vi demonstrere implementering av sorteringsteknikk for innsetting på C ++ språk.

C ++ Eksempel

#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 <

Produksjon:

Inngangslisten er

12 4 3 1 15 45 33 21 10 2

Sortert liste er

1 2 3 4 10 12 15 21 33 45

Deretter vil vi se Java-implementeringen av Insertion sort-teknikken.

Java-eksempel

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) + ' '); } } }

Produksjon:

Inngangsliste med elementer ...

12 4 3 1 15 45 33 21 10 2

hvor kan jeg se anime gratis

sortert liste over elementer ...

1 2 3 4 10 12 15 21 33 45

I begge implementeringene kan vi se at vi begynner å sortere fra 2ndelement i matrisen (sløyfevariabelen j = 1) og sammenlign gjeldende element med alle sine tidligere elementer, og sorter deretter elementet for å plassere det i riktig posisjon hvis det nåværende elementet ikke er i orden med alle dets tidligere elementer.

Innsettingssortering fungerer best og kan fullføres i færre passeringer hvis matrisen er delvis sortert. Men etter hvert som listen blir større, reduseres ytelsen. En annen fordel med Insertion sort er at det er en stabil sort som betyr at den opprettholder rekkefølgen på like elementer i listen.

Kompleksitetsanalyse av innleggssorteringsalgoritmen

Fra pseudokoden og illustrasjonen ovenfor er innsettingssorter den effektive algoritmen sammenlignet med sortering av boble eller utvalg. I stedet for å bruke for loop og nåværende forhold, bruker den en while-loop som ikke utfører flere ekstra trinn når matrisen er sortert.

Imidlertid, selv om vi overfører den sorterte matrisen til Insertion sort-teknikken, vil den fremdeles utføre den ytre for loop og derved kreve et antall trinn for å sortere en allerede sortert array. Dette gjør den beste tidskompleksiteten ved innsetting sortere en lineær funksjon av N der N er antall elementer i matrisen.

Dermed er de forskjellige kompleksitetene for innsettingssorteringsteknikk gitt nedenfor:

Kompleksitet i verste fallO (n 2)
Kompleksitet i beste tilfellePå)
Gjennomsnittlig tidskompleksitetO (n 2)
RomkompleksitetO (1)

Til tross for disse kompleksitetene kan vi fremdeles konkludere med at innsettingssortering er den mest effektive algoritmen sammenlignet med andre sorteringsteknikker som boble sortering og utvalg sortering.

Konklusjon

Innsettingssortering er den mest effektive av alle de tre teknikkene som er diskutert så langt. Her antar vi at det første elementet er sortert, og deretter gjentatte ganger sammenligner hvert element med alle dets tidligere elementer, og plasserer det nåværende elementet i riktig posisjon i matrisen.

I denne opplæringen, mens vi diskuterer innsettingssortering, har vi lagt merke til at vi sammenligner elementene ved hjelp av en økning på 1, og de er også sammenhengende. Denne funksjonen resulterer i at det kreves flere pass for å få den sorterte listen.

I vår kommende opplæring vil vi diskutere “Shell sort” som er en forbedring i forhold til Selection sort.

I skallsortering introduserer vi en variabel kjent som 'inkrement' eller 'gap' ved hjelp av hvilken vi deler listen opp i underlister som inneholder ikke-sammenhengende elementer som 'gap' fra hverandre. Skalsortering krever færre passeringer sammenlignet med innsettingssortering og er også raskere.

I våre fremtidige veiledninger vil vi lære om to sorteringsteknikker, 'Quicksort' og 'Mergesort' som bruker 'Divide and conquer' -strategi for sortering av datalister.

=> Se opp nybegynnere C ++ treningsguide her.

Anbefalt lesing

^