Сортиране на вмъкване в Java

Програмиране

1. Общ преглед

В този урок ще обсъдим алгоритъма за сортиране на вмъкване и ще разгледаме неговото изпълнение на Java .

Insertion Sort е ефективен алгоритъм за поръчка на малък брой артикули. Този метод се основава на начина, по който играчите на карти сортират ръка на игрални карти.

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

Нека започнем с разбирането на стъпките на алгоритъма във форма на псевдокод.

2. Псевдокод

Ще представим нашия псевдокод за сортиране на вмъкване като процедура, наречена INSERTION-SORT , като за параметър ще вземем масив A [1 .. n] от n елементи, които трябва да бъдат сортирани. Алгоритъмът сортира входния масив на място (чрез пренареждане на елементите в масива A).

След като процедурата приключи, входният масив A съдържа пермутация на входната последователност, но в сортиран ред:

INSERTION-SORT(A) for i=2 to A.length key = A[i] j = i - 1 while j > 0 and A[j] > key A[j+1] = A[j] j = j - 1 A[j + 1] = key

Нека да разгледаме накратко алгоритъма по-горе.

Индексът i показва позицията на текущия елемент в масива за обработка.

Започваме от втория елемент, тъй като по дефиниция се смята, че масив с един елемент е сортиран. Елементът с индекс i се нарича ключ . След като има ключа, втората част на алгоритъма се занимава с намирането на правилния му индекс. Ако ключът е по-малък от стойността на елемента с индекс j , тогава ключът се премества с една позиция вляво. Процесът продължава до случая, когато стигнем до елемент, който е по-малък от ключа.

Важно е да се отбележи, че преди да започне итерацията за намиране на правилната позиция на ключа при индекс i , масивът A [1 .. j - 1] вече е сортиран .

3. Императивно изпълнение

За императивния случай ще напишем функция, наречена insertionSortImperative , като вземем като параметър масив от цели числа. Функцията започва итерация по масива от втория елемент.

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

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

public static void insertionSortImperative(int[] input) { for (int i = 1; i 
    
     = 0 && input[j] > key) { input[j + 1] = input[j]; j = j - 1; } input[j + 1] = key; } }

След това нека създадем тест за метода по-горе:

@Test public void givenUnsortedArray_whenInsertionSortImperative_thenSortedAsc() { int[] input = {6, 2, 3, 4, 5, 1}; InsertionSort.insertionSortImperative(input); int[] expected = {1, 2, 3, 4, 5, 6}; assertArrayEquals("the two arrays are not equal", expected, input); }

Горният тест доказва, че алгоритъмът сортира правилно във възходящ ред входния масив .

4. Рекурсивно изпълнение

Функцията за рекурсивния случай се нарича insertionSortR екурсивна и приема като вход масив от цели числа (същият като за императивния случай).

Разликата тук от императивния случай (въпреки факта, че е рекурсивен) е, че той извиква претоварена функция с втори аргумент, равен на броя на елементите за сортиране.

Тъй като искаме да сортираме пълния масив, ще предадем няколко елемента, равни на дължината му:

public static void insertionSortRecursive(int[] input) { insertionSortRecursive(input, input.length); }

Рекурсивният случай е малко по-труден. Основният случай възниква, когато се опитваме да сортираме масив с един елемент. В този случай не правим нищо.

Всички последващи рекурсивни повиквания сортират предварително дефинирана част от входния масив - започвайки от втория елемент, докато стигнем до края на масива:

private static void insertionSortRecursive(int[] input, int i) { if (i <= 1) { return; } insertionSortRecursive(input, i - 1); int key = input[i - 1]; int j = i - 2; while (j>= 0 && input[j] > key) { input[j + 1] = input[j]; j = j - 1; } input[j + 1] = key; }

И ето как изглежда стека на повикванията за входен масив от 6 елемента:

insertionSortRecursive(input, 6) insertionSortRecursive(input, 5) and insert the 6th item into the sorted array insertionSortRecursive(input, 4) and insert the 5th item into the sorted array insertionSortRecursive(input, 3) and insert the 4th item into the sorted array insertionSortRecursive(input, 2) and insert the 3rd item into the sorted array insertionSortRecursive(input, 1) and insert the 2nd item into the sorted array

Нека да видим и теста за него:

@Test public void givenUnsortedArray_whenInsertionSortRecursively_thenSortedAsc() { int[] input = {6, 4, 5, 2, 3, 1}; InsertionSort.insertionSortRecursive(input); int[] expected = {1, 2, 3, 4, 5, 6}; assertArrayEquals("the two arrays are not equal", expected, input); }

Горният тест доказва, че алгоритъмът сортира правилно във възходящ ред входния масив .

5. Сложност във времето и пространството

Времето, необходимо на процедурата INSERTION-SORT за изпълнение, е O (n ^ 2) . За всеки нов елемент ние итерираме отдясно наляво върху вече сортираната част от масива, за да намерим правилната му позиция. След това го вмъкваме, като изместваме елементите с една позиция надясно.

Алгоритъмът сортира на място, така че неговата сложност в пространството е O (1) за императивното изпълнение и O (n) за рекурсивното изпълнение.

6. Заключение

В този урок видяхме как да приложим сортиране на вмъкване.

Този алгоритъм е полезен за сортиране на малък брой елементи. Става неефективно при сортиране на входни последователности с повече от 100 елемента.

Имайте предвид, че въпреки своята квадратична сложност, той сортира на място, без да се нуждае от помощно пространство, какъвто е случаят при сортиране чрез сливане .

Целият код може да бъде намерен в GitHub.