Benchmark algorytmów sortowania w języku Java.

1. Cel zajęć i wstęp

Celem zadania jest:

1. Zastosowanie polimorfizmu i interfejsów w języku Java do budowy elastycznego modułu testującego.
2. Praktyczne zmierzenie czasu wykonania algorytmów sortowania o różnej złożoności obliczeniowej.
3. Samodzielna implementacja algorytmu Quick Sort na podstawie formalnego pseudokodu.
4. Modelowanie przepływu sterowania za pomocą schematu blokowego.
5. Formułowanie wniosków w oparciu o teorię złożoności obliczeniowej $ O $.

Pomiar czasu w języku Java:

W inżynierii oprogramowania do precyzyjnego profilowania kodu stosuje się licznik nanosekundowy procesora:

long start = System.nanoTime();
// ... mierzony algorytm ...
long stop = System.nanoTime();

long durationInNano = stop - start;
double durationInMillis = durationInNano / 1_000_000.0;

Ważna uwaga metodologiczna:

Każdy algorytm musi sortować tę samą tablicę nieposortowaną. Przekazanie do kolejnego sortera tablicy już posortowanej fałszuje pomiary. Dlatego przed wywołaniem metody sort() należy utworzyć kopię danych za pomocą metody array.clone().

2. Materiały startowe

Jako bazę projektową otrzymujesz gotowy interfejs ISorter, klasę generatora danych ArrayGenerator oraz szkielet klasy pomiarowej Benchmark.

Interfejs ISorter.java

package ...;

public interface ISorter {
    void sort(int[] array);
    String getName();
}

Klasa ArrayGenerator.java

package ...;

import java.util.Random;

public class ArrayGenerator {
    /**
     * Generuje tablicę o podanym rozmiarze z losowymi wartościami z przedziału [min, max].
     */
    public static int[] generateRandom(int size, int min, int max) {
        Random random = new Random();
        int[] array = new int[size];
        int bound = (max - min) + 1;

        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(bound) + min;
        }

        return array;
    }
}

Szkielet klasy Benchmark.java

package ...;

public class Benchmark {

    public static void main(String[] args) {
        int[] testSizes = { 10_000, 50_000 };

        // Tablica polimorficzna badanych algorytmów
        ISorter[] sorters = {
            new BubbleSorter(),
            new InsertionSorter(),
            new SelectionSorter()
            // Po wykonaniu Zadania 3 odkomentuj:
            // new QuickSorter()
        };

        for (int size : testSizes) {
            System.out.println("============================================================");
            System.out.printf("ROZPOCZĘCIE TESTÓW DLA ROZMIARU: %d ELEMENTÓW%n", size);
            System.out.println("============================================================");

            int[] baseArray = ArrayGenerator.generateRandom(size, 0, 100_000);

            for (ISorter sorter : sorters) {
                // Klonujemy tablicę, aby każdy algorytm sortował identyczny zestaw danych
                int[] arrayCopy = baseArray.clone();

                long startTime = System.nanoTime();
                sorter.sort(arrayCopy);
                long endTime = System.nanoTime();

                double durationMs = (endTime - startTime) / 1_000_000.0;
                boolean isSorted = isSortedAscending(arrayCopy);

                System.out.printf("Algorytm: %-18s | Czas: %8.2f ms | Posortowano poprawnie: %b%n",
                        sorter.getName(), durationMs, isSorted);
            }
            System.out.println();
        }
    }

    private static boolean isSortedAscending(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] > array[i + 1]) {
                return false;
            }
        }
        return true;
    }
}

3. Treść zadań do wykonania (łącznie: 100 pkt)

Zadanie 1: Implementacja klas bazowych sorterów (35 pkt)

Utwórz trzy klasy implementujące interfejs ISorter:

1. BubbleSorter - sortowanie bąbelkowe.
2. InsertionSorter - sortowanie przez wstawianie.
3. SelectionSorter - sortowanie przez wybieranie.

Każda klasa musi:

• Implementować metodę void sort(int[] array) sortującą przekazaną tablicę rosnąco.
• Implementować metodę String getName() zwracającą czytelną nazwę algorytmu (np. "Bubble Sort").
• Być napisana zgodnie ze standardem Java Code Conventions (właściwe formatowanie, hermetyzacja, czytelne nazwy zmiennych).

(Szczegółowe pseudokody i listy kroków tych algorytmów znajdziesz w Załączniku A do niniejszej karty).

Zadanie 2: Konfiguracja i uruchomienie modułu Benchmark (10 pkt)

1. Zintegruj zaimplementowane klasy BubbleSorter, InsertionSorter i SelectionSorter ze szkieletem Benchmark.java.
2. Uruchom program dla obu rozmiarów prób badawczych:
   
   • N₁=10 000 elementów
   • N₂=50 000 elementów
3. Upewnij się, że każdy algorytm uzyskuje status: Posortowano poprawnie: true.

Zadanie 3: Tłumacz z pseudokodu - Implementacja QuickSorter (30 pkt)

Na podstawie poniższego formalnego pseudokodu algorytmu Quick Sort (wariant Lomuto) utwórz klasę QuickSorter implementującą interfejs ISorter.

Pseudokod algorytmu Quick Sort:

ALGORYTM QuickSort(A, low, high):
    JEŻELI low < high TO:
        pivotIndex = Partition(A, low, high)
        QuickSort(A, low, pivotIndex - 1)
        QuickSort(A, pivotIndex + 1, high)

ALGORYTM Partition(A, low, high):
    pivot = A[high]                 // element osiowy (ostatni element)
    i = low - 1                     // wskaźnik elementów mniejszych od pivota
    
    DLA j = low DO high - 1 WYKONAJ:
        JEŻELI A[j] <= pivot TO:
            i = i + 1
            Zamień(A[i], A[j])
            
    Zamień(A[i + 1], A[high])        // umieszczenie pivota na właściwym miejscu
    ZWRÓĆ i + 1                     // zwrócenie pozycji podziału

Wymagania implementacyjne:

1. Metoda interfejsu public void sort(int[] array) wywołuje prywatną metodę rekurencyjną:
   

   quickSort(array, 0, array.length - 1);

    
2. Metody quickSort oraz partition powinny mieć modyfikator dostępu private.
3. Dołącz new QuickSorter() do tablicy sorters w klasie Benchmark i uruchom pełne testy porównawcze.

Zadanie 4: Schemat blokowy logiki pomiarowej (15 pkt)

Za pomocą programu graficznego (np. draw.io) sporządź znormalizowany schemat blokowy prezentujący przebieg pętli pomiarowej programu Benchmark dla pojedynczego rozmiaru tablicy.

Schemat musi zawierać:

• [ ] Blok startu i zakończenia procedury.
• [ ] Wygenerowanie losowej tablicy bazowej.
• [ ] Pętlę iterującą po tablicy obiektów ISorter.
• [ ] Klonowanie tablicy przed pomiarem (array.clone()).
• [ ] Pobranie czasu początkowego i końcowego wokół metody sort().
• [ ] Blok decyzyjny (warunkowy) sprawdzający warunek zakończenia pętli.
• [ ] Wypisanie wyniku na ekran.

Zadanie 5: Wnioski i złożoność obliczeniowa (10 pkt)

Na końcu pliku Benchmark.java (w komentarzu wieloliniowym /* ... */) wpisz uzyskane przez Ciebie wyniki pomiarów dla N=50 000 elementów oraz sformułuj odpowiedzi na poniższe pytania:

1. Porównanie empiryczne: Który algorytm okazał się najszybszy dla 50 000 elementów i jaka była różnica rzędu wielkości w stosunku do najwolniejszego?

ZAŁĄCZNIK A: Specyfikacja algorytmów bazowych

1. Bubble Sort (Sortowanie bąbelkowe)

• Idea: Cykliczne porównywanie sąsiadujących elementów i zamiana ich miejscami, gdy lewy jest większy od prawego. Po każdej iteracji największy element wędruje na koniec tablicy.
• Pseudokod:
  

  ALGORYTM BubbleSort(A):
      n = Długość(A)
      DLA i = 0 DO n - 2 WYKONAJ:
          DLA j = 0 DO n - i - 2 WYKONAJ:
              JEŻELI A[j] > A[j + 1] TO:
                  temp = A[j]
                  A[j] = A[j + 1]
                  A[j + 1] = temp
  

2. Selection Sort (Sortowanie przez wybieranie)

• Idea: Wyszukiwanie elementu minimalnego w nieposortowanej części tablicy i zamiana go miejscami z elementem na początku tej części.
• Pseudokod:
  

  ALGORYTM SelectionSort(A):
      n = Długość(A)
      DLA i = 0 DO n - 2 WYKONAJ:
          minIndex = i
          DLA j = i + 1 DO n - 1 WYKONAJ:
              JEŻELI A[j] < A[minIndex] TO:
                  minIndex = j
          JEŻELI minIndex != i TO:
              temp = A[i]
              A[i] = A[minIndex]
              A[minIndex] = temp
  

3. Insertion Sort (Sortowanie przez wstawianie)

• Idea: Pobranie kolejnego elementu jako klucza i przesuwanie w prawo wszystkich elementów większych od niego, a następnie wstawienie klucza w zwolnione miejsce (analogia do układania kart w dłoni).
• Pseudokod:
  

  ALGORYTM InsertionSort(A):
      n = Długość(A)
      DLA i = 1 DO n - 1 WYKONAJ:
          klucz = A[i]
          j = i - 1
          DOPÓKI j >= 0 ORAZ A[j] > klucz WYKONAJ:
              A[j + 1] = A[j]
              j = j - 1
          A[j + 1] = klucz