Jak wiadomo, czas sortowania zależny jest od danych. Dane do posortowania składały się z liczb naturalnych. Każdy z algorytmów został sprawdzony pod 6-ma rożnymi tablicami danych. Pierwszy typ danych składał się z liczb losowych (random). Dla każdego algorytmu były te same dane. Drugi typ składał się z tablicy, w której pierwsza liczba była maksymalną liczbą, a pozostałe elementy były już posortowane w sposób rosnący (increasing). Następnym typem danych był modyfikacją poprzedniej tablicy poprzez wprowadzenie powtórzeń wartości tej tablicy (increasing-repeated). Ilość powtórzeń wynosiła wartość pierwiastka z ilości elementów w tablicy (jeżeli elementów w tablicy było 10 000 to ilość powtórzeń jednego elementu wynosiła 100). Skoro już była tablica "prawie" posortowana w sposób rosnąco to następnym typem danych była tablica posortowana z sposób malejąco, ale pierwszy element wynosił 0 (decreasing). Analogicznie, do następnego typu danych wprowadzono modyfikację poprzez powtarzanie tych samych elementów (decreasing-repeated). Ostatnim typem danych była tablica składająca się z jedynki i samych zer (onezero). Algorytm o nazwie BuildInNet to standardowy algorytm sortowania listy przygotowany przez MS i jest on zaimplementowany jako agorytm Quicksort.
Poniżej jest przedstawiony wykres w skali logarytmicznej z czasem działania algorytmów dla losowo wygenerowanych danych. Oś odcięta stanowi grupę ilości danych ( odpowiednio 10, 100, 1 000, 10 000 i 100 000 elementów w tablicy), a oś rzędnych przedstawia czas działania algorytmu w milisekundach.
A poniżej są tablice z wynikami sortowania. Wartości czasu sortowania są przedstawione w milisekundach.
Jak widać w poniższej tablicy, wprowadzenie powtarzalnych elementów nie zmienia znacząco czasu działania algorytmów.
Jak widać na powyższych tabelkach, 3 algorytmy działają stosunkowo długo oraz nie mają znaczenia czy dane są posortowane w postaci rosnąco czy malejąco. Te algorytmy to: Odd-Even sort, Selection i Stooge sort. Takie algorytmy jak Quicksort, BuildInNet Counting i ShellSort działają równie szybko dla tablicy prawie posortowanej rosnąco jak i malejąco. Dla tablicy z jedną modyfikacją (onezero) oraz z prawie posortowaną tablicą (increasing), selection sort ma gorszy wynik czasu sortowania niż dla algorytmów bubble sort, comb sort czy sortowanie gnoma, mimo że dla innych danych te algorytmy są szybsze.
Algorytm Stooge sort ma najgorszą złożoność obliczeniową. Dla 10 000 elementów czas działania był o 3 rzędy wielkości większy niż dla słabych algorytmów. Sortowanie zostało zatrzymane dla 100 0000 elementów,gdyż czas sortowania wynosił 489 557 429 ms, a to jest ... strasznie długo. W przybliżeniu stanowi to 5 dni i 15 godzin. Gdy sprawdzałem dane, to okazało się, że dane zostały posortowane do 48 147 elementu. Dla tablicy liczącej do 1000 elementu nie ma znaczenia jaki algorytm zastosujesz z sortowaniu (za wyjątkiem nieszczęsnego stoogesorta).
Do dalszych testów wybrałem 6 najlepszych algorytmów. W śród nich są: Counting, Quicksort, Shellsort, Mergesort, Insertsort i dla porównania BuildInNet (algorytm Quicksort w BCL). Poniższy wykres przedstawia czas sortowania w skali logarytmicznej dla poszczególnej ilość danych (1000, 10 000, 100 000 i 1 000 000 elementów).
Z tego można wybrać 4 najlepsze algorytmy. Poniżej wykres dla tablicy z danymi losowymi (random) w skali liniowej (OY przedstawia czas działania algorytmu w milisekundach).
W trakcie przerwy w pisaniu algorytmów miałem możliwość zainteresowania się tańcami ludowymi:)
Bardzo mi się podobają filmiki przedstawiające algorytmy sortowania za pomocą tańców. Jestem bardzo ciekaw jak można by było przedstawić jakiś algorytm za pomocą ruedy z salsy :) Może problem ucztujących filozofów.
Brak komentarzy:
Prześlij komentarz