Algoritm de sortare inserare în Java cu Exemplu de program

Ce este algoritmul de sortare prin inserție?

Sortarea prin inserție este un algoritm de sortare simplu, potrivit pentru seturi mici de date. În timpul fiecărei iterații, algoritmul:

• Îndepărtează un element dintr-o matrice.
• O compară cu cea mai mare valoare din mulțime.
• Mută ​​elementul în locația corectă.

Comportamentul reflectă modul în care un jucător de cărți își aranjează mâna: fiecare carte nouă este ridicată și împinsă la stânga, trecând pe lângă fiecare carte mai mare, până când se oprește în locul potrivit. Deoarece toate deplasările au loc în interiorul matricei originale, sortarea prin inserție este atât in-place (pe loc), cât și stabilă.

Aparține aceleiași familii de articole prietenoase pentru începători Java rutine de sortare ca sortare cu bule, totuși, în mod normal, efectuează mult mai puține scrieri asupra datelor care sunt deja parțial ordonate.

Procesul algoritmului de sortare prin inserare

Iată cum funcționează grafic procesul algoritmului de sortare prin inserare:

Animația repetă aceiași trei pași Java se efectuează programul de mai jos. Tabelul de simulare tracafișează acei pași pe matricea eșantion {860, 8, 200, 9}, exact așa cum programul îi afișează la momentul execuției.

Observați că trecerea 3 necesită două comparații deoarece cheia 9 trebuie să treacă de două valori mai mari. Prin urmare, numărul de comparații crește odată cu cât de departe de ordine începe fiecare element.

Java Exemplu de program pentru a sorta o matrice folosind algoritmul de sortare prin inserție:

Programul de mai jos sortează tabloul {860, 8, 200, 9} și afișează un comentariu continuu, astfel încât fiecare comparație și fiecare deplasare să fie vizibilă. Salvați-l ca InsertionSortExample.java și compilați-l cu orice JDK 8 sau o versiune ulterioară.

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

Rularea clasei produce trace prezentat aici. Fiecare Sortare număr permis Linia marchează o iterație a buclei exterioare, iar linia imprimată după fiecare schimbare arată matricea așa cum se prezintă în acel moment.

Code ieșire:

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

Complexitatea timpului și spațiului sortării prin inserție

Performanța sortării prin inserție depinde în mare măsură de cât de ordonată este deja intrarea, motiv pentru care cel mai bun caz și cel mai rău caz diferă printr-un întreg ordin de creștere.

Utilizarea spațiului este mult mai simplă. Doar contoarele i, j, n și key sunt create, iar matricea este rearanjată la locul ei, deci spațiul auxiliar este O(1) indiferent de cât de mare crește intrarea.

Deoarece bucla interioară se oprește imediat ce întâlnește o valoare mai mică, sortarea prin inserție este descrisă ca adaptivă: cu cât intrarea este mai aproape de ordinea sortată, cu atât timpul de execuție se apropie mai mult de liniar.

Avantajele și dezavantajele sortării prin inserție

Sortarea prin inserție supraviețuiește în bibliotecile de producție în ciuda cazului său mediu pătratic, deoarece factorii săi constanți sunt mici, iar comportamentul său este previzibil.

Avantaje

• Simplu de scris și ușor de trace de mână, ceea ce îl potrivește atât predării, cât și interviurilor.
• Stabil, astfel încât înregistrările care partajează o cheie își păstrează ordinea relativă originală.
• In situ, necesitând doar O(1) memorie suplimentară dincolo de matricea de intrare.
• Adaptiv, ajungând la O(n) pe date care sunt deja aproape sortate.
• Online, adică poate sorta o listă în timp ce elemente noi încă sosesc.

Dezavantaje

• Timpul pătratic pe intrări aleatorii sau ordonate invers îl face nepotrivit pentru matricele mari.
• Fiecare deplasare scrie în matrice, deci mută mai multe date decât o face sortarea prin selecție.
• Sortarea prin îmbinare și sortarea rapidă o depășesc confortabil odată ce intrarea trece prin câteva zeci de elemente.

O regulă practică este să se apeleze la sortarea prin inserție atunci când matricea este mică, când datele sunt aproape în ordine sau când o sortare de tip împărțire și cucerire a redus o partiție la o mână de elemente.

Sortare prin inserție vs. BubblSortare e vs. sortare prin selecție

Toți cei trei algoritmi sunt sortări prin comparație pătratică, însă diferă în ceea ce privește stabilitatea, modul în care reacționează la intrările ordonate și numărul de scrieri pe care le efectuează.

Sortarea prin selecție câștigă atunci când o scriere este costisitoare, deoarece efectuează cele mai puține schimbări. Sortarea prin inserție câștigă aproape oriunde altundeva la această scară, în special pe date parțial ordonate, motiv pentru care sortările de bibliotecă, cum ar fi cea din spatele comun Java Exerciții iar componentele interne ale JDK-ului trec la acesta pentru partiții foarte mici.

Întrebări frecvente