Insertion Sort Algoritme i Java med programeksempel

Hvad er Insertion Sort Algorithm?

Indsættelsessortering er en simpel sorteringsalgoritme, der er velegnet til små datasæt. Under hver iteration vil algoritmen:

• Fjerner et element fra et array.
• Sammenligner det med den største værdi i matrix.
• Flytter elementet til dets korrekte placering.

Opførslen afspejler den måde, en kortspiller arrangerer en hånd på: hvert nyt kort tages op og skubbes til venstre forbi hvert større kort, indtil det hviler på det rigtige sted. Fordi al forskydning sker inden for det oprindelige array, er indsættelsessortering både på plads og stabil.

Den tilhører den samme familie af begyndervenlige Java sorteringsrutiner som boble sortering, men den udfører normalt langt færre skrivninger på data, der allerede er delvist ordnet.

Insertion Sort Algoritme Process

Her er hvordan indsættelsessorteringsalgoritmen fungerer grafisk:

Animationen gentager de samme tre trin Java Programmet nedenfor udføres. Tørløbstabellen tracUdfører disse trin på eksempelarrayet {860, 8, 200, 9}, præcis som programmet udskriver dem under kørsel.

Bemærk at gennemgang 3 kræver to sammenligninger, fordi tast 9 skal passere to større værdier. Antallet af sammenligninger vokser derfor med hvor langt ude af rækkefølge hvert element starter.

Java Programeksempel til at sortere et array ved hjælp af Insertion Sort Algorithm:

Programmet nedenfor sorterer arrayet {860, 8, 200, 9} og udskriver en løbende kommentar, så hver sammenligning og hvert skift er synligt. Gem det som InsertionSortExample.java og kompilere den med en hvilken som helst JDK 8 eller nyere 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();
	    
	}
}

At afholde klassen producerer tracvist her. Hver Sorteringspasnummer Linjen markerer én iteration af det ydre loop, og linjen, der udskrives efter hver swap, viser arrayet, som det ser ud på det tidspunkt.

Code Output:

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- og rumkompleksitet af indsættelsessortering

Indsættelsessorteringsydeevnen afhænger i høj grad af, hvor ordnet inputtet allerede er, hvilket er grunden til, at det bedste og det værste tilfælde adskiller sig med en hel vækstorden.

Pladsudnyttelsen er langt enklere. Kun tællerne i, j, n og key oprettes, og arrayet omarrangeres på plads, så hjælperummet er O(1) uanset hvor stort inputtet vokser.

Fordi den indre løkke stopper, så snart den møder en mindre værdi, beskrives indsættelsessortering som adaptiv: jo tættere inputtet er på den sorterede rækkefølge, desto tættere bevæger køretiden sig mod lineær.

Fordele og ulemper ved indsættelsessortering

Indsættelsessortering overlever i produktionsbiblioteker på trods af sit kvadratiske gennemsnitstilfælde, fordi dens konstante faktorer er små, og dens adfærd er forudsigelig.

Fordele

• Enkel at skrive og nem at trace i hånden, hvilket er velegnet til undervisning og interviews.
• Stabil, så poster, der deler en nøgle, beholder deres oprindelige relative rækkefølge.
• In-place, kræver kun O(1) ekstra hukommelse ud over input-arrayet.
• Adaptiv, når O(n) på data, der allerede er næsten sorteret.
• Online, hvilket betyder, at den kan sortere en liste, mens nye elementer stadig ankommer.

Ulemper

• Kvadratisk tid på tilfældigt eller omvendt ordnet input gør den uegnet til store arrays.
• Hvert skift skriver til arrayet, så det flytter flere data end sorteringsfunktion.
• Merge sort og quicksort klarer sig bedre end det, når inputtet passerer et par dusin elementer.

En praktisk regel er at bruge indsættelsessortering, når arrayet er lille, når dataene næsten er i orden, eller når en divider-og-hersk-sortering har reduceret en partition til en håndfuld elementer.

Indsættelsessortering vs. Bubble-sortering vs. valgsortering

Alle tre algoritmer er kvadratiske sammenligningstyper, men de adskiller sig i stabilitet, i hvordan de reagerer på ordnet input, og i antallet af skrivninger, de udfører.

Udvælgelsessortering vinder, når en skrivning er dyr, fordi den udfører færrest swaps. Indsættelsessortering vinder næsten alle andre steder på denne skala, især på delvist ordnede data, hvilket er grunden til bibliotekssorteringer som den bagved. fælles Java øvelser og JDK's interne komponenter skifter til det for meget små partitioner.

Ofte Stillede Spørgsmål