Алгоритъм за сортиране на вмъкване в Java с примерна програма

Какво представлява алгоритъмът за сортиране чрез вмъкване?

Сортирането чрез вмъкване е прост алгоритъм за сортиране, подходящ за малки набори от данни. По време на всяка итерация алгоритъмът:

• Премахва елемент от масив.
• Сравнява го с най-голямата стойност в масив.
• Премества елемента на правилното му място.

Поведението отразява начина, по който играчът на карти подрежда ръката си: всяка нова карта се взема и избутва наляво покрай всяка по-голяма карта, докато не се окаже на правилното място. Тъй като цялото изместване се случва вътре в оригиналния масив, сортирането чрез вмъкване е едновременно на място и стабилно.

Принадлежи към същото семейство, подходящо за начинаещи Java сортиране на рутини като сортиране с балончета, но обикновено извършва много по-малко записи върху данни, които вече са частично подредени.

Процес на алгоритъм за сортиране на вмъкване

Ето как процесът на алгоритъма за сортиране на вмъкване работи графично:

Анимацията повтаря същите три стъпки Java програмата по-долу изпълнява. Таблицата за пробно изпълнение tracизписва тези стъпки върху примерния масив {860, 8, 200, 9}, точно както програмата ги отпечатва по време на изпълнение.

Обърнете внимание, че третият етап се нуждае от две сравнения, защото ключът 9 трябва да премине покрай две по-големи стойности. Следователно броят на сравненията нараства с това колко извън реда започва всеки елемент.

Java Примерна програма за сортиране на масив с помощта на алгоритъм за сортиране чрез вмъкване:

Програмата по-долу сортира масива {860, 8, 200, 9} и отпечатва текущ коментар, така че всяко сравнение и всяка промяна са видими. Запазете го като InsertionSortExample.java и го компилирайте с всяка JDK 8 или по-нова версия.

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

Изпълнението на класа води до tracе показано тук. Всеки Сортиране на номер на пропуск Редът маркира една итерация на външния цикъл, а редът, отпечатан след всяка размяна, показва масива такъв, какъвто е в този момент.

Code Изход:

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

Времева и пространствена сложност на сортирането чрез вмъкване

Производителността на сортирането чрез вмъкване зависи силно от това колко подреден е входът, поради което най-добрият и най-лошият случай се различават с цял порядък на растеж.

Използването на пространството е много по-лесно. Само плотовете i, j, n намлява key се създават и масивът се пренарежда на място, така че спомагателното пространство е O(1), независимо колко голям нараства входът.

Тъй като вътрешният цикъл спира веднага щом достигне по-малка стойност, сортирането с вмъкване се описва като адаптивно: колкото по-близо е входът до сортирания ред, толкова по-близо времето за изпълнение се приближава към линейно.

Предимства и недостатъци на сортирането чрез вмъкване

Сортирането чрез вмъкване оцелява в производствените библиотеки въпреки случая на квадратично средно, защото константните му фактори са малки и поведението му е предвидимо.

Предимства

• Лесно за писане и лесно за tracръчно, което е подходящо както за преподаване, така и за интервюта.
• Стабилен, така че записите, които споделят ключ, запазват първоначалния си относителен ред.
• На място, изискваща само O(1) допълнителна памет извън входния масив.
• Адаптивно, достигайки O(n) за данни, които вече са почти сортирани.
• Онлайн, което означава, че може да сортира списък, докато все още пристигат нови елементи.

Недостатъци

• Квадратичното време при произволен или обратно подреден вход го прави неподходящ за големи масиви.
• Всяко изместване записва в масива, така че премества повече данни, отколкото сортирането чрез селекция.
• Сортирането чрез сливане и бързото сортиране го превъзхождат удобно, след като входът премине през няколко десетки елемента.

Практическо правило е да се използва сортиране с вмъкване, когато масивът е малък, когато данните са почти подредени или когато сортирането „разделяй и владей“ е свело дяла до няколко елемента.

Сортиране чрез вмъкване срещу Bubble Сортиране срещу сортиране по избор

И трите алгоритъма са с квадратично сравнение, но се различават по стабилност, по начина, по който реагират на подреден вход, и по броя на записите, които извършват.

Сортирането с избор печели, когато записът е скъп, защото извършва най-малко размени. Сортирането с вмъкване печели почти навсякъде другаде в този мащаб, особено при частично подредени данни, поради което библиотечните сортировки, като този отзад, са... общ Java упражнения и вътрешните компоненти на JDK превключват към него за много малки дялове.

Въпроси и Отговори