Uczę się o Quicksort i chcę zilustrować różne tablice, na których Quicksort miałoby trudności. Quicksort, o którym myślę, nie ma początkowego losowego tasowania, dzieli 2 partycje i nie oblicza mediany.
Do tej pory wymyśliłem trzy przykłady:
[1,2,3,4,5,6,7,8,9,10] - when the array is sorted
[10,9,8,7,6,5,4,3,2,1] - when the array is reversed
[1,1,1,1,1,1,1,1,1,1] - when the array is the same values
[1,1,1,2,2,2,3,3,3,3] - when there are few and unique keys
Na przykład nie jestem zbyt pewien tego:
[1,3,5,7,9,10,8,6,4,2]
Co zatem sprawia, że tablica, z którą ma problemy szybkie sortowanie, w porównaniu do tablicy, w której jest (prawie) idealna?
algorithms
sorting
mrQWERTY
źródło
źródło
[2,1,2,1,2,1,2,1]i że jest to całość odpowiedź). Ideą pytania byłoby, najlepiej, aby inni ludzie mogli przyjść i dowiedzieć się więcej o tym, dlaczego (która ma odpowiedź), a nie przykłady (których jest niezliczona liczba).Odpowiedzi:
Algorytm każdego rodzaju ma najgorszy przypadek, aw wielu przypadkach najgorszy przypadek jest naprawdę zły, dlatego warto go przetestować. Problem polega na tym, że nie ma jednego najgorszego przypadku tylko dlatego, że znasz podstawowy algorytm.
Najczęstsze najgorsze przypadki to: już posortowane; posortowane w odwrotnej kolejności; prawie posortowane, jeden element niesprawny; wszystkie wartości są takie same; wszystko to samo, z wyjątkiem pierwszego (lub ostatniego), jest wyższe (lub niższe). Kiedyś mieliśmy rodzaj, w którym najgorszym przypadkiem był szczególny wzór piłokształtny, który był bardzo trudny do przewidzenia, ale dość powszechny w praktyce.
Najgorszym przypadkiem dla Quicksort jest to, że zawsze wybiera najgorszy możliwy punkt obrotu, dzięki czemu jedna z partycji ma tylko jeden element. Jeśli element przestawny jest pierwszym elementem (zły wybór), wówczas dane już posortowane lub odwrotnie posortowane są najgorszym przypadkiem. W przypadku mediany trzech danych przestawnych, które są takie same lub tylko pierwszy lub ostatni jest inny, robi to.
W przypadku szybkiego sortowania średnia złożoność to nlogn, a najgorszy przypadek to n ^ 2. Powodem, dla którego warto wywołać najgorsze zachowanie, jest to, że dzieje się tak również w przypadku największej głębokości rekurencji. W przypadku naiwnej implementacji głębokość rekurencji może wynosić n, co może spowodować przepełnienie stosu. Testowanie innych ekstremalnych sytuacji (w tym najlepszego przypadku) może być opłacalne z podobnych powodów.
źródło
O(NlogN)wydajnością lub lepszą) najgorsze i średnie przypadki mają tę samą złożoność. To sugeruje, że zwykle NIE warto testować w najgorszym przypadku. (Biorąc pod uwagę, że test jest prawdopodobnieO(N)... lub gorszy.)Algorytm ucieka od większości złych przypadków przy użyciu losowej osi przestawnej, z wyłączeniem elementów ciągłych równej liczbie przestawnej z podziału i wyszukiwania asymetrycznego. Przeszukuje do przodu element większy lub równy osi przestawnej i przeszukuje do tyłu element mniejszy niż przestawna.
Dziękuję MichaelT, wyszukiwanie asymetryczne ma na celu rozwiązanie [2,1,2,1,2,1,1,1].
Poniższy wynik jest generowany przez moją funkcję qsort_random (). N = 100 000
Większość przypadków jest szybsza niż losowy wzór. Wzór doliny jest złym przypadkiem dla większości selekcji przestawnych.
Funkcja qsort_log2 () ucieka od złych przypadków, wybierając element przestawny w elementach log2 (N).
qsort (3) używa biblioteki GNU, która jest sortowaniem indeksów przez scalanie.
qsort_trad () wybierz oś przestawną w pierwszym, środkowym i ostatnim elemencie.
Funkcje qsort_random () i qsort_log2 () nie używają zamiany.
Programy i skrypty źródłowe C są publikowane w github .
źródło