Bubble Sort
Implementierung
package net.bitelligence.training.exercise.sorting.bubble_sort;
public class BubbleSort {
/**
* This method sorts an array of integers using the bubble sort algorithm.
* The input is an array of integers to be sorted, and the output is the sorted array.
* The bubble sort algorithm repeatedly steps through the list to be sorted,
* compares each pair of adjacent items and swaps them if they are in the wrong order.
* The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.
*
* @param numbers The array of integers to be sorted
* @return The sorted array of integers
*/
public int[] sort(int[] numbers) {
// ...
return numbers;
}
}package net.bitelligence.training.exercise.sorting.bubble_sort;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
class BubbleSortTest {
@Test
public void should_correctly_sort_mixed_arrays() {
final int[] unsorted1 = {};
final int[] unsorted2 = { 1 };
final int[] unsorted3 = { 2, 1 };
final int[] unsorted4 = { 2, 1, 3 };
final int[] unsorted5 = { 2, 4, 1, 3 };
final int[] unsorted6 = { 2, 1, 2, 3, 9 };
final int[] unsorted7 = { 1, 2, 3, 4, 5, 6 };
final int[] expected1 = {};
final int[] expected2 = { 1 };
final int[] expected3 = { 1, 2 };
final int[] expected4 = { 1, 2, 3 };
final int[] expected5 = { 1, 2, 3, 4 };
final int[] expected6 = { 1, 2, 2, 3, 9 };
final int[] expected7 = { 1, 2, 3, 4, 5, 6 };
assertArrayEquals(expected1, new BubbleSort().sort(unsorted1));
assertArrayEquals(expected2, new BubbleSort().sort(unsorted2));
assertArrayEquals(expected3, new BubbleSort().sort(unsorted3));
assertArrayEquals(expected4, new BubbleSort().sort(unsorted4));
assertArrayEquals(expected5, new BubbleSort().sort(unsorted5));
assertArrayEquals(expected6, new BubbleSort().sort(unsorted6));
assertArrayEquals(expected7, new BubbleSort().sort(unsorted7));
}
}package net.bitelligence.training.exercise.sorting.bubble_sort;
public class BubbleSort {
/**
* This method sorts an array of integers using the bubble sort algorithm.
* The input is an array of integers to be sorted, and the output is the sorted array.
* The bubble sort algorithm repeatedly steps through the list to be sorted,
* compares each pair of adjacent items and swaps them if they are in the wrong order.
* The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.
*
* @param numbers The array of integers to be sorted
* @return The sorted array of integers
*/
public int[] sort(int[] numbers) {
boolean swapped = true;
while (swapped) {
swapped = false;
for (int i = 0; i < numbers.length - 1; i++) {
if (numbers[i] > numbers[i + 1]) {
final int temp = numbers[i];
numbers[i] = numbers[i + 1];
numbers[i + 1] = temp;
swapped = true;
}
}
}
return numbers;
}
}package net.bitelligence.training.exercise.sorting.bubble_sort;
public class BubbleSort {
/**
* This method sorts an array of integers using the bubble sort algorithm.
* The input is an array of integers to be sorted, and the output is the sorted array.
* The bubble sort algorithm repeatedly steps through the list to be sorted,
* compares each pair of adjacent items and swaps them if they are in the wrong order.
* The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.
*
* @param numbers The array of integers to be sorted
* @return The sorted array of integers
*/
public int[] sort(int[] numbers) {
// iterate through all the numbers, last iteration can be skipped
for (int i = 0; i < numbers.length - 1; i++) {
// iterate through all numbers who have not been moved to their final position yet
for (int j = 0; j < numbers.length - i - 1; j++) {
// compare left to right, if left is bigger swap both
if (numbers[j] > numbers[j + 1]) {
final int temp = numbers[j];
numbers[j] = numbers[j + 1];
numbers[j + 1] = temp;
}
}
}
return numbers;
}
}Funktionsweise
In der Bubble-Phase wird die Eingabe-Liste von links nach rechts durchlaufen. Dabei wird in jedem Schritt das aktuelle Element mit dem rechten Nachbarn verglichen. Falls die beiden Elemente das Sortierkriterium verletzen, werden sie getauscht. Am Ende der Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe am Ende der Liste.
Die Bubble-Phase wird so lange wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da die restliche zu sortierende Eingabe keine größeren bzw. kleineren Elemente mehr enthält.
Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Blasen im Wasser (daher der Name) immer weiter nach oben, das heißt, an das Ende der Liste. Es werden stets zwei Zahlen miteinander in „Bubbles“ vertauscht. [1]
Hilfestellung
Tipp #1
Verstehen Sie die Grundidee des Algorithmus: Der Bubble Sort funktioniert, indem das Array durchlaufen wird und benachbarte Elemente miteinander verglichen werden. Wenn ein Element größer als sein Nachbar ist, werden die Elemente getauscht. Der Algorithmus wiederholt diesen Prozess, bis das Array sortiert ist.
Tipp #2
Implementieren Sie den Vergleich und den Austausch korrekt: Stellen Sie sicher, dass Sie die benachbarten Elemente richtig miteinander vergleichen und sie korrekt austauschen, falls notwendig.
Optional
Optimieren Sie den Algorithmus: Der Bubble Sort hat eine große Zeitkomplexität von O(n²), da er das Array in jeder Runde durchlaufen muss, um sicherzustellen, dass es sortiert ist.
Es gibt jedoch Möglichkeiten, den Algorithmus zu optimieren, indem zum Beispiel eine Flag zu setzen um zu überprüfen, ob es eine Runde gab, in der keine Austausche vorgenommen wurden, in diesem Fall kann man die Durchläufe abbrechen.