W najgorszym przypadku w miejscu stabilny rodzaj?

Mam problem ze znalezieniem dobrych zasobów, które dają najgorszy przypadek w miejscu stabilnego algorytmu sortowania. Czy ktoś wie o dobrych zasobach? $O(n \ln n)$

Tylko przypomnienie, w miejscu oznacza, że wykorzystuje przekazaną tablicę, a algorytm sortujący może używać tylko stałej dodatkowej przestrzeni. Stabilny oznacza, że elementy z tym samym kluczem pojawiają się w tej samej kolejności w posortowanej tablicy, jak w oryginale.

Na przykład naiwne sortowanie scalające jest najgorszym przypadkiem i jest stabilne, ale używa dodatkowej przestrzeni. Standardowy Quicksort może być stabilny, jest na miejscu, ale w najgorszym przypadku . Heapsort jest na miejscu, w najgorszym przypadku ale nie jest stabilny. Wikipedia ma niezły wykres, które algorytmy sortowania mają wady. Zauważ, że nie ma algorytmu sortowania, który wymienia, który ma wszystkie trzy warunki stabilności, najgorszego przypadku i jest na miejscu. $O(n \ln n)$ $O(n)$ $O(n^2)$ $O(n \ln n)$ $O(n \ln n)$

Znalazłem artykuł Katajainen, Pasanen i Teuhola, zatytułowany „Praktyczne połączenie w miejscu” , który twierdzi, że w najgorszym przypadku istnieje stabilny wariant połączenia. Jeśli dobrze rozumiem ich wyniki, używają rekursywnie scalania (oddolnego?) Na pierwszym tablicy i na drugim tablicy i używają drugiego jako miejsce na zarysowania, aby wykonać scalenie. Wciąż to czytam, więc doceniam wszelkie informacje na temat tego, czy poprawnie interpretuję ich wyniki. $O(n \ln n)$ $\frac{1}{4}$ $\frac{1}{2}$ $\frac{1}{4}$

Byłbym również bardzo zainteresowany najgorszym przypadkiem w miejscu stabilnego szybkiego sortowania. Z tego, co rozumiem, modyfikowanie szybkiego sortowania jako najgorszego przypadku wymaga wybrania odpowiedniego elementu przestawnego, który zniszczyłby stabilność, która normalnie cieszyłaby się. $O(n \ln n)$ $O(n \ln n)$

Jest to czysto teoretyczne i nie mam praktycznego zastosowania. Chciałbym tylko poznać algorytm, który ma wszystkie trzy z tych funkcji.

— użytkownik834
źródło

Jest to podobne pytanie na SO tutaj z odpowiedzią, która daje odwołać zawartych w pytaniu. Uważam, że nie jest to podwójne pytanie, ponieważ proszę o dalsze wyjaśnienia, więcej literatury i, przy odrobinie szczęścia, opis algorytmu.

— user834,

Zobacz to pytanie na stronie math.stackexchange.com.

— Tsuyoshi Ito

Dlaczego inny sposób wyboru osi w QuickSort zniszczyłby jej stabilność?

— svick

@svick, jedynym sposobem, w jaki wiem, jak sprawić, by QuickSort był najgorszym przypadkiem

jest wybranie osi obrotu bardziej inteligentnie niż losowo. Nauczyłem się tego, używając algorytmu selekcji, który wykorzystuje algorytm mediany mediany, który niszczy stabilność. Jeśli coś przeoczyłem, daj mi znać.

O (n \ln n)

$O(n \ln n)$

— user834,

@TsuyoshiIto, zastanów się nad odpowiedzią. Ponadto, jeśli mógłbyś podać krótki szkic algorytmu, myślę, że to też byłoby bardzo pomocne.

— user834,

Odpowiedzi:

Istnieje kilka algorytmów, które są powyższe, i prawie wszystkie z nich zostały wynalezione w ciągu ostatnich 30 lat.

Prawdopodobnie najładniejsza jest klasa algorytmów o nazwie Block sort , w tym wersja (o nazwie WikiSort) autorstwa Kima i Kutznera w 2008 roku. Jest to nie tylko stabilna i całkowicie na miejscu (narzut pamięci O (1) w modelu transdikotomicznym), ale jest również adaptacyjny i dlatego podejmie mniej kroków, aby posortować listy prawie posortowane, konwergując do porównań O (n) w przypadku już posortowanej listy. Implementację w C, C ++ i Javie można znaleźć tutaj: https://github.com/BonzaiThePenguin/WikiSort

Interesujący jest również algorytm GrailSort (również sortowanie blokowe) Huanga i Langstona (1989-1992), który faktycznie przewyższa WikiSort w kilku typach przypadków testowych. Implementacja C ++ jest dostępna tutaj: https://github.com/Mrrl/GrailSort

— kwintopia
źródło

Możesz napisać stabilne miejsce scalania w miejscu. Zobacz to po szczegóły. Własnymi słowami autora:

Piękny na miejscu - algorytm scalania. Przetestuj na odwróconych tablicach, aby zrozumieć, jak działają rotacje. Najszybszy znany na miejscu stabilny rodzaj. Bez ryzyka eksplozji stosu. Koszt: stosunkowo duża liczba ruchów. Stos może być nadal drogi. Jest to rodzaj scalania z inteligentnym scalaniem, które „obraca” tablice podrzędne. Ten kod jest kopiowany z biblioteki stl C ++ i przetłumaczony na Javę.

Nie skopiuję tutaj kodu, ale można go znaleźć pod linkiem lub sprawdzając C ++ STL. Daj mi znać, jeśli chcesz, abym spróbował podać bardziej szczegółowy opis tego, co się tutaj dzieje.

— Patrick87
źródło

O (\ln n)

$O(\ln n)$

O (1)

$O(1)$

O (\ln n)

$O(\ln n)$

Knuth zajmuje się tym również w TAoCP.

— Raphael

O (n \ln^{2} n)

$O(n\ln^2n)$

Proszę wziąć to za długi komentarz do kilku praktycznych przemyśleń. Chociaż nie jest to odpowiedź na twoje pytanie, myślę, że możesz zainteresować się tą dyskusją w języku Python:

$\lg(N!)$ $N-1$

[...]

Scalanie sąsiadujących ze sobą odcinków o długości A i B w miejscu jest bardzo trudne . Znane są konstrukcje teoretyczne, które potrafią to zrobić, ale są zbyt trudne i powolne do praktycznego zastosowania . Ale jeśli mamy pamięć temp równą min (A, B), jest to łatwe.

Źródło: bugs.python.org , autor: Tim Peters

$\mathcal{O}(n \log n)$

Zauważ również, że Timsort działa dobrze na już posortowanych tablicach.

Python korzysta z Timsort (który jest Mergesort z pewnymi poprawkami), a gdy kilka lat temu sprawdziłem implementację Java, był to również Mergesort (myślę, że teraz także używają Timsort).

— Martin Thoma
źródło