Sortowanie bąbelkowe

Algorytmy: sortowanie i wyszukiwanie - Podstawy Javy (Java)

Zasada działania sortowania bąbelkowego: Algorytm porównuje sąsiednie elementy Jeśli element po lewej jest większy, następuje zamiana W każdym przejściu największy element "wypływa" na koniec tablicy Proces powtarza się dla coraz krótszej części tablicy Złożoność algorytmu: Czasowa: O(n²) - gdzie n to liczba elementów Pamięciowa: O(1) - wymaga tylko jednej zmiennej pomocniczej Przypadek najgorszy: O(n²) - tablica posortowana odwrotnie Przypadek najlepszy: O(n) - tablica już posortowana (w wersji zoptymalizowanej) Optymalizacje: Dodanie flagi swapped - przerwanie gdy nie było zamian Zmniejszanie zakresu porównań w każdej iteracji Śledzenie liczby porównań i zamian Zalety: Prosty w implementacji Nie wymaga dodatkowej pamięci Stabilny (zachowuje kolejność równych elementów) Wady: Niska wydajność dla dużych zbiorów danych Zawsze wykonuje porównania, nawet gdy tablica jest posortowana

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    // Przykładowa tablica do sortowania
    int[] array = {64, 4, 9, 12, 22, 11, 90, 55, 63};
    
    System.out.println("Tablica przed sortowaniem:");
    System.out.println(Arrays.toString(array));

    // Podstawowa implementacja sortowania bąbelkowego
    bubbleSort(array);

    System.out.println("\nTablica po sortowaniu:");
    System.out.println(Arrays.toString(array));

    // Demonstracja zoptymalizowanego sortowania bąbelkowego
    int[] array2 = {64, 4, 9, 12, 22, 11, 90, 55, 63};
    System.out.println("\nDrugi przykład (zoptymalizowany):");
    System.out.println("Przed sortowaniem:");
    System.out.println(Arrays.toString(array2));
    
    optimizedBubbleSort(array2);

    System.out.println("Po sortowaniu:");
    System.out.println(Arrays.toString(array2));
  }

  // Podstawowa implementacja sortowania bąbelkowego
  public static void bubbleSort(int[] arr) {
    int n = arr.length;
    int iterations = 0;
    int swaps = 0;

    // Zewnętrzna pętla - liczba przejść
    for (int i = 0; i < n-1; i++) {
      System.out.println("\nIteracja " + (i + 1) + ":");
      
      // Wewnętrzna pętla - porównywanie par elementów
      for (int j = 0; j < n-1-i; j++) {
        iterations++;
        // Porównanie sąsiednich elementów
        if (arr[j] > arr[j+1]) {
          // Zamiana miejscami
          int temp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = temp;
          swaps++;
        }
        // Wyświetlenie stanu tablicy po każdym porównaniu
        System.out.println("Porównanie " + (j + 1) + ": " + Arrays.toString(arr));
      }
    }
    System.out.println("\nLiczba porównań: " + iterations);
    System.out.println("Liczba zamian: " + swaps);
  }

  // Zoptymalizowana wersja sortowania bąbelkowego
  public static void optimizedBubbleSort(int[] arr) {
    int n = arr.length;
    int iterations = 0;
    int swaps = 0;
    boolean swapped;

    for (int i = 0; i < n-1; i++) {
      swapped = false;
      
      for (int j = 0; j < n-1-i; j++) {
        iterations++;
        if (arr[j] > arr[j+1]) {
          // Zamiana miejscami
          int temp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = temp;
          swapped = true;
          swaps++;
        }
      }

      // Jeśli w danym przejściu nie było żadnej zamiany,
      // tablica jest już posortowana
      if (!swapped) {
        break;
      }
    }
    
    System.out.println("Liczba porównań (zoptymalizowana wersja): " + iterations);
    System.out.println("Liczba zamian (zoptymalizowana wersja): " + swaps);
  }
}

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Podstawy Javy · Zaloguj się, aby zapisać postęp na koncie.