Algoritam sortiranja umetanjem u Java s primjerom programa

Što je algoritam sortiranja umetanjem?

Sortiranje umetanjem jednostavan je algoritam za sortiranje prikladan za male skupove podataka. Tijekom svake iteracije, algoritam:

• Uklanja element iz niza.
• Uspoređuje ga s najvećom vrijednošću u poredak.
• Premješta element na njegovo ispravno mjesto.

Ponašanje odražava način na koji igrač karata slaže ruku: svaka nova karta se uzima i gura lijevo pored svake veće karte dok ne stane na pravo mjesto. Budući da se svo pomicanje događa unutar izvornog niza, sortiranje umetanjem je i na mjestu i stabilno.

Pripada istoj obitelji onih prilagođenih početnicima. Java sortiranje rutina kao sortiranje mjehurićima, no obično obavlja puno manje zapisa na podatke koji su već djelomično uređeni.

Proces algoritma sortiranja umetanjem

Evo kako proces algoritma sortiranja umetanjem radi grafički:

Animacija ponavlja ista tri koraka Java program u nastavku izvodi. Tablica probnog rada tracispisuje te korake na primjeru niza {860, 8, 200, 9}, točno onako kako ih program ispisuje za vrijeme izvođenja.

Primijetite da prolaz 3 zahtijeva dvije usporedbe jer ključ 9 mora proći pored dvije veće vrijednosti. Broj usporedbi stoga raste s time koliko je svaki element izvan redoslijeda na početku.

Java Primjer programa za sortiranje niza pomoću algoritma sortiranja umetanjem:

Program u nastavku sortira niz {860, 8, 200, 9} i ispisuje tekući komentar, tako da je svaka usporedba i svaki pomak vidljiv. Spremi ga kao InsertionSortExample.java i kompajlirati ga s bilo kojim JDK 8 ili novijim izdanjem.

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

Pokretanje nastave proizvodi trace prikazano ovdje. Svaki Broj propusnice za sortiranje Linija označava jednu iteraciju vanjske petlje, a linija ispisana nakon svake zamjene prikazuje niz kakav stoji u tom trenutku.

Code Izlaz:

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

Vremenska i prostorna složenost sortiranja umetanjem

Učinkovitost sortiranja umetanjem uvelike ovisi o tome koliko je ulaz već uređen, zbog čega se najbolji i najgori slučaj razlikuju za cijeli red rasta.

Korištenje prostora je daleko jednostavnije. Samo pultovi i, j, n i key se stvaraju, a niz se preuređuje na mjestu, tako da je pomoćni prostor O(1) bez obzira koliko ulaz raste.

Budući da se unutarnja petlja zaustavlja čim naiđe na manju vrijednost, sortiranje umetanjem opisuje se kao adaptivno: što je ulaz bliži sortiranom redoslijedu, to se vrijeme izvođenja više pomiče prema linearnom.

Prednosti i nedostaci sortiranja umetanjem

Sortiranje umetanjem opstaje u produkcijskim bibliotekama unatoč slučaju kvadratnog prosjeka, jer su mu konstantni faktori mali, a ponašanje predvidljivo.

Prednosti

• Jednostavno za pisanje i lako za tracručno, što je prikladno za nastavu i intervjue.
• Stabilan, tako da zapisi koji dijele ključ zadržavaju svoj izvorni relativni redoslijed.
• Na mjestu, potrebno je samo O(1) dodatne memorije izvan ulaznog polja.
• Adaptivno, dostižući O(n) na podacima koji su već gotovo sortirani.
• Online, što znači da može sortirati popis dok novi elementi još uvijek pristižu.

Nedostaci

• Kvadratno vrijeme na slučajnom ili obrnuto uređenom ulazu čini ga neprikladnim za velike nizove.
• Svaki shift zapisuje u niz, pa premješta više podataka nego sortiranje odabirom.
• Sortiranje spajanjem i brzo sortiranje ga znatno nadmašuju nakon što ulaz prođe kroz nekoliko desetaka elemenata.

Praktično pravilo je posegnuti za sortiranjem umetanjem kada je niz malen, kada su podaci gotovo u redu ili kada je sortiranje "podijeli i vladaj" svelo particiju na nekoliko elemenata.

Sortiranje umetanjem u odnosu na Bubble Sortiranje vs. sortiranje odabirom

Sva tri algoritma su kvadratne usporedbe, ali se razlikuju po stabilnosti, načinu na koji reagiraju na uređeni ulaz i broju zapisa koje izvode.

Sortiranje odabirom pobjeđuje kada je pisanje skupo, jer izvodi najmanje zamjena. Sortiranje umetanjem pobjeđuje gotovo svugdje drugdje na ovoj skali, posebno na djelomično uređenim podacima, zbog čega se koriste knjižnična sortiranja poput onog iza. zajednički Java Vježbe a JDK interni dijelovi se prebacuju na njega za vrlo male particije.

Pitanja i odgovori