Home-theater-designers
Innsettingssortering er en teknikk som fungerer ved å bruke en sortert underliste og kontinuerlig legge til en verdi fra den usorterte listen til hele listen er sortert.
Algoritmen begynner med det første listeelementet som den sorterte underlisten. Det sammenligner deretter det neste tallet med det første. Hvis den er større, settes den inn i den første indeksen. Ellers er det igjen i indeksen.
Den tredje verdien blir deretter sammenlignet med de to andre, og deretter satt inn i riktig indeks. Denne prosessen fortsetter til hele listen er sortert.
En nærmere titt på innsettingssortering
Beskrivelsen ovenfor var kanskje ikke fornuftig for deg. Et eksempel skal hjelpe deg å forstå mye bedre.
Anta at du har en liste: [39, 6, 2, 51, 30, 42, 7].
Algoritmen identifiserer 39 som den første verdien av den sorterte underlisten. Evalueringen går deretter videre til den andre posisjonen.
Relatert: Dynamisk programmering: eksempler, vanlige problemer og løsninger
6 blir deretter sammenlignet med 39. Siden 6 er mindre enn 39, settes 6 inn i den første posisjonen og 39 i den andre. Den nye listeordren er etter at det første passet er nå:
[6, 39, 2, 51, 30, 42, 7]
Evalueringen går nå over til tredje posisjon. 2 blir sammenlignet med de to siste tallene og deretter satt inn i riktig posisjon. Den nye listeordren er etter at det andre passet nå er:
[2, 6, 39, 51, 30, 42, 7]
For det tredje passet er listerekkefølgen:
[2, 6, 39, 51, 30, 42, 7]
Prosessen gjentas til hele listen er sortert.
Se diagrammet nedenfor som oppsummerer disse operasjonene:
Algoritme analyse
Tidskompleksiteten til Insertion Sort er O (n2), akkurat som boblesortering . Antall sammenligninger i verste fall er summen av alle heltall fra 1 til (n-1), noe som gir en kvadratisk sum.
Kodeimplementering
Python- og Java -koden nedenfor viser hvordan du kan implementere Insertion Sort -metoden.
Python:
def insertionSort(mylist):
for step in range(1, len(mylist)):
current_element = mylist[step]
position = step
while position > 0 and mylist[position - 1] > current_element:
mylist[position] = mylist[position - 1]
position = position - 1
mylist[position] = current_elementJava:
void insertionSort(int[] myarray) {
int n = myarray.length;
for (int x = 1; x int key = myarray[x];
int y = x-1;
while ( (y > -1) && ( myarray [y] > key ) ) {
myarray [y+1] = myarray [y];
y--;
}
myarray[y+1] = key;
}
} Bedre koding med pseudokode
Kodeksemplene ovenfor ble gitt uten pseudokode som du kan referere til for å skrive denne algoritmen på andre språk. De fleste programmerere (forfatteren inkludert) liker å løpe til tastaturene sine etter å ha blitt fortalt 'hvisker' om hvordan et program fungerer.
Denne tilnærmingen er dessverre utsatt for feil ettersom programlogikken blir mer komplisert. Hvordan vil du nivåere programmeringsspillet ditt ved å lære å bruke pseudokode?
Dele Dele kvitring E -post Hva er Pseudocode og hvordan gjør det deg til en bedre utvikler?Sliter du med å lære programmering? Ta tak i koden ved å lære pseudokode. Men hva er pseudokode, og kan det virkelig hjelpe?
Les neste Relaterte temaer- Programmering
- Java
- Python
- Opplæringsprogrammer for koding
Jerome er personalforfatter på MakeUseOf. Han dekker artikler om programmering og Linux. Han er også en kryptoentusiast og holder alltid oversikt over kryptoindustrien.
du bryter vi fikser nær megMer fra Jerome Davidson
Abonner på vårt nyhetsbrev
Bli med i vårt nyhetsbrev for tekniske tips, anmeldelser, gratis ebøker og eksklusive tilbud!
Klikk her for å abonnere