Co stanowi zły przypadek do szybkiego sortowania?

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

Jak wybierany jest element przestawny? Podałeś dwa sposoby, że nie został wybrany, ale nie sposób, w jaki został wybrany.

— Winston Ewert

Podaj Najgorszy przypadek dla QuickSort - kiedy to może wystąpić? na StackOverflow odczyt. Sorting.at uważam również za dobrą wizualizację algorytmów sortowania.

@WinstonEwert Pivot jest wybierany przez pierwszy element.

— mrQWERTY,

@ Renren29 Zmodyfikowałem pytanie nieco, próbując je przenieść, aby skupić się na powodach, dla których quicksort miałby trudności z daną tablicą, zamiast szukać przykładowych tablic (nie sądzę, że ludzie udzielają odpowiedzi [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).

Używasz szybkiego sortowania do kawałków 2 elementów? Ponieważ implementacje w świecie rzeczywistym używają prostszych rodzajów dla małych porcji. Np. Porównaj i zamień jest o wiele prostsze niż Quicksort dla N = 2.

— MSalters

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.

— david.pfx
źródło

Rozumiem, więc odchylenie standardowe od średniej naprawdę determinuje wynik podziału.

— mrQWERTY

„... i prawie w każdym przypadku najgorszy przypadek jest naprawdę zły, dlatego warto go przetestować”. . To jest dyskusyjne. Kiedy patrzę na tę tabelę: en.wikipedia.org/wiki/… dochodzę do wniosku, że dla większości „dobrych” algorytmów sortowania (tj. Ze średnią 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 prawdopodobnie O(N)... lub gorszy.)

— Stephen C

@ Renren29: Mediana 3 osi obrotu będzie pierwsza lub ostatnia tylko wtedy, gdy 2 lub 3 wartości będą takie same. SD nie wchodzi w to.

— david.pfx

@StephenC: Wiele „dobrych” algorytmów, w tym quicksort, ma złożoność n ^ 2 najgorszych przypadków. Ale zobacz edycję.

— david.pfx

@ david.pfx - „Some” ... TAK. „Prawie każdy” ... NIE.

— Stephen C

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

usec    call   compare   copy    pattern
80132   62946  1971278   877143  random
47326   57578  1606067   215155  sorted : 0,1,2,3,...,n-1
49927   63578  1628883   338715  sorted in reverse : n-1,n-2,...,2,1,0
55619   63781  1596934   377330  nearly reverse : n-2,n-1,n-4,n-3,...,2,3,0,1
54714   66667  1611454   290392  median-3-killer : n-1,0,1,2,...,n-2
1491    1      99999     4       all values the same : n,n,n,...
1577    1      99999     4       first is higher : n,1,1,1,...
2778    2      156159    10      last is lower : n,n,n,...,n,1
2994    3      199996    100009  a few data : n,...,n,1,...,1
3196    3      199996    50012   zigzag : n,1,n,1,...,n,1
917796  56284  67721985  673356  valley(sawtooth?) : n-1,n-3,...,0,...,n-4,n-2

Większość przypadków jest szybsza niż losowy wzór. Wzór doliny jest złym przypadkiem dla większości selekcji przestawnych.

qsort(3)       usec = 14523   call = 0      compare = 884463    copy = 0
qsort_head()   usec = 138609  call = 99999  compare = 8120991   copy = 1214397
qsort_middle() usec = 664325  call = 99999  compare = 52928111  copy = 1036047
qsort_trad()   usec = 118122  call = 99999  compare = 6476025   copy = 1337523
qsort_random() usec = 295699  call = 58806  compare = 19439952  copy = 732962
qsort_log2()   usec = 66411   call = 63987  compare = 1597455   copy = 944821

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 .

— Leorge Takeuchi
źródło