Po krótkiej analizie kodu stwierdzam że Twój bubble sort został zaimplementowany bardzo naiwnie. Liczba swapów jest proporcjonalna do O(n^2) gdzie w "poprawnej" wersji jest zależna od O(n). Inaczej mówiąc: robisz swapa zawsze gdy dwa elementy są w złej kolejności a nie tylko wtedy gdy przejrzysz całą nieposortowaną tablice.
@Klopsztanga: Krzysztofie B. odważny jesteś wrzucając swój kod razem z danymi osobowymi. Kilka uwag co do kodu: pamiętaj o delete, czas sortowania 80k elementów zajęło sortowaniu bąbelkowemu 45 sekund? Kod kompilowany był pod release z optymalizacją na prędkość wykonania? Ja na uczelnie pisałem podobny program, tylko u nas nie chcieli pomiaru czasu tylko liczbę atomowych / bazowych operacji (np swap) który każdy algorytm wykonywał. Dodatkowo trzeba było wskazać zapotrzebowanie na pamięć
Świetna wizualizacja. Chociaż z quicksortem to warto pamiętać że w wyjątkowo pesymistycznym przypadku działa on tak samo jak bubble sort, czyli w czasie O(n^2) :> jednak rzadkość tego przypadku (chociaż to zależy od danych) oraz fakt że quicksort się bardzo prosto implementuje przeważają szalę. Ale i tak kopce FTW :>
@Marmite: PS - nie polecam wybierać sortowania bąbelkowego/przez wstawianie i wpisywać w to pole obok listy algorytmów sortowania wartości "1" - może Wam na troche zmulić kompa, patrząc po tym na ile go zmulił quicksort.
Komentarze (19)
najlepsze
http://www.speedyshare.com/nc5yr/sorting-benchmark.zip
Po krótkiej analizie kodu stwierdzam że Twój bubble sort został zaimplementowany bardzo naiwnie. Liczba swapów jest proporcjonalna do O(n^2) gdzie w "poprawnej" wersji jest zależna od O(n). Inaczej mówiąc: robisz swapa zawsze gdy dwa elementy są w złej kolejności a nie tylko wtedy gdy przejrzysz całą nieposortowaną tablice.
autor chyba nie wytrzymał presji