Invoegsorteeralgoritme in Java met programmavoorbeeld

Wat is een invoegsorteeralgoritme?

Invoegsortering is een eenvoudig sorteeralgoritme dat geschikt is voor kleine datasets. Tijdens elke iteratie zal het algoritme:

• Verwijdert een element uit een array.
• Vergelijk het met de grootste waarde in de reeks.
• Verplaatst het element naar de juiste locatie.

Het gedrag is vergelijkbaar met de manier waarop een kaartspeler zijn hand schikt: elke nieuwe kaart wordt opgepakt en naar links geschoven, voorbij elke grotere kaart, totdat deze op de juiste plek ligt. Omdat alle verschuivingen binnen de oorspronkelijke array plaatsvinden, is insertion sort zowel in-place als stabiel.

Het behoort tot dezelfde familie van beginnersvriendelijke spellen. Java sorteerroutines als bellen sorterenToch voert het normaal gesproken veel minder schrijfbewerkingen uit op gegevens die al gedeeltelijk geordend zijn.

Invoegsorteeralgoritmeproces

Hier ziet u hoe het algoritme voor het sorteren van invoegingen grafisch werkt:

De animatie herhaalt dezelfde drie stappen. Java Onderstaand programma wordt uitgevoerd. De testtabel tracVoer die stappen uit op de voorbeeldreeks {860, 8, 200, 9}, precies zoals het programma ze tijdens de uitvoering afdrukt.

Merk op dat stap 3 twee vergelijkingen vereist, omdat de sleutel 9 langs twee grotere waarden moet gaan. Het aantal vergelijkingen neemt dus toe naarmate de volgorde van de elementen verder uit de orde is.

Java Programmavoorbeeld om een ​​array te sorteren met behulp van het invoegsorteeralgoritme:

Het onderstaande programma sorteert de array {860, 8, 200, 9} en print een doorlopend commentaar, zodat elke vergelijking en elke verschuiving zichtbaar is. Sla het op als InsertionSortExample.java en compileer het met elke JDK 8 of latere versie.

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();
	    
	}
}

Het uitvoeren van de klasse produceert het volgende: trace hier getoond. Elk Sorteer pasnummer De regel markeert één iteratie van de buitenste lus, en de regel die na elke wisseling wordt afgedrukt, toont de array zoals die er op dat moment uitziet.

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

Tijd- en ruimtecomplexiteit van invoegsorteerbewerking

De prestaties van insertion sort zijn sterk afhankelijk van hoe geordend de invoer al is, waardoor het beste en het slechtste geval een hele orde van grootte van elkaar verschillen.

Het ruimtegebruik is veel eenvoudiger. Alleen de aanrechtbladen i, j, n en key worden aangemaakt en de array wordt ter plekke herschikt, zodat de hulpruimte O(1) is, ongeacht hoe groot de invoer wordt.

Omdat de binnenste lus stopt zodra deze een kleinere waarde tegenkomt, wordt insertion sort beschreven als adaptief: hoe dichter de invoer bij de gesorteerde volgorde ligt, hoe dichter de looptijd bij lineair komt.

Voordelen en nadelen van invoegsortering

Invoegsorteeralgoritmen worden ondanks het kwadratische gemiddelde nog steeds veel gebruikt in productiebibliotheken, omdat de constante factoren klein zijn en het gedrag voorspelbaar is.

Voordelen

• Eenvoudig te schrijven en makkelijk te trace met de hand, wat het geschikt maakt voor lesgeven en interviews.
• Stabiel, dus records die dezelfde sleutel delen, behouden hun oorspronkelijke relatieve volgorde.
• In-place, waarbij slechts O(1) extra geheugen nodig is naast de invoerarray.
• Adaptief, met een complexiteit van O(n) op data die al bijna gesorteerd is.
• Online, wat betekent dat een lijst gesorteerd kan worden terwijl er nog nieuwe elementen binnenkomen.

Nadelen

• De kwadratische rekentijd bij willekeurige of omgekeerd geordende invoer maakt het ongeschikt voor grote arrays.
• Elke shift schrijft naar de array, waardoor er meer data wordt verplaatst dan bij selectiesortering.
• Merge sort en quicksort presteren aanzienlijk beter zodra de invoer enkele tientallen elementen bevat.

Een praktische vuistregel is om insertion sort te gebruiken wanneer de array klein is, wanneer de gegevens bijna in de juiste volgorde staan, of wanneer een divide-and-conquer sort een partitie heeft gereduceerd tot een handvol elementen.

Invoegsorteermethode versus Bubble Sort versus Selection Sort

Alle drie de algoritmen zijn kwadratische vergelijkingssorteeralgoritmen, maar ze verschillen in stabiliteit, in hoe ze reageren op geordende invoer en in het aantal schrijfbewerkingen dat ze uitvoeren.

Selectiesortering wint wanneer een schrijfbewerking kostbaar is, omdat het de minste swaps uitvoert. Invoegsortering wint op deze schaal bijna overal, vooral bij gedeeltelijk geordende data, en daarom zijn bibliotheeksorteringen zoals die achter de selectiesortering zo populair. gemeenschappelijk Java oefeningen En de interne werking van de JDK schakelt er automatisch naar over voor zeer kleine partities.

Veelgestelde vragen