Nie zamierzam udawać, że znam wszystkie odpowiedzi, ponieważ myślę, że uzyskanie rzeczywistych odpowiedzi może wymagać zakodowania algorytmów i sprofilowania ich na podstawie reprezentatywnych próbek danych. Ale myślałem o tym pytaniu przez cały wieczór i oto, co przyszło mi do głowy do tej pory, i kilka domysłów, co działa najlepiej, gdzie.
Niech N będzie liczbą elementów ogółem, M będzie liczbą poza kolejnością.
Sortowanie bąbelkowe będzie musiało spowodować przejście przez wszystkie N elementów około 2 * M + 1. Jeśli M jest bardzo małe (0, 1, 2?), Myślę, że będzie to bardzo trudne do pokonania.
Jeśli M jest małe (powiedzmy mniejsze niż log N), sortowanie przez wstawianie będzie miało świetną średnią wydajność. Jednak jeśli nie ma sztuczki, której nie widzę, będzie miała bardzo złą wydajność w najgorszym przypadku. (Zgadza się? Jeśli ostatni element w zamówieniu jest pierwszy, musisz wstawić każdy element, o ile widzę, co zabije wydajność.) Zgaduję, że istnieje bardziej niezawodny algorytm sortowania. przypadku, ale nie wiem, co to jest.
Jeśli M jest większe (powiedzmy równe lub duże niż log N), sortowanie introspektywne jest prawie na pewno najlepsze.
Wyjątek od tego wszystkiego: jeśli faktycznie wiesz z wyprzedzeniem, które elementy są nieposortowane, najlepszym rozwiązaniem będzie wyciągnięcie tych elementów, posortowanie ich za pomocą sortowania introspektywnego i połączenie dwóch posortowanych list w jedną posortowaną listę. Gdybyś mógł szybko dowiedzieć się, które elementy są niesprawne, byłoby to również dobre ogólne rozwiązanie - ale nie udało mi się znaleźć prostego sposobu, aby to zrobić.
Dalsze przemyślenia (z dnia na dzień): Jeśli M + 1 <N / M, możesz przejrzeć listę w poszukiwaniu serii N / M w rzędzie, które są posortowane, a następnie rozwinąć ten bieg w dowolnym kierunku, aby znaleźć -zamawiać rzeczy. To zajmie co najwyżej porównania 2BA. Następnie możesz posortować nieposortowane elementy i wykonać posortowane scalenie na dwóch listach. Sumaryczne porównania powinny być mniejsze niż coś w rodzaju 4N + M log2 (M), co, jak sądzę, przebije każdą niewyspecjalizowaną procedurę sortowania. (Jeszcze dalej myśl: to jest trudniejsze niż myślałem, ale nadal uważam, że jest to rozsądnie możliwe.)
Inną interpretacją pytania jest to, że może istnieć wiele nieuporządkowanych pozycji, ale są one bardzo blisko miejsca, w którym powinny znajdować się na liście. (Wyobraź sobie, że zaczynasz od posortowanej listy i zamieniasz każdą inną pozycję na następną.) W takim przypadku uważam, że sortowanie bąbelkowe działa bardzo dobrze - myślę, że liczba przebiegów będzie proporcjonalna do pozycji znajdującej się najdalej na miejscu. jest. Sortowanie przez wstawianie będzie działać słabo, ponieważ każdy pozasłużony element spowoduje wstawienie. Podejrzewam, że introspektywne sortowanie lub coś takiego też się sprawdzi.