Sortuj bąbelki Java

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ę.

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. 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.

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]

Jak wydajne jest sortowanie bąbelkowe?

Sortowanie bąbelkowe jest jednym z najłatwiejszych do wdrożenia algorytmów, ale nie jest wydajne. Wymaga pary zagnieżdżonych pętli. Nawet w zoptymalizowanej wersji algorytmu w najgorszym przypadku (każdy element zbioru danych jest w odwrotnej kolejności do pożądanego) zewnętrzna pętla wykonuje jedną iterację dla każdego z n elementów zbioru danych . Wewnętrzna pętla wykonuje iterację n razy za pierwszym razem, ( n-1 ) za drugim i tak dalej. Stąd, aby wszystkie n elementy zostały posortowane, pętle muszą zostać wykonane n*(n-1)/2 razy. Wywołuje O(n ² )złożoności czasowej i oznacza, że ​​algorytm wykonuje około 500 000 porównań dla 1000 elementów tablicy. Jednak algorytm sortowania bąbelkowego jest dość skuteczny w wykorzystaniu pamięci (złożoność pamięci to O(n) ) i jest naprawdę dobry dla prawie posortowanych małych zbiorów danych.