Insertion Sort Algoritm in Java med programexempel

Vad är Insertion Sort Algorithm?

Insättningssortering är en enkel sorteringsalgoritm som lämpar sig för små datamängder. Under varje iteration, algoritmen:

• Tar bort ett element från en array.
• Jämför det mot det största värdet i array.
• Flyttar elementet till rätt plats.

Beteendet speglar hur en kortspelare arrangerar en hand: varje nytt kort plockas upp och skjuts åt vänster förbi varje större kort tills det vilar på rätt plats. Eftersom all förskjutning sker inuti den ursprungliga matrisen är insättningssortering både på plats och stabil.

Den tillhör samma familj av nybörjarvänliga Java sorteringsrutiner som bubbelsorter, men den utför normalt betydligt färre skrivningar på data som redan är delvis ordnad.

Insättningssorteringsalgoritmprocess

Så här fungerar sorteringsalgoritmen för infogning grafiskt:

Animationen upprepar samma tre steg Java Programmet nedan utförs. Torrkörningstabellen tracutför dessa steg på exempelmatrisen {860, 8, 200, 9}, exakt som programmet skriver ut dem vid körning.

Observera att pass 3 behöver två jämförelser eftersom tangent 9 måste passera två större värden. Antalet jämförelser ökar därför med hur långt ur ordning varje element börjar.

Java Programexempel för att sortera en matris med Insertion Sort Algorithm:

Programmet nedan sorterar arrayen {860, 8, 200, 9} och skriver ut en löpande kommentar, så varje jämförelse och varje förskjutning är synlig. Spara den som InsertionSortExample.java och kompilera den med valfri JDK 8 eller senare version.

package com.guru99;
 
public class InsertionSortExample {
 
	
    public static void main(String a[])
    {    
        int[] myArray  = {860,8,200,9};  
        
        System.out.println("Before Insertion Sort");  
        
        printArray(myArray);
            
        insertionSort(myArray);//sorting array using insertion sort    
           
        System.out.println("After Insertion Sort");  
        
        printArray(myArray);   
    }    
 public static void insertionSort(int arr[]) 
	{  
        int n = arr.length;  
        
        for (int i = 1; i < n; i++)
        {   System.out.println("Sort Pass Number "+(i));
            int key = arr[i];  
            int j = i-1;  
            
            while ( (j > -1) && ( arr [j] > key ) ) 
            {  
            System.out.println("Comparing "+ key  + " and " + arr [j]); 
                arr [j+1] = arr [j];  
                j--;  
            }  
            arr[j+1] = key; 
            System.out.println("Swapping Elements: New Array After Swap");
            printArray(arr);
        }  
    }
 static void printArray(int[] array){
	    
	    for(int i=0; i < array.length; i++)
		{  
			System.out.print(array[i] + " ");  
		} 
	    System.out.println();
	    
	}
}

Att hålla klassen producerar tracvisas här. Varje Sorteringspassnummer linjen markerar en iteration av den yttre loopen, och linjen som skrivs ut efter varje byte visar arrayen som den ser ut just då.

Code Produktion:

Before Insertion Sort
860 8 200 9 
Sort Pass Number 1
Comparing 8 and 860
Swapping Elements: New Array After Swap
8 860 200 9 
Sort Pass Number 2
Comparing 200 and 860
Swapping Elements: New Array After Swap
8 200 860 9 
Sort Pass Number 3
Comparing 9 and 860
Comparing 9 and 200
Swapping Elements: New Array After Swap
8 9 200 860 
After Insertion Sort
8 9 200 860

Tids- och rumskomplexitet för insättningssortering

Prestandan för insättningssortering beror starkt på hur ordnad inmatningen redan är, vilket är anledningen till att det bästa fallet och det värsta fallet skiljer sig åt med en hel ordningsstorlek.

Utrymmesutnyttjandet är mycket enklare. Endast räknarna i, j, n och key skapas och arrayen omorganiseras på plats, så hjälputrymmet är O(1) oavsett hur stor inmatningen växer.

Eftersom den inre loopen stannar så snart den möter ett mindre värde beskrivs insättningssortering som adaptiv: ju närmare ingången är sorterad ordning, desto närmare rör sig körtiden linjär.

Fördelar och nackdelar med insättningssortering

Insättningssortering överlever i produktionsbibliotek trots sitt kvadratiska medelvärde, eftersom dess konstanta faktorer är små och dess beteende är förutsägbart.

Fördelar

• Enkel att skriva och lätt att trace för hand, vilket passar för undervisning och intervjuer.
• Stabil, så poster som delar en nyckel behåller sin ursprungliga relativa ordning.
• På plats, behöver endast O(1) extra minne utöver inmatningsmatrisen.
• Adaptiv, når O(n) på data som redan är nästan sorterad.
• Online, vilket betyder att den kan sortera en lista medan nya element fortfarande anländer.

Nackdelar

• Kvadratisk tid på slumpmässig eller omvänd ordning i inmatningen gör den olämplig för stora matriser.
• Varje skift skriver till arrayen, så den flyttar mer data än vad urvalssortering gör.
• Merge sortering och quicksort överträffar det bekvämt när inmatningen passerar några dussin element.

En praktisk regel är att använda insättningssortering när arrayen är liten, när data nästan är i ordning, eller när en dela-och-härska-sortering har reducerat en partition till en handfull element.

Insättningssortering vs. Bubble-sortering kontra urvalssortering

Alla tre algoritmerna är kvadratiska jämförelsetyper, men de skiljer sig åt i stabilitet, i hur de reagerar på ordnad inmatning och i antalet skrivningar de utför.

Urvalssortering vinner när en skrivning är dyr, eftersom den utför minst antal byten. Insättningssortering vinner nästan överallt annars i denna skala, särskilt på delvis ordnad data, vilket är anledningen till att bibliotekssorteringar som den bakom gemensam Java övningar och JDK-internationerna växlar till det för mycket små partitioner.

Vanliga frågor