streamalism.org

1. Bemutatkozás

Ebben a rövid cikkben részletesen feltárjuk a Bubble Sort algoritmust, amelynek középpontjában a Java implementáció áll.

Ez az egyik legegyszerűbb rendezési algoritmus; az alapötlet azfolyamatosan cserélje a szomszédos elemeket egy tömbből, ha hibás sorrendben vannak, amíg a gyűjtemény rendezésre nem kerül.

Az adatstruktúra iterálásakor a kis elemek „buborékok” jelennek meg a lista tetején. Ezért a technikát buborékfajtának nevezik.

Mivel a válogatást cserével végzik, azt mondhatjuk, hogy helyben rendezi.

Is, ha két elemnek ugyanaz az értéke, a kapott adatok sorrendje megmarad - ami stabil fajta.

2. Módszertan

Mint korábban említettük, egy tömb rendezéséhez iterálunk rajta, miközben összehasonlítjuk a szomszédos elemeket, és szükség esetén felcseréljük őket. Egy tömb méretű n, fellépünk n-1 ilyen iterációk.

Vegyünk egy példát a módszertan megértéséhez. A tömböt növekvő sorrendben szeretnénk rendezni:

4 2 1 6 3 5

Az első iterációt a 4. és a 2. összehasonlításával kezdjük; határozottan nincsenek a megfelelő sorrendben. A csere a következőket eredményezné:

[2 4] 1 6 3 5

Most ismételve ugyanazt a 4 és 1 esetében:

2 [14] 6 3 5

A végéig folytatjuk:

2 1 [4 6] 3 5

2 1 4 [36] 5

2 1 4 3 [5 6]

Mint láthatjuk, az első iteráció végén az utolsó elemet a megfelelő helyen kaptuk. Most csak annyit kell tennünk, hogy ugyanazt az eljárást ismételjük meg további iterációkban. Kivéve a már rendezett elemeket kizárjuk.

A második iterációban a teljes tömböt iteráljuk, az utolsó elem kivételével. Hasonlóképpen, a 3. iterációnál kihagyjuk az utolsó 2 elemet. Általánosságban elmondható, hogy a k-edik iterációhoz indexig iterálunk n-k (kizárva). Végén a n-1 iterációk, megkapjuk a rendezett tömböt.

Most, hogy megérti a technikát, merüljünk el a megvalósításban.

3. Végrehajtás

Végezzük el a Java 8 megközelítéssel megvitatott példa tömb rendezését:

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

És egy gyors JUnit teszt az algoritmushoz:

@Test public void whenSortedWithBubbleSort_thenGetSortedArray () {Integer [] tömb = {2, 1, 4, 6, 3, 5}; Egész szám [] sortedArray = {1, 2, 3, 4, 5, 6}; BubbleSort bubbleSort = új BubbleSort (); bubbleSort.bubbleSort (tömb); assertArrayEquals (tömb, sortedArray); }

4. Komplexitás és optimalizálás

Ahogy látjuk, az átlag és a legrosszabb esetben, az idő bonyolultsága azO (n ^ 2).

Továbbá, a tér bonyolultsága, még a legrosszabb forgatókönyv esetén is, az O (1), mivel a Bubble sort algoritmus nem igényel külön memóriát és a rendezés az eredeti tömbben történik.

A megoldás alapos elemzésével ezt láthatjuk ha egy iterációban nem találhatók swapok, akkor nem kell tovább ismételnünk.

A korábban tárgyalt példa esetében a 2. iteráció után kapjuk:

1 2 3 4 5 6

A harmadik iterációban nincs szükségünk a szomszédos elempárok cseréjére. Így az összes fennmaradó iterációt kihagyhatjuk.

Rendezett tömb esetén az első iterációban nem lesz szükség cserére - ami azt jelenti, hogy leállíthatjuk a végrehajtást. Ez a legjobb eset és a Az algoritmus időbeli összetettsége O (n).

Most valósítsuk meg az optimalizált megoldást.

public void optimizedBubbleSort (Integer [] arr) {int i = 0, n = arr.length; logikai csereSzükséges = igaz; while (i <n - 1 && swapNeeded) {swapNeeded = hamis; for (int j = 1; j arr [j]) {int temp = arr [j - 1]; arr [j - 1] = arr [j]; arr [j] = hőmérséklet; swapNeeded = true; }} if (! swapNeeded) {törés; } i ++; }}

Ellenőrizzük az optimalizált algoritmus kimenetét:

@Test public void givenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray () {Integer [] tömb = {2, 1, 4, 6, 3, 5}; Egész szám [] sortedArray = {1, 2, 3, 4, 5, 6}; BubbleSort bubbleSort = új BubbleSort (); bubbleSort.optimizedBubbleSort (tömb); assertArrayEquals (tömb, sortedArray); }

5. Következtetés

Ebben az oktatóanyagban láthattuk, hogyan működik a Bubble Sort, és hogyan lehet megvalósítani a Java-ban. Láttuk azt is, hogyan lehet optimalizálni. Összefoglalva, ez egy helyben stabil algoritmus, időbeli összetettséggel:

• Legrosszabb és átlagos eset: O (n * n), ha a tömb fordított sorrendben van
• Legjobb eset: O (n), amikor a tömb már rendezve van

Az algoritmus népszerű a számítógépes grafikában, mivel képes észlelni a rendezés néhány apró hibáját. Például egy szinte rendezett tömbben csak két elemet kell felcserélni, hogy egy teljesen rendezett tömböt kapjunk. A Bubble Sort az ilyen hibákat lineáris időben képes kijavítani (azaz rendezni ezt a tömböt).

Mint mindig, az algoritmus megvalósításának kódja megtalálható a GitHubon.