streamalism.org

1. Introduksjon

I denne raske artikkelen vil vi utforske Bubble Sort-algoritmen i detalj, med fokus på en Java-implementering.

Dette er en av de mest enkle sorteringsalgoritmene; kjernetanken er åfortsett å bytte tilstøtende elementer av en matrise hvis de er i feil rekkefølge til samlingen er sortert.

Små gjenstander "bobler" til toppen av listen når vi gjentar datastrukturen. Derfor er teknikken kjent som boblesortering.

Ettersom sortering utføres ved å bytte, kan vi si at den utfører sortering på stedet.

Også, hvis to elementer har samme verdier, vil resulterende data få sin ordre bevaret - noe som gjør det til en stabil sortering.

2. Metodikk

Som nevnt tidligere, for å sortere en matrise, gjentar vi den mens vi sammenligner tilstøtende elementer, og bytter dem om nødvendig. For en rekke størrelser n, vi opptrer n-1 slike gjentakelser.

La oss ta et eksempel for å forstå metodikken. Vi vil sortere matrisen i stigende rekkefølge:

4 2 1 6 3 5

Vi starter den første iterasjonen med å sammenligne 4 og 2; de er definitivt ikke i riktig rekkefølge. Bytte vil resultere i:

[2 4] 1 6 3 5

Gjenta nå det samme i 4 og 1:

2 [14] 6 3 5

Vi fortsetter å gjøre det til slutten:

2 1 [4 6] 3 5

2 1 4 [36] 5

2 1 4 3 [5 6]

Som vi kan se, på slutten av den første iterasjonen, fikk vi det siste elementet på sitt rette sted. Nå er alt vi trenger å gjøre å gjenta den samme prosedyren i ytterligere iterasjoner. Bortsett fra at vi ekskluderer elementene som allerede er sortert.

I den andre iterasjonen gjentas vi gjennom hele matrisen bortsett fra det siste elementet. Tilsvarende, for tredje iterasjon, utelater vi de to siste elementene. Generelt, for den femte iterasjonen, itererer vi til indeksen n-k (ekskludert). Ved slutten av n-1 iterasjoner, får vi den sorterte matrisen.

Nå som du forstår teknikken, la oss dykke ned i implementeringen.

3. Gjennomføring

La oss implementere sorteringen for eksempelmatrisen vi diskuterte ved hjelp av Java 8-tilnærmingen:

ugyldig bubbleSort (Heltall [] arr) {int n = arrlengde; 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;}}); }

Og en rask JUnit-test for algoritmen:

@Test offentlig ugyldig nårSortedWithBubbleSort_thenGetSortedArray () {Integer [] array = {2, 1, 4, 6, 3, 5}; Heltall [] sortedArray = {1, 2, 3, 4, 5, 6}; BubbleSort bubbleSort = ny BubbleSort (); bubbleSort.bubbleSort (matrise); assertArrayEquals (array, sortedArray); }

4. Kompleksitet og optimalisering

Som vi kan se, for gjennomsnittet og verste fall, tidskompleksiteten erO (n ^ 2).

I tillegg, romkompleksiteten, selv i det verste scenariet, er O (1) ettersom boblesorteringsalgoritmen ikke krever noe ekstra minne og sorteringen foregår i den opprinnelige matrisen.

Ved å analysere løsningen nøye, kan vi se det hvis det ikke finnes bytter i en iterasjon, trenger vi ikke å gjenta videre.

I tilfelle eksemplet diskutert tidligere, etter 2. iterasjon, får vi:

1 2 3 4 5 6

I den tredje iterasjonen trenger vi ikke å bytte noen par tilstøtende elementer. Så vi kan hoppe over alle gjenværende iterasjoner.

I tilfelle en sortert matrise, vil ikke bytte være nødvendig i selve den første iterasjonen - noe som betyr at vi kan stoppe utførelsen. Dette er best case scenario og tidskompleksiteten til algoritmen er O (n).

La oss nå implementere den optimaliserte løsningen.

public void optimizedBubbleSort (Integer [] arr) {int i = 0, n = arr.length; boolsk bytteNeeded = true; mens (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; }} hvis (! swapNeeded) {pause; } i ++; }}

La oss sjekke utdataene for den optimaliserte algoritmen:

@Test offentlig ugyldighet gittIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray () {Integer [] array = {2, 1, 4, 6, 3, 5}; Heltall [] sortedArray = {1, 2, 3, 4, 5, 6}; BubbleSort bubbleSort = ny BubbleSort (); bubbleSort.optimizedBubbleSort (array); assertArrayEquals (array, sortedArray); }

5. Konklusjon

I denne veiledningen så vi hvordan Bubble Sort fungerer, og implementeringen i Java. Vi så også hvordan det kan optimaliseres. For å oppsummere er det en stabil algoritme på stedet, med tidskompleksitet:

• Verste og gjennomsnittlige tilfelle: O (n * n), når matrisen er i omvendt rekkefølge
• Beste tilfelle: O (n), når matrisen allerede er sortert

Algoritmen er populær innen datagrafikk på grunn av dens evne til å oppdage noen små feil ved sortering. For eksempel, i et nesten sortert utvalg, trenger bare to elementer å byttes for å få et helt sortert utvalg. Bubblesortering kan fikse slike feil (dvs. sortere denne matrisen) på lineær tid.

Som alltid kan koden for implementering av denne algoritmen finnes på GitHub.