Beszúrási rendezési algoritmus Java programpéldával

Mi az a beszúrási rendezési algoritmus?

A beszúrásos rendezés egy egyszerű rendezési algoritmus, amely kis adatkészletekhez alkalmas. Minden iteráció során az algoritmus:

• Eltávolít egy elemet a tömbből.
• Összehasonlítja a legnagyobb értékkel a sor.
• Az elemet a megfelelő helyre mozgatja.

A viselkedés tükrözi azt, ahogyan egy kártyajátékos elrendezi a lapjait: minden új lapot felvesz, és balra eltolja minden nagyobb kártya mellett, amíg a megfelelő helyre nem kerül. Mivel minden eltolódás az eredeti tömbön belül történik, a beszúrásos rendezés a helyén van és stabil is.

Ugyanabba a kezdőbarát családba tartozik. Java rendezési rutinok, mint buborékfajta, mégis általában sokkal kevesebb írást hajt végre a már részben rendezett adatokon.

Beillesztési rendezési algoritmus folyamata

A Beszúrás rendezési algoritmusa grafikusan a következőképpen működik:

Az animáció ugyanazt a három lépést ismétli Java az alábbi program végrehajtja. A próbafuttatási táblázat tracVégezze el ezeket a lépéseket a {860, 8, 200, 9} minta tömbön, pontosan úgy, ahogy a program futásidőben kinyomtatja azokat.

Figyeljük meg, hogy a 3. lépéshez két összehasonlítás szükséges, mivel a 9-es kulcsnak két nagyobb értéken kell áthaladnia. Az összehasonlítások száma tehát azzal növekszik, hogy az egyes elemek mennyire eltérnek a sorrendtől.

Java Programpélda egy tömb rendezésére beillesztési rendezési algoritmussal:

Az alábbi program rendezi a {860, 8, 200, 9} tömböt, és egy futó kommentárt nyomtat, így minden összehasonlítás és minden eltolás látható. Mentse el más néven InsertionSortExample.java és fordítsd le bármilyen JDK 8-as vagy újabb kiadással.

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

Az óra lebonyolítása eredményezi a tracitt látható. Mindegyik Rendezési szám A sor a külső ciklus egy iterációját jelöli, és az egyes swapok után kiírt sor a tömb aktuális állapotát mutatja.

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

A beszúrási rendezés időbeli és térbeli komplexitása

A beszúrásos rendezés teljesítménye nagymértékben függ attól, hogy mennyire rendezett a bemenet, ezért a legjobb és a legrosszabb eset egy egész növekedési renddel tér el egymástól.

A helykihasználás sokkal egyszerűbb. Csak a pultok i, j, n és a key létrejönnek, és a tömböt a helyén átrendezzük, így a segédterület O(1)-es, függetlenül attól, hogy mennyire nő a bemenet.

Mivel a belső ciklus leáll, amint eléri a kisebb értéket, a beszúrásos rendezést adaptívnak nevezzük: minél közelebb van a bemenet a rendezett sorrendhez, annál közelebb kerül a futási idő a lineárishoz.

A beszúrásos rendezés előnyei és hátrányai

A beszúrásos rendezés a kvadratikus átlag esete ellenére is fennmarad az éles könyvtárakban, mivel konstans tényezői aprók, viselkedése pedig kiszámítható.

Előnyök

• Egyszerűen írható és könnyen elkészíthető trackézzel, ami alkalmas oktatásra és interjúkra.
• Stabil, így az azonos kulcsot megosztó rekordok megtartják eredeti relatív sorrendjüket.
• Helyben működik, a bemeneti tömbön túl csak O(1) extra memóriára van szükség.
• Adaptív, O(n) értéket ér el olyan adatokon, amelyek már majdnem rendezettek.
• Online, ami azt jelenti, hogy rendezni tudja a listákat, miközben az új elemek még érkeznek.

Hátrányok

• A véletlenszerű vagy fordított sorrendű bemeneten alkalmazott kvadratikus idő miatt nem alkalmas nagy tömbökhöz.
• Minden egyes eltolás a tömbbe ír, tehát több adatot mozgat, mint a kijelöléses rendezés.
• Az összevont és a gyors rendezés kényelmesen felülmúlja ezt, ha a bemenet néhány tucat elemen halad át.

Egy gyakorlati szabály az, hogy beszúrós rendezést akkor használunk, ha a tömb kicsi, amikor az adatok majdnem rendezettek, vagy amikor az oszd meg és uralkodj rendezés a partíciót néhány elemre redukálta.

Beszúrásos rendezés vs. BubblRendezés vs. Kijelöléses rendezés

Mindhárom algoritmus kvadratikus összehasonlító rendezés, mégis különböznek stabilitásukban, abban, hogyan reagálnak a rendezett bemenetre, és az általuk végrehajtott írások számában.

A szelekciós rendezés akkor nyer, ha az írás költséges, mivel a legkevesebb cserét végzi. A beszúrásos rendezés szinte mindenhol máshol nyer ezen a skálán, különösen részben rendezett adatokon, ezért a könyvtári rendezések, mint például a mögötte lévő, a legjobbak. közös Java ünnepély és a JDK belső részei nagyon kis partíciók esetén erre váltanak.

GYIK