Jeśli kiedykolwiek słyszałeś o metodach sortowania w programowaniu, najprawdopodobniej był to algorytm sortowania bąbelkowego. To jest słynny. Sortowanie bąbelkowe zna każdy programista (a przynajmniej słyszał o nim podczas nauki) nie dlatego, że jest to najlepszy algorytm sortowania na świecie, ale najłatwiejszy. Ten algorytm jest zwykle używany do celów edukacyjnych lub możesz go otrzymać jako zadanie podczas rozmowy kwalifikacyjnej Java Junior. Algorytm Java Bubble Sort jest bardzo łatwy do zrozumienia, jednak nie jest wydajny. W każdym razie, zastanówmy się.
Krok 1: przeglądamy tablicę. Algorytm rozpoczyna się od dwóch pierwszych elementów (z indeksami 0 i 1), 8 i 7, i sprawdza, czy są one w odpowiedniej kolejności. Oczywiście 8 > 7, więc zamieniamy je miejscami. Następnie patrzymy na drugi i trzeci element (indeksy 1 i 2), teraz są to 8 i 1. Z tych samych powodów zamieniamy je miejscami. Po raz trzeci porównujemy 8 z 2 i co najmniej 8 z 5. W sumie dokonaliśmy czterech zamian: (8, 7), (8, 1), (8, 2) i (8, 5). Wartość 8, największa w tej tablicy, pojawiła się na końcu listy na właściwej pozycji.
Wynikiem pierwszego kroku działania algorytmu sortowania bąbelkowego jest następna tablica:
Krok 2. Zrób to samo z (7,1), (7,2) i (7,5). 7 jest teraz na przedostatniej pozycji i nie musimy porównywać go z „ogonem” listy, jest już posortowany.
Wynikiem drugiego kroku działania algorytmu sortowania bąbelkowego jest następna tablica:
Jak widać, ta tablica jest już posortowana. W każdym razie algorytm sortowania bąbelkowego powinien zacząć działać przynajmniej jeszcze raz. Krok 3. Jeszcze raz przechodzimy przez tablicę. Nie ma tu nic do zamiany, więc jeśli używamy „ulepszonego” algorytmu Bubble Sort (ze sprawdzeniem, czy w poprzednim kroku dokonano przynajmniej jednej zamiany) ten krok jest ostatnim.
Co to jest sortowanie
Przede wszystkim musisz zrozumieć, czym ogólnie jest sortowanie i co możemy sortować w programach Java. Jeśli możemy porównać dwa lub więcej elementów lub obiektów według dowolnego z ich atrybutów, oznacza to, że można je posortować według tego atrybutu. Na przykład liczby w porządku rosnącym lub malejącym albo słowa alfabetycznie. Dlatego elementy muszą być ze sobą porównywalne. Nawiasem mówiąc, elementy czego? W Javie możemy porównywać elementy Collections. Na przykład możemy sortować Array lub ArrayList liczb całkowitych, łańcuchów i tak dalej.Jak działa sortowanie bąbelkowe
Powiedzmy, że musimy posortować tablicę liczb całkowitych w porządku rosnącym, czyli od najmniejszej do największej liczby. Najpierw idziemy wzdłuż całej tablicy i porównujemy co 2 sąsiednie elementy. Jeśli są w złej kolejności (lewy sąsiad jest większy niż prawy), zamieniamy je miejscami. Przy pierwszym przejściu na końcu pojawi się największy element (jeśli sortujemy rosnąco). Można powiedzieć, że największy element „wyskakuje”. To jest powód nazwy algorytmu sortowania bąbelkowego. Powtarzamy pierwszy krok od pierwszego do przedostatniego elementu. Mamy drugi co do wielkości element na przedostatnim miejscu. I tak dalej. Algorytm możemy nieco ulepszyć, sprawdzając, czy w poprzednim kroku dokonano przynajmniej jednej wymiany. Jeśli tak nie jest, przestajemy biegać po tablicy.Przykład sortowania bąbelkowego
Posortujmy tablicę liczb całkowitych, tę, którą możesz zobaczyć na poniższym obrazku.




Sortowanie bąbelkowe kodu Java
Realizacja Java sortowania bąbelkowego
Stwórzmy dwie metody sortowania bąbelkowego. Pierwszy, bubbleSort(int[] myArray) jest płaski. Przechodzi przez tablicę za każdym razem. Drugi, OptimizedBubbleSort(int myArray[]) jest optymalizowany poprzez zatrzymanie algorytmu, jeśli wewnętrzna pętla nie spowodowała zamiany. Licznik pokazuje, ile kroków wykonałeś podczas sortowania. Tutaj mamy realizację Bubble sort Java:
import java.util.Arrays;
public class BubbleSortExample {
// Plane Bubble sort example
public static int[] bubbleSort(int[] myArray) {
int temp = 0; // temporary element for swapping
int counter = 0; // element to count quantity of steps
for (int i = 0; i < myArray.length; i++) {
counter = i + 1;
for (int j = 1; j < (myArray.length - i); j++) {
if (myArray[j - 1] > myArray[j]) {
// swap array’s elements using temporary element
temp = myArray[j - 1];
myArray[j - 1] = myArray[j];
myArray[j] = temp;
}
}
}
System.out.println("Steps quantity, non optimized = " + counter);
return myArray;
}
// An optimized version of Java Bubble Sorting
static int[] optimizedBubbleSort(int myArray[]) {
int temp;
boolean swapped;
int counter = 0; // element to count quantity of steps
for (int i = 0; i < myArray.length - 1; i++) {
counter = i + 1;
swapped = false;
for (int j = 0; j < myArray.length - i - 1; j++) {
// counter++;
if (myArray[j] > myArray[j + 1]) {
// swap arr[j] and arr[j+1]
temp = myArray[j];
myArray[j] = myArray[j + 1];
myArray[j + 1] = temp;
swapped = true;
}
} // counter = i;
// If there weren't elements to swap in inner loop, then break
if (swapped == false) {
break;
}
}
System.out.println("steps quantity, optimized = " + counter);
return myArray;
}
public static void main(String[] args) {
int arr[] = {8, 7, 1, 2, 5};
int arr1[] = {8, 7, 1, 2, 5};
System.out.println("Array arr Before Bubble Sort");
// we use java.util.Arrays toString method to print the array
System.out.println(Arrays.toString(arr));
System.out.println("Array arr After Bubble Sort");
System.out.println(Arrays.toString(bubbleSort(arr)));
System.out.println("Array arr1 Before Bubble Sort");
System.out.println(Arrays.toString(arr1));
System.out.println("Array arr1 After Optimized Bubble Sort");
System.out.println(Arrays.toString(optimizedBubbleSort(arr1)));
}
}
Wynik działania algorytmu Bubble sort Java:
Array arr Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr After Bubble Sort
Steps quantity, non optimized = 5
[1, 2, 5, 7, 8]
Array arr1 Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr1 After Optimized Bubble Sort
steps quantity, optimized = 3
[1, 2, 5, 7, 8]
GO TO FULL VERSION