Sortowanie to jeden z fundamentalnych problemow informatyki. Jak ulozyc n elementow w porzadku rosnacym — i dlaczego jedne metody sa tysiace razy szybsze od innych? Zbadaj to interaktywnie.
Porownuje sasiednie elementy i zamienia jesli sa w zlej kolejnosci
Bubble Sort z malejacymi przyrostami Papernova-Stasevicha
Dziel i zwyciezaj — dzieli na polowy i scala posortowane czesci
Buduje max-heap i wielokrotnie wyciaga element maksymalny
Losowy pivot, partycja na mniejsze/wieksze, rekurencja
Mediana trzech jako pivot, iteracyjny z jawnym stosem
Sortowanie to proces ukladania elementow zbioru w okreslonym porzadku — najczesciej rosnacym lub malejacym. Jest to jedna z najczesciej wykonywanych operacji w informatyce: wyszukiwanie binarne, bazy danych, systemy plikow, algorytmy grafowe — wszystkie zaleza od posortowanych danych.
Rozne algorytmy sortowania maja rozna zlozonosc obliczeniowa. Proste metody jak Bubble Sort dzialaja w czasie O(n²) — dla 10 000 elementow to 100 milionow operacji. Zaawansowane metody jak Merge Sort czy Quick Sort dzialaja w O(n log n) — to tylko 130 000 operacji. Roznica jest tysiackrotna.
W tym projekcie implementujemy 6 algorytmow, testujemy je na 5 roznych ksztaltach danych wejsciowych (losowe, rosnace, malejace, A-ksztaltne, V-ksztaltne) i analizujemy czy rzeczywista liczba operacji zgadza sie z teoretyczna zlozonoscia.
Animowana krok po kroku z podswietleniem operacji, panelem tablicy i opisem kazdego kroku dopasowanym do algorytmu.
Pomiary czasu, porownan i zamian na 10 rozmiarach tablic w 5 ksztaltach danych. Wykresy interaktywne z Recharts.
Pelny raport z tabelami, wykresami, analiza zlozonosci i eksportem do PDF — zgodny z wymaganiami instrukcji.
| Ksztalt | Przyklad | Zastosowanie w analizie |
|---|---|---|
| Rosnace | 1, 2, 3, 4, 5, 6, 7, 8 | Best case: Bubble Sort O(n) |
| Malejace | 8, 7, 6, 5, 4, 3, 2, 1 | Worst case: Bubble Sort O(n²) |
| A-ksztaltne | 1, 3, 5, 7, 8, 6, 4, 2 | Przypadek mieszany |
| V-ksztaltne | 8, 6, 4, 2, 1, 3, 5, 7 | Przypadek mieszany |
| Losowe | 4, 7, 2, 9, 1, 5, 8, 3 | Average case |
Wartosci w kazdym ciagu naleza do przedzialu <1, 10×n> — zgodnie z instrukcja. Dla kazdego rozmiaru n generowane jest 10 ciagow, wyniki usredniane.