Home-theater-designers
Insättningssortering är en teknik som fungerar genom att använda en sorterad underlista och kontinuerligt lägga till ett värde från den osorterade listan tills hela listan är sorterad.
Algoritmen börjar med det första listobjektet som den sorterade underlistan. Den jämför sedan nästa tal med det första. Om det är större, sätts det in i det första indexet. Annars är det kvar i sitt index.
Det tredje värdet jämförs sedan med de andra två och sätts sedan in i rätt index. Denna process fortsätter tills hela listan är sorterad.
En närmare titt på införingssortering
Beskrivningen ovan kanske inte var vettig för dig. Ett exempel bör hjälpa dig att förstå mycket bättre.
Antag att du har en lista: [39, 6, 2, 51, 30, 42, 7].
Algoritmen identifierar 39 som det första värdet för den sorterade underlistan. Utvärderingen går sedan vidare till den andra positionen.
Relaterat: Dynamisk programmering: Exempel, vanliga problem och lösningar
6 jämförs sedan med 39. Eftersom 6 är mindre än 39 sätts 6 in i det första läget och 39 i det andra. Den nya listorder är efter det första passet är nu:
[6, 39, 2, 51, 30, 42, 7]
Utvärderingen övergår nu till den tredje positionen. 2 jämförs med de två sista siffrorna och infogas sedan i rätt position. Den nya listorderna är efter det andra passet nu:
[2, 6, 39, 51, 30, 42, 7]
För det tredje passet är listordningen:
[2, 6, 39, 51, 30, 42, 7]
Processen upprepas tills hela listan är sorterad.
Se diagrammet nedan som sammanfattar dessa operationer:
Algoritm analys
Tidskomplexiteten för Insertion Sort är O (n2), precis som bubbla sortera . Antalet jämförelser i värsta fall är summan av alla heltal från 1 till (n-1), vilket ger en kvadratisk summa.
Kodimplementering
Python- och Java -koden nedan visar hur du kan implementera Insertion Sort -metoden.
Pytonorm:
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;
}
} Bättre kodning med pseudokod
Kodexemplen ovan gavs utan någon pseudokod som du kan referera till för att skriva denna algoritm på andra språk. De flesta programmerare (författaren ingår) gillar att springa till sina tangentbord efter att ha fått veta 'viskar' om hur ett program fungerar.
Detta tillvägagångssätt är tyvärr utsatt för fel eftersom programlogiken blir mer komplicerad. Hur skulle du vilja öka ditt programmeringsspel genom att lära dig att använda pseudokod?
Dela med sig Dela med sig Tweet E-post Vad är Pseudocode och hur gör det dig till en bättre utvecklare?Kämpar du för att lära dig programmering? Ta tag i koden genom att lära dig pseudokod. Men vad är pseudokod och kan det verkligen hjälpa?
Läs Nästa Relaterade ämnen- Programmering
- Java
- Pytonorm
- Handledning för kodning
Jerome är personalförfattare på MakeUseOf. Han täcker artiklar om programmering och Linux. Han är också en kryptoentusiast och håller alltid koll på kryptoindustrin.
ställa in ny e -postadressMer från Jerome Davidson
Prenumerera på vårt nyhetsbrev
Gå med i vårt nyhetsbrev för tekniska tips, recensioner, gratis e -böcker och exklusiva erbjudanden!
Klicka här för att prenumerera