streamalism.org

1. Úvod

V tomto rýchlom článku sa podrobne pozrieme na algoritmus Bubble Sort so zameraním na implementáciu Java.

Toto je jeden z najpriamočiarejších algoritmov triedenia; hlavnou myšlienkou jeneustále vymieňajte susedné prvky poľa, ak sú v nesprávnom poradí, kým nie je kolekcia zoradená.

Malé položky „bublinkujú“ na začiatok zoznamu pri opakovaní dátovej štruktúry. Preto je táto technika známa ako bublinková.

Keďže triedenie sa vykonáva výmenou, môžeme povedať, že sa vykonáva triedenie na mieste.

Tiež ak majú dva prvky rovnaké hodnoty, výsledné údaje sa zachovajú v poradí - čo z neho robí stabilný druh.

2. Metodika

Ako už bolo spomenuté, na zoradenie poľa ho iterujeme pri porovnávaní susedných prvkov a v prípade potreby ich zameníme. Pre pole veľkosti n, vystupujeme n-1 také iterácie.

Zoberme si príklad na pochopenie metodiky. Radili by sme pole vo vzostupnom poradí:

4 2 1 6 3 5

Prvú iteráciu začneme porovnaním 4 a 2; rozhodne nie sú v správnom poradí. Výsledkom výmeny bude:

[2 4] 1 6 3 5

Teraz opakujeme to isté pre 4 a 1:

2 [14] 6 3 5

Robíme to až do konca:

2 1 [4 6] 3 5

2 1 4 [36] 5

2 1 4 3 [5 6]

Ako vidíme, na konci prvej iterácie sme dostali posledný prvok na správne miesto. Všetko, čo musíme urobiť, je zopakovať ten istý postup v ďalších iteráciách. Okrem toho vylučujeme prvky, ktoré sú už zoradené.

V druhej iterácii budeme iterovať cez celé pole okrem posledného prvku. Podobne pre 3. iteráciu vynecháme posledné 2 prvky. Všeobecne pre k-tú iteráciu iterujeme do indexu n-k (vylúčené). Na konci n-1 iterácie, dostaneme zoradené pole.

Teraz, keď už tejto technike rozumiete, sa ponoríme do implementácie.

3. Implementácia

Poďme implementovať triedenie pre vzorové pole, o ktorom sme diskutovali pomocou prístupu 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 teplota = arr [j]; arr [j] = arr [j - 1]; arr [j - 1] = teplota;}}); }

A rýchly test JUnit algoritmu:

@Test public void whenSortedWithBubbleSort_thenGetSortedArray () {Integer [] pole = {2, 1, 4, 6, 3, 5}; Celé číslo [] triedenéArray = {1, 2, 3, 4, 5, 6}; BubbleSort bubbleSort = nový BubbleSort (); bubbleSort.bubbleSort (pole); assertArrayEquals (pole, sortArray); }

4. Zložitosť a optimalizácia

Ako vidíme, pre priemerný a najhorší prípad, časová zložitosť jeO (n ^ 2).

Navyše, zložitosť priestoru, aj v najhoršom scenári, je O (1), pretože algoritmus triedenia bublín nevyžaduje žiadnu ďalšiu pamäť a triedenie prebieha v pôvodnom poli.

Dôslednou analýzou riešenia to môžeme vidieť ak sa v iterácii nenájdu žiadne swapy, nemusíme ďalej iterovať.

V prípade príkladu diskutovaného skôr, po 2. iterácii, dostaneme:

1 2 3 4 5 6

V tretej iterácii nepotrebujeme zameniť žiadny pár susedných prvkov. Takže môžeme preskočiť všetky zostávajúce iterácie.

V prípade zoradeného poľa nebude pri prvej iterácii potrebná zámena - čo znamená, že môžeme zastaviť vykonávanie. Toto je najlepší scenár a časová zložitosť algoritmu je O (n).

Poďme teraz implementovať optimalizované riešenie.

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

Poďme skontrolovať výstup pre optimalizovaný algoritmus:

@Test public void givenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray () {Integer [] pole = {2, 1, 4, 6, 3, 5}; Celé číslo [] triedenéArray = {1, 2, 3, 4, 5, 6}; BubbleSort bubbleSort = nový BubbleSort (); bubbleSort.optimizedBubbleSort (pole); assertArrayEquals (pole, sortArray); }

5. Záver

V tomto tutoriáli sme videli, ako funguje Bubble Sort a jeho implementácia v Jave. Tiež sme videli, ako sa dá optimalizovať. Ak to zhrnieme, jedná sa o stabilný algoritmus na mieste s časovou zložitosťou:

• Najhorší a priemerný prípad: O (n * n), keď je pole v opačnom poradí
• Najlepší prípad: O (n), keď je pole už zoradené

Algoritmus je v počítačovej grafike populárny vďaka svojej schopnosti zistiť malé chyby pri triedení. Napríklad v takmer zoradenom poli je potrebné vymeniť iba dva prvky, aby ste získali úplne zoradené pole. Bubble Sort dokáže takéto chyby (tj. Zoradiť toto pole) opraviť v lineárnom čase.

Ako vždy, kód na implementáciu tohto algoritmu nájdete na GitHub.