Python Insertion Sort
Hvordan fungerer innsettingssorteringen?
Arbeidet med innsettingssort blir diskutert i detalj her. Tallene sorteres ved hjelp av innsettingssorteringen. Det plasserer gjentatte ganger det påfølgende usorterte elementet på riktig sted i den tidligere sorterte listen. Det grunnleggende konseptet er å sammenligne det andre medlemmet med matrisens første element som antagelig allerede er sortert. Hvis det andre elementet er en mindre verdi enn det første, byttes det. Denne prosedyren gjentas for de gjenværende matriseelementene. De verste og gjennomsnittlige tilfellene av innsettingssort har en O (N2) tidskompleksitet, mens det beste tilfellet har en O (n) tidskompleksitet.
Eksempel 1:
Vi tar et lineært eksempel for å forstå konseptet innsettingssortering. Referansekoden er gitt i følgende:
for n i rekkevidde (1, len (arr)):
nøkkel = arr [n]
m = n-1
mens m> = 0 og nøkkel < arr[m] :
arr [m + 1] = arr [m]
m -= 1
arr [m + 1] = nøkkel
arr = [29, 15, 7, 10, 46]
InsertionSortalgo (ARR)
Print ("Resultatet av sortert matrise er:", ARR)
Som sett i dette eksemplet, definerer vi en innsettingssortfunksjon på linje 1. Denne implementeringen tar en liste over tall som input og sorterer listen i stigende rekkefølge. Vi tildeler "ARR" -variabelen som en liste i dette eksemplet. Etter det starter vi den ytre sløyfen som sjekker indeksen for matrisen. "For" -sløyfen brukes her. Området begynner på 1, som er det andre nummeret i en matrise, og fortsetter gjennom løkken til det siste elementet.
Inne i denne sløyfen initialiserer vi en nøkkelvariabel som sjekker indeksverdien en etter en. Etter det oppretter vi en variabel som holder matriseringsverdien (n-1). Den indre sløyfen begynner nå å sjekke matriseverdiene. Den indre sløyfen starter ved gjeldende indeks for den ytre sløyfen og sammenligner det nåværende elementet med det forrige elementet. Hvis det forrige elementet er større, forskyves det til høyre og det nåværende elementets indeks reduseres. Dette fortsetter til riktig posisjon for det nåværende elementet er funnet.
Det nåværende elementet plasseres på riktig sted etter at den indre sløyfen er ferdig. Til slutt erklærer vi og initialiserer matrisen som heter “ARR”. Vi brukte denne matrisen i den tidligere beskrevne innsettingsfunksjonen for å utføre sortering på matrisen. Til slutt gir vi matrisen i utskriftserklæringen for å vise utfallet på konsollen.
Utgangen fra dette eksempelprogrammet er gitt i følgende:
[7, 10, 15, 29, 46]Eksempel 2:
Vi vil også forklare innsettingssortering i Python ved hjelp av et annet eksempel. Vi lager og kjører dette eksemplet ved hjelp av et hvilket som helst Python -verktøy som Pycharm eller Jupiter Notebook. Referansekoden for dette andre eksemplet er vedlagt i det følgende:
For I in Range (1, Len (ArrayX)):
temp = arrayx [i]
forrige eleement = i-1
Mens forrige element> = 0 og Temp < arrayX[previousElement]:
ArrayX [forrige element+1] = ArrayX [forrige element]
Forrige element- = 1
ArrayX [forrige element+1] = Temp
ArrayX = [45, 66, 37, 99, 10, 5, 2, 78, 1]
sortArray (arrayx)
print ("Resultatet av sortert matrise er", arrayx)
Vi erklærer en rekke for sorteringsformål ved å definere funksjonen som heter “sortarray”. Vi bruker en sløyfe for å krysse matrisen og starte søket med indeksen "1". Vi legger lengden på matrisen og indeksen "1" i rekkevidden der løkken utføres. Vi legger en annen variabel der vi for øyeblikket lagrer verdien av Loop -iterasjonen “I” i matrisen og tildeler verdien til “Temp” -variabelen. Vi lagrer den forrige verdien som sannsynligvis er det første elementet i matrisen vi sammenligner "temp" -variabelen for å søke om denne verdien er større eller mindre enn verdien som er lagret i "temp" -variabelen og navnet den variabelen som " forrige element ”.
Den indre sløyfen tar verdien som er til stede i "tidligere element" -variabelen for å sjekke om verdien er større enn "0". Deretter sammenligner vi de to variablene som heter "Temp" og "forrige element" som er lagret i matrisen. Denne verdien sendes til løkken ikke er slutt. Hvis verdien av matrisen som er lagret i “Forrige element” er “+1”, betyr det at løkken endrer verdien er mindre enn den forrige verdien av matrisen som er lagret i indeksen “0”. Deretter bytter vi disse to variablene som den mindre verdien forskyves mot indeksen “0” og den større verdien flyttes i stedet for en annen variabel.
Her skriver vi logikken for å bytte elementene i matrisen for å sortere elementene. Nå blir alle verdiene for matrisen sjekket en etter en. Endring av verdiene er mindre og forskjøvet mot starten av matrisen. La oss ta dette utvalget for vurdering. Vi starter matrisen med indeksen “1”. Dette betyr at vi først tar “66”. Deretter sammenligner vi verdien av "66" med den forrige verdien som er lagret i indeks "0", som er "45". Nå er “45” mindre enn “66”. Så vi bytter deretter variabelen som lagrer verdien av “66”. Deretter tildeler vi den forrige verdien av matrisen i "temp" -variabelen. Nå lagrer vi verdien av "45" i "temp" -variabelen.
Til slutt tildeler vi verdien som er lagret i "Array [forrige element +1]" der neste verdi til forrige verdi er lagret. Etter det lagrer vi den neste forrige verdien i temp for å begynne å sortere igjen. På denne måten bytter vi de større og mindre verdiene. Så inntil sløyfen er gyldig, lagres elementene i matrisen raskt, en etter en. På slutten av koden viser vi resultatet av denne matrisen på konsollen gjennom utskriftserklæringen.
Her vises utgangen fra denne matrisen på konsollen siden resultatet av den lagrede matrisen er
[1,2,5,10,37,45,66,78,99].Konklusjon
Vi konkluderer med at innsettingssortering er den viktigste typen sortering som brukes til å sortere alle elementene i en matrise i Python. Innføringssort er en stabil og på stedet, men ineffektiv algoritme som har mange fordeler som vi diskuterte ved hjelp av eksempler. Her delte vi matrisen i to deler: sortert og usortert. Sammenligningen mellom disse to delene opprettet den sorterte matrisen på slutten.