Algoritmus řazení vložení do Java s příkladem programu

Co je algoritmus řazení vložení?

Vložení řazení je jednoduchý třídicí algoritmus vhodný pro malé soubory dat. Během každé iterace algoritmus:

• Odebere prvek z pole.
• Porovná ji s největší hodnotou v řada.
• Přesune prvek na správné místo.

Toto chování odráží způsob, jakým hráč sestavuje karty v ruce: každá nová karta je zvednuta a posouvána doleva za každou větší kartu, dokud nespočívá na správném místě. Protože veškeré posunování probíhá uvnitř původního pole, je řazení vkládáním na místě i stabilní.

Patří do stejné rodiny programů vhodných pro začátečníky. Java třídící rutiny jako bublinové řazení, přesto obvykle provádí mnohem méně zápisů do dat, která jsou již částečně uspořádaná.

Proces algoritmu řazení vložení

Zde je návod, jak graficky funguje proces řazení algoritmu vložení:

Animace opakuje stejné tři kroky Java Níže uvedený program provede. Tabulka zkušebního provozu tracvypíše tyto kroky na vzorovém poli {860, 8, 200, 9} přesně tak, jak je program vypíše za běhu.

Všimněte si, že průchod 3 vyžaduje dvě porovnání, protože klíč 9 musí projít kolem dvou větších hodnot. Počet porovnání proto roste s tím, jak daleko mimo pořadí každý prvek začíná.

Java Příklad programu pro řazení pole pomocí algoritmu řazení vložení:

Následující program seřadí pole {860, 8, 200, 9} a vypíše průběžný komentář, takže každé porovnání a každý posun je viditelný. Uložte jej jako InsertionSortExample.java a zkompilujte jej s libovolnou verzí JDK 8 nebo novější.

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

Spuštění kurzu vytvoří trace je zde zobrazeno. Každý Číslo třídicího průkazu Řádek označuje jednu iteraci vnější smyčky a řádek vytištěný po každé výměně zobrazuje pole v daném okamžiku.

Code Výstup:

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

Časová a prostorová složitost řazení vložením

Výkon řazení vkládáním silně závisí na tom, jak je vstup již uspořádán, a proto se nejlepší a nejhorší případ liší o celý řád růstu.

Využití prostoru je mnohem jednodušší. Pouze pulty i, j, n a key jsou vytvořeny a pole je přeskupeno na místě, takže pomocný prostor je O(1) bez ohledu na to, jak velký vstup roste.

Protože vnitřní smyčka se zastaví, jakmile narazí na menší hodnotu, je řazení vkládáním popsáno jako adaptivní: čím blíže je vstup seřazenému pořadí, tím blíže se doba běhu posouvá k lineárnímu směru.

Výhody a nevýhody řazení vložením

Vkládací řazení přežívá v produkčních knihovnách i přes případ kvadratického průměru, protože jeho konstantní faktory jsou malé a jeho chování je předvídatelné.

Výhody

• Jednoduché psaní a snadné tracručně, což je vhodné pro výuku i pohovory.
• Stabilní, takže záznamy, které sdílejí klíč, si zachovávají své původní relativní pořadí.
• Na místě, potřebuje pouze O(1) paměti navíc nad rámec vstupního pole.
• Adaptivní, dosahující O(n) na datech, která jsou již téměř seřazena.
• Online, což znamená, že dokáže seřadit seznam i v době, kdy se přidávají nové prvky.

Nevýhody

• Kvadratický čas na náhodném nebo obráceně uspořádaném vstupu jej činí nevhodným pro velká pole.
• Každý posun zapisuje do pole, takže přesouvá více dat než výběrové řazení.
• Sortování sloučením a rychlé sortování jej pohodlně překonávají, jakmile vstup projde několika desítkami prvků.

Praktickým pravidlem je sáhnout po vloženém řazení, když je pole malé, když jsou data téměř v pořádku nebo když řazení metodou „rozděl a panuj“ zredukovalo oddíl na hrstku prvků.

Řazení vložením vs. Bubble-řazení vs. výběrové řazení

Všechny tři algoritmy jsou kvadratického porovnání, liší se však stabilitou, reakcí na uspořádaný vstup a počtem zápisů, které provádějí.

Výběrové řazení vítězí, když je zápis nákladný, protože provádí nejméně záměn. V tomto měřítku vítězí vkládací řazení téměř všude jinde, zejména u částečně uspořádaných dat, což je důvod, proč se používají knihovní řazení, jako je to za ním. společný Java cvičení a interní prvky JDK se na něj přepínají pro velmi malé oddíly.

Nejčastější dotazy