streamalism.org

1. Uvod

U ovom brzom članku detaljno ćemo istražiti algoritam sortiranja mjehurića, usredotočujući se na implementaciju Jave.

Ovo je jedan od najjednostavnijih algoritama za sortiranje; srž ideje je danastavi mijenjati susjedne elemente niza ako su u netočnom redoslijedu dok se zbirka ne sortira.

Male stavke "oblačiće" se na vrh popisa dok ponavljamo strukturu podataka. Stoga je tehnika poznata kao sorta mjehurića.

Kako se sortiranje vrši zamjenom, možemo reći da vrši sortiranje na mjestu.

Također, ako dva elementa imaju iste vrijednosti, rezultirajući podaci imat će sačuvan redoslijed - što ga čini stabilnom sortom.

2. Metodologija

Kao što je ranije spomenuto, da bismo sortirali niz, prelazimo kroz njega uspoređujući susjedne elemente i po potrebi ih mijenjajući. Za niz veličina n, nastupamo n-1 takve ponavljanja.

Uzmimo primjer za razumijevanje metodologije. Željeli bismo sortirati niz po rastućem redoslijedu:

4 2 1 6 3 5

Prvu iteraciju započinjemo uspoređivanjem 4 i 2; definitivno nisu u pravilnom redoslijedu. Zamjena bi rezultirala:

[2 4] 1 6 3 5

Sada, ponavljajući isto za 4 i 1:

2 [14] 6 3 5

Nastavljamo to do kraja:

2 1 [4 6] 3 5

2 1 4 [36] 5

2 1 4 3 [5 6]

Kao što vidimo, na kraju prve iteracije dobili smo posljednji element na pravom mjestu. Sada, sve što trebamo učiniti je ponoviti isti postupak u daljnjim ponavljanjima. Osim, izuzimamo elemente koji su već sortirani.

U drugoj ćemo iteraciji proći kroz čitav niz osim zadnjeg elementa. Slično tome, za 3. iteraciju izostavljamo zadnja 2 elementa. Općenito, za k-tu iteraciju ponavljamo indeks n-k (isključen). Na kraju n-1 iteracije, dobit ćemo sortirani niz.

Sad kad razumijete tehniku, zaronimo u provedbu.

3. Provedba

Primijenimo sortiranje za primjer niza o kojem smo razgovarali koristeći pristup 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;}}); }

I brzi JUnit test za algoritam:

@Test javna void whenSortedWithBubbleSort_thenGetSortedArray () {Integer [] niz = {2, 1, 4, 6, 3, 5}; Cijeli broj [] sortedArray = {1, 2, 3, 4, 5, 6}; BubbleSort bubbleSort = novi BubbleSort (); bubbleSort.bubbleSort (niz); assertArrayEquals (niz, sortiraniArray); }

4. Složenost i optimizacija

Kao što vidimo, za prosječni i najgori slučaj, složenost vremena jeO (n ^ 2).

U Dodatku, složenost prostora, čak iu najgorem scenariju, je O (1) jer algoritam Bubble sort ne zahtijeva dodatnu memoriju a sortiranje se odvija u izvornom nizu.

Pažljivom analizom rješenja možemo to vidjeti ako u iteraciji nisu pronađene zamjene, ne trebamo ponavljati dalje.

U slučaju prethodno raspravljenog primjera, nakon 2. iteracije dobivamo:

1 2 3 4 5 6

U trećoj iteraciji ne trebamo zamijeniti nijedan par susjednih elemenata. Tako možemo preskočiti sve preostale ponavljanja.

U slučaju razvrstanog niza, zamjena neće biti potrebna u prvoj iteraciji - što znači da možemo zaustaviti izvršenje. Ovo je najbolji slučaj i vremenska složenost algoritma je O (n).

Sada, implementirajmo optimizirano rješenje.

javna praznina optimizedBubbleSort (Integer [] arr) {int i = 0, n = arr.length; logička swapNeeded = true; while (i <n - 1 && swapNeeded) {swapNeeded = false; za (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 ++; }}

Provjerimo izlaz za optimizirani algoritam:

@Test javna praznina givenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray () {Integer [] niz = {2, 1, 4, 6, 3, 5}; Cijeli broj [] sortedArray = {1, 2, 3, 4, 5, 6}; BubbleSort bubbleSort = novi BubbleSort (); bubbleSort.optimizedBubbleSort (niz); assertArrayEquals (niz, sortiraniArray); }

5. Zaključak

U ovom uputstvu vidjeli smo kako funkcionira Bubble Sort i njegova implementacija u Javi. Vidjeli smo i kako se to može optimizirati. Da rezimiramo, to je stabilni algoritam na mjestu, s vremenskom složenošću:

• Najgori i prosječan slučaj: O (n * n), kada je niz obrnutim redoslijedom
• Najbolji slučaj: O (n), kada je niz već sortiran

Algoritam je popularan u računalnoj grafici zbog svoje sposobnosti otkrivanja nekih malih pogrešaka u sortiranju. Na primjer, u gotovo razvrstanom polju, samo dva elementa trebaju se zamijeniti da bi se dobio potpuno razvrstani niz. Bubble Sort može ispraviti takve pogreške (tj. Razvrstati ovaj niz) u linearnom vremenu.

Kao i uvijek, kod za implementaciju ovog algoritma možete pronaći na GitHub-u.