Сортиране на балончета в Java

1. Въведение

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

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

Малките елементи се „пускат“ в горната част на списъка, докато повтаряме структурата на данните. Следователно техниката е известна като сортиране на балончета.

Тъй като сортирането се извършва чрез размяна, можем да кажем, че извършва сортиране на място.

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

2. Методология

Както бе споменато по-рано, за да сортираме масив, ние го итерираме, като сравняваме съседни елементи и ги разменяме, ако е необходимо. За масив с размер n извършваме n-1 такива итерации.

Нека вземем пример, за да разберем методологията. Бихме искали да сортираме масива във възходящ ред:

4 2 1 6 3 5

Започваме първата итерация чрез сравняване на 4 и 2; определено не са в правилния ред. Размяната би довела до:

[2 4] 1 6 3 5

Сега, повтаряйки същото за 4 и 1:

2 [1 4] 6 3 5

Продължаваме да го правим до края:

2 1 [ 4 6] 3 5

2 1 4 [3 6] 5

2 1 4 3 [5 6]

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

Във втората итерация ще прегледаме целия масив, с изключение на последния елемент. По същия начин за 3-та итерация пропускаме последните 2 елемента. Като цяло, за k-та итерация, итерираме до индекс nk (изключен). В края на n-1 итерации ще получим сортирания масив.

Сега, когато разбирате техниката, нека се потопим в изпълнението.

3. Прилагане

Нека реализираме сортирането за примерния масив, който обсъдихме, използвайки подхода Java 8:

void bubbleSort(Integer[] arr) { int n = arr.length; IntStream.range(0, n - 1) .flatMap(i -> IntStream.range(1, n - i)) .forEach(j -> { if (arr[j - 1] > arr[j]) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } }); }

И бърз JUnit тест за алгоритъма:

@Test public void whenSortedWithBubbleSort_thenGetSortedArray() { Integer[] array = { 2, 1, 4, 6, 3, 5 }; Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 }; BubbleSort bubbleSort = new BubbleSort(); bubbleSort.bubbleSort(array); assertArrayEquals(array, sortedArray); }

4. Сложност и оптимизация

Както можем да видим, за средната и най-лошия случай , сложността време е O (N ^ 2) .

В допълнение, сложността на пространството , дори в най-лошия сценарий, е O (1), тъй като алгоритъмът за сортиране на балончета не изисква допълнителна памет и сортирането се извършва в оригиналния масив.

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

В случай на примера, обсъден по-рано, след 2-ра итерация получаваме:

1 2 3 4 5 6

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

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

Сега, нека внедрим оптимизираното решение.

public void optimizedBubbleSort(Integer[] arr) { int i = 0, n = arr.length; boolean swapNeeded = true; while (i < n - 1 && swapNeeded) { swapNeeded = false; for (int j = 1; j  arr[j]) { int temp = arr[j - 1]; arr[j - 1] = arr[j]; arr[j] = temp; swapNeeded = true; } } if(!swapNeeded) { break; } i++; } }

Нека проверим резултата за оптимизирания алгоритъм:

@Test public void givenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray() { Integer[] array = { 2, 1, 4, 6, 3, 5 }; Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 }; BubbleSort bubbleSort = new BubbleSort(); bubbleSort.optimizedBubbleSort(array); assertArrayEquals(array, sortedArray); }

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

В този урок видяхме как работи Bubble Sort и неговата реализация в Java. Видяхме и как може да бъде оптимизиран. За да обобщим, това е стабилен на място алгоритъм със сложност във времето:

  • Най-лош и среден случай: O (n * n), когато масивът е в обратен ред
  • Най-добрият случай: O (n), когато масивът вече е сортиран

Алгоритъмът е популярен в компютърната графика, поради способността му да открива някои малки грешки при сортирането. Например в почти сортиран масив трябва да се разменят само два елемента, за да се получи напълно сортиран масив. Bubble Sort може да поправи такива грешки (т.е. да сортира този масив) за линейно време.

Както винаги, кодът за изпълнение на този алгоритъм може да бъде намерен в GitHub.