Mam problem ze znalezieniem dobrych zasobów, które dają najgorszy przypadek w miejscu stabilnego algorytmu sortowania. Czy ktoś wie o dobrych zasobach?
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 ) O ( n 2 ) 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.1 1 1
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 )
Jest to czysto teoretyczne i nie mam praktycznego zastosowania. Chciałbym tylko poznać algorytm, który ma wszystkie trzy z tych funkcji.
źródło
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
źródło
Możesz napisać stabilne miejsce scalania w miejscu. Zobacz to po szczegóły. Własnymi słowami autora:
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.
źródło
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:
Źródło: bugs.python.org , autor: Tim Peters
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).
źródło