Lisäyslajittelualgoritmi sisään Java Ohjelmaesimerkin kanssa

Mikä on lisäyslajittelualgoritmi?

Lisäyslajittelu on yksinkertainen lajittelualgoritmi, joka sopii pienille tietojoukoille. Jokaisen iteraation aikana algoritmi:

• Poistaa elementin taulukosta.
• Vertaa sitä alueen suurimpaan arvoon ryhmä.
• Siirtää elementin oikeaan paikkaan.

Toiminta peilaa tapaa, jolla kortinpelaaja järjestää käden: jokainen uusi kortti nostetaan ja työnnetään vasemmalle jokaisen suuremman kortin ohi, kunnes se on oikeassa paikassa. Koska kaikki siirtäminen tapahtuu alkuperäisen taulukon sisällä, lisäyslajittelu on sekä paikallaan oleva että vakaa.

Se kuuluu samaan aloittelijaystävällisten tuotteiden perheeseen. Java lajittelurutiinit kuten kupla, mutta se suorittaa yleensä paljon vähemmän kirjoituksia datalle, joka on jo osittain järjestetty.

Lisäyslajittelualgoritmiprosessi

Tässä on, kuinka lisäyslajittelualgoritmiprosessi toimii graafisesti:

Animaatio toistaa samat kolme vaihetta Java alla oleva ohjelma suorittaa. Koeajopöytä tracSuorittaa nuo vaiheet esimerkkitaulukossa {860, 8, 200, 9} täsmälleen sellaisena kuin ohjelma tulostaa ne suorituksen aikana.

Huomaa, että kolmannessa vaiheessa tarvitaan kaksi vertailua, koska avaimen 9 on kuljettava kahden suuremman arvon ohi. Vertailujen määrä siis kasvaa sen mukaan, kuinka kaukana epäjärjestyksessä kukin elementti alkaa.

Java Ohjelmaesimerkki taulukon lajitteluun lisäyslajittelualgoritmin avulla:

Alla oleva ohjelma lajittelee taulukon {860, 8, 200, 9} ja tulostaa juoksevan kommentin, joten jokainen vertailu ja jokainen siirto on näkyvissä. Tallenna se nimellä InsertionSortExample.java ja käännä se millä tahansa JDK 8:lla tai uudemmalla versiolla.

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

Kurssin suorittaminen tuottaa trace näkyy tässä. Jokainen Lajittelupassin numero rivi merkitsee ulomman silmukan yhtä iteraatiota, ja jokaisen vaihdon jälkeen tulostettava rivi näyttää taulukon sellaisena kuin se on sillä hetkellä.

Code lähtö:

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

Lisäyslajittelun aika- ja paikkakompleksisuus

Lisäyslajittelun suorituskyky riippuu suuresti syötteen jo valmiiksi järjestäytyneestä arvosta, minkä vuoksi paras ja huonoin tapaus eroavat toisistaan ​​kokonaisen kasvukertaluvun verran.

Tilankäyttö on paljon yksinkertaisempaa. Vain tiskipöydät i, j, n ja key luodaan ja taulukko järjestetään uudelleen paikalleen, joten aputila on O(1) riippumatta siitä, kuinka suureksi syöte kasvaa.

Koska sisempi silmukka pysähtyy heti, kun se saavuttaa pienemmän arvon, lisäyslajittelua kuvataan adaptiiviseksi: mitä lähempänä syöte on lajiteltua järjestystä, sitä lähemmäksi suoritusaika liikkuu lineaarista.

Lisäyslajittelun edut ja haitat

Lisäyslajittelu säilyy tuotantokirjastoissa neliöllisen keskiarvon tapauksestaan ​​huolimatta, koska sen vakiotekijät ovat pieniä ja sen käyttäytyminen on ennustettavaa.

edut

• Helppo kirjoittaa ja helppo trackäsin, mikä sopii sekä opetukseen että haastatteluihin.
• Vakaa, joten saman avaimen jakavien tietueiden alkuperäinen järjestys säilyy.
• Paikallaan, tarvitsee vain O(1) lisämuistia syöttötaulukon lisäksi.
• Adaptiivinen, saavuttaa O(n):n datassa, joka on jo lähes lajiteltu.
• Verkossa, mikä tarkoittaa, että se voi lajitella listaa jo uusien elementtien saapuessa.

Haitat

• Satunnaisen tai käänteisessä järjestyksessä olevan syötteen neliöllinen aika tekee siitä sopimattoman suurille taulukoille.
• Jokainen shift kirjoittaa taulukkoon, joten se siirtää enemmän dataa kuin valintalajittelu.
• Yhdistämislajittelu ja pikalajittelu suoriutuvat siitä selvästi paremmin, kun syöte läpäisee muutaman kymmenen elementin.

Käytännöllinen sääntö on turvautua lisäyslajitteluun, kun taulukko on pieni, kun tiedot ovat lähes järjestyksessä tai kun hajoita ja hallitse -lajittelu on supistanut osion muutamaan alkioon.

Lisäyslajittelu vs. Bubble-lajittelu vs. valintalajittelu

Kaikki kolme algoritmia ovat toisen asteen vertailulajitteluja, mutta ne eroavat toisistaan ​​vakauden, järjestettyyn syötteeseen reagoinnin ja suorittamiensa kirjoituskertojen määrän suhteen.

Valintalajittelu voittaa, kun kirjoitus on kallista, koska se suorittaa vähiten vaihtoja. Lisäyslajittelu voittaa lähes kaikkialla muualla tässä mittakaavassa, erityisesti osittain järjestetyssä datassa, minkä vuoksi kirjastolajittelut, kuten takana oleva yhteinen Java harjoitukset ja JDK:n sisäiset osat siirtyvät siihen hyvin pienille osioille.

UKK