streamalism.org

1. Introduktion

I denne hurtige artikel vil vi udforske Bubble Sort-algoritmen i detaljer og fokusere på en Java-implementering.

Dette er en af ​​de mest enkle sorteringsalgoritmer; kerneideen er atfortsæt med at bytte tilstødende elementer af en matrix, hvis de er i en forkert rækkefølge, indtil samlingen er sorteret.

Små emner “bobler” øverst på listen, når vi gentager datastrukturen. Derfor er teknikken kendt som boblesortering.

Da sortering udføres ved at bytte, kan vi sige, at den udfører sortering på stedet.

Også, hvis to elementer har samme værdier, bevares rækkefølgen af ​​data - hvilket gør det til en stabil slags.

2. Metodologi

Som nævnt tidligere gentager vi det for at sortere en matrix, mens vi sammenligner tilstødende elementer og bytter dem om nødvendigt. For en række størrelser n, vi udfører n-1 sådanne gentagelser.

Lad os tage et eksempel for at forstå metoden. Vi vil gerne sortere arrayet i stigende rækkefølge:

4 2 1 6 3 5

Vi starter den første iteration ved at sammenligne 4 og 2; de er bestemt ikke i den rette rækkefølge. Bytte ville resultere i:

[2 4] 1 6 3 5

Gentag nu det samme i 4 og 1:

2 [14] 6 3 5

Vi fortsætter med at gøre det indtil slutningen:

2 1 [4 6] 3 5

2 1 4 [36] 5

2 1 4 3 [5 6]

Som vi kan se, i slutningen af ​​den første iteration, fik vi det sidste element på det rette sted. Nu er alt, hvad vi skal gøre, at gentage den samme procedure i yderligere iterationer. Bortset fra udelukker vi de elementer, der allerede er sorteret.

I den anden iteration gentages vi gennem hele arrayet undtagen det sidste element. Tilsvarende for 3. iteration udelader vi de sidste 2 elementer. Generelt for it-iteration gentager vi till index n-k (ekskluderet). Ved udgangen af n-1 iterationer, får vi det sorterede array.

Nu hvor du forstår teknikken, lad os dykke ned i implementeringen.

3. Implementering

Lad os implementere sorteringen til det eksempel array, vi diskuterede ved hjælp af Java 8 tilgang:

ugyldig bubbleSort (Heltal [] arr) {int n = arrlængde; 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 hurtig JUnit-test for algoritmen:

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

4. Kompleksitet og optimering

Som vi kan se, i gennemsnit og i værste fald, tidskompleksiteten erO (n ^ 2).

Ud over, rumkompleksiteten, selv i det værste scenarie, er O (1), da Bubblesorteringsalgoritme ikke kræver ekstra hukommelse og sorteringen finder sted i den oprindelige matrix.

Ved at analysere løsningen omhyggeligt kan vi se det hvis der ikke findes swaps i en iteration, behøver vi ikke gentage det yderligere.

I tilfælde af eksemplet, der blev diskuteret tidligere, efter 2. iteration, får vi:

1 2 3 4 5 6

I den tredje iteration behøver vi ikke bytte noget par tilstødende elementer. Så vi kan springe alle resterende iterationer over.

I tilfælde af et sorteret array er det ikke nødvendigt at bytte i selve den første iteration - hvilket betyder, at vi kan stoppe udførelsen. Dette er det bedste tilfælde og algoritmens tidskompleksitet er O (n).

Lad os nu implementere den optimerede løsning.

offentlig ugyldighed optimeretBubbleSort (Heltal [] arr) {int i = 0, n = arr.længde; boolsk swapNeeded = sand; 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 = sandt; }} hvis (! swapNeeded) {pause; } i ++; }}

Lad os kontrollere output for den optimerede algoritme:

@Test offentlig ugyldighed givenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray () {Integer [] array = {2, 1, 4, 6, 3, 5}; Heltal [] sortedArray = {1, 2, 3, 4, 5, 6}; BubbleSort bubbleSort = ny BubbleSort (); bubbleSort.optimizedBubbleSort (matrix); assertArrayEquals (array, sortedArray); }

5. Konklusion

I denne vejledning så vi, hvordan Bubble Sort fungerer, og det implementeres i Java. Vi så også, hvordan det kan optimeres. For at opsummere er det en på stedet stabil algoritme med tidskompleksitet:

• Værste og gennemsnitlige tilfælde: O (n * n), når arrayet er i omvendt rækkefølge
• Bedste tilfælde: O (n), når arrayet allerede er sorteret

Algoritmen er populær inden for computergrafik på grund af dens evne til at opdage nogle små fejl ved sortering. For eksempel i et næsten sorteret array skal kun to elementer byttes for at få et helt sorteret array. Boblesortering kan rette sådanne fejl (dvs. sortere dette array) i lineær tid.

Som altid kan koden til implementering af denne algoritme findes på GitHub.