Sortowanie bąbelkowe jest okropne. Zawsze jest O (n ^ 2). Przynajmniej usuń to ze swojej odpowiedzi, żeby było dobrze.
jjnguy
79
jjnguy, to jest po prostu błędne. Myślę, że musisz powtórzyć swoją klasę algorytmów. Na prawie posortowanych danych (to przypadek adaptacyjny) jest O (N). Jednak wymaga to 2 przejść przez dane, a Insertion zajmuje tylko 1 dla prawie posortowanych danych, co sprawia, że Insertion jest zwycięzcą. Bańka wciąż jest dobra
mmcdole
3
Wydajność spada naprawdę bardzo, jeśli dane nigdy nie są prawie posortowane. Nadal bym go osobiście nie używał.
Blorgbeard wychodzi
5
To łącze zostało przerwane, kiedy go wypróbowałem. Spróbuj tego zamiast tego: sorting-algorithms.com
Michael La Voie
107
Tylko kilka pozycji => SORTOWANIE WSTAWIANIA
Przedmioty są w większości już posortowane => SORTOWANIE WSTAWIANIA
W trosce o najgorsze scenariusze => SORTOWANIE HEAP
Zainteresowany dobrym wynikiem przeciętnym => QUICKSORT
Przedmioty pochodzą z gęstego wszechświata => SORTOWANIE ŁYŻKI
Chęć napisania jak najmniejszego kodu => SORTOWANIE WSTAWIANIA
To jest dokładnie taka odpowiedź, jakiej szukałem, czytam książki, ale nie wydaje mi się, aby znaleźć jakieś jasne wyjaśnienie wyboru alogorytmów w określonych przypadkach, czy mógłbyś to rozwinąć lub podać link, abym mógł wejść do to trochę więcej? Dzięki
Simran kaur
9
Należy dodać „Dane są już posortowane według innego kryterium => MERGE SORT”
Jim Hunziker
30
sortowanie czasu
Timsort jest "adaptacyjnym, stabilnym, naturalnym scalaniem" z " nadprzyrodzoną wydajnością na wielu rodzajach częściowo uporządkowanych tablic (potrzeba mniej niż lg (N!) Porównań, a zaledwie N-1)". Wbudowany Pythonsort()używa tego algorytmu od jakiegoś czasu, najwyraźniej z dobrymi wynikami. Jest specjalnie zaprojektowany do wykrywania i wykorzystywania częściowo posortowanych podciągów w danych wejściowych, które często występują w rzeczywistych zbiorach danych. W prawdziwym świecie często bywa, że porównania są znacznie droższe niż zamiana pozycji na liście, ponieważ zwykle zamienia się tylko wskaźnikami, co bardzo często sprawia, że sortowanie czasu jest doskonałym wyborem. Jeśli jednak wiesz, że twoje porównania są zawsze bardzo tanie (na przykład napisanie programu zabawkowego do sortowania 32-bitowych liczb całkowitych), istnieją inne algorytmy, które prawdopodobnie będą działać lepiej. Najłatwiejszym sposobem wykorzystania sortowania czasu jest oczywiście użycie Pythona, ale ponieważ Python jest open source, możesz także pożyczyć kod. Alternatywnie, powyższy opis zawiera więcej niż wystarczająco dużo szczegółów, aby napisać własną implementację.
@JF Sebastian: sortowanie czasu jest znacznie szybsze niż lg(n!)porównania na prawie posortowanej tablicy, aż do O(n)! | @behrooz: Żadne sortowanie porównawcze nie może mieć średniej wielkości przypadku lepszej niż O(n log n)i lg(n!)jest O(n log n). Tak więc najgorszy przypadek sortowania czasu jest asymptotycznie nie gorszy niż w przypadku jakiegokolwiek innego rodzaju porównania. Ponadto jego najlepszy przypadek jest lepszy lub równy jakiemukolwiek innemu sortowaniu porównawczemu.
Artelius
3
Timsort jest nadal O (nlogn) w najgorszym przypadku, ale jego dobre przypadki są całkiem przyjemne. Oto porównanie z kilkoma wykresami: stromberg.dnsalias.org/~strombrg/sort-comparison Zauważ, że timsort w Cython nie było prawie tak szybko, jak Pythona zbudowany w timsort w C.
user1277476
19
Sortowanie przez wstawianie z następującym zachowaniem:
Dla każdego elementu kw gniazdach 1..nnajpierw sprawdź, czy el[k] >= el[k-1]. Jeśli tak, przejdź do następnego elementu. (Oczywiście pomiń pierwszy element).
Jeśli nie, użyj wyszukiwania binarnego w elementach, 1..k-1aby określić miejsce wstawienia, a następnie przewiń elementy. (Możesz to zrobić tylko wtedy, gdy k>Tgdzie Tjest jakaś wartość progowa; przy małych kjest to przesada.)
Myślę, że sortowanie bąbelkowe może to pokonać, jeśli liczba nieposortowanych elementów jest bardzo mała (np. Jeden lub dwa), ale ogólnie wydaje mi się, że jest to prawdopodobnie najlepsze rozwiązanie.
Sol
Ze względu na krok 1 dla już posortowanych elementów istnieje dokładnie jedno porównanie i zero przesunięć danych, co jest oczywiście najlepszym, co możesz zrobić. Krok 2 to ten, który możesz ulepszyć, ale bubble przesunie tę samą liczbę elementów i może mieć więcej porównań, w zależności od twojego impl.
Jason Cohen
Właściwie po dalszych rozważaniach myślę, że sortowanie bąbelkowe jest silniejsze niż myślałem. Właściwie to dość trudne pytanie. Na przykład, jeśli weźmiesz pod uwagę przypadek, w którym lista jest całkowicie posortowana, z wyjątkiem elementu, który powinien być ostatni, jest pierwszy, sortowanie bąbelkowe znacznie przewyższy to, co opisujesz.
Sol,
Próbowałem to zaimplementować, ale wyszukiwanie binarne nie jest dużym postępem, ponieważ nadal musisz przesunąć cały blok, aby wstawić element. Więc zamiast 2xrange otrzymujesz range + logb (zakres).
Jest oparty na szybkim sortowaniu, ale pozwala uniknąć najgorszego przypadku, jaki ma szybkie sortowanie dla prawie posortowanych list.
Sztuczka polega na tym, że ten algorytm sortowania wykrywa przypadki, w których quicksort przechodzi w tryb najgorszego przypadku i przełącza się do sortowania stosowego lub scalającego. Prawie posortowane partycje są wykrywane przez jakąś nienaiwną metodę partycji, a małe partycje są obsługiwane za pomocą sortowania przez wstawianie.
Otrzymujesz najlepsze ze wszystkich głównych algorytmów sortowania za cenę większej ilości kodu i większej złożoności. I możesz być pewien, że nigdy nie napotkasz najgorszego zachowania, niezależnie od tego, jak wyglądają Twoje dane.
Jeśli jesteś programistą C ++, sprawdź algorytm std :: sort. Może już wewnętrznie używać sortowania introspekcyjnego.
Splaysort to mało znana metoda sortowania oparta na drzewach typu splay , typie adaptacyjnego drzewa binarnego. Splaysort jest dobry nie tylko dla danych częściowo posortowanych, ale także dla danych częściowo posortowanych odwrotnie, a nawet dla wszystkich danych, które mają wcześniej istniejącą kolejność. W ogólnym przypadku jest to O (nlogn) i O (n) w przypadku, gdy dane są w jakiś sposób posortowane (do przodu, do tyłu, organ-piszczałka itp.).
Jego wielką zaletą w porównaniu z sortowaniem przez wstawianie jest to, że nie powraca do zachowania O (n ^ 2), gdy dane nie są w ogóle posortowane, więc nie musisz mieć absolutnej pewności, że dane są częściowo posortowane przed ich użyciem .
Jego wadą jest dodatkowa przestrzeń nad strukturą drzewa splay, której potrzebuje, a także czas wymagany do zbudowania i zniszczenia drzewa splay. Ale w zależności od oczekiwanej wielkości danych i ilości wstępnie posortowanych danych, koszty ogólne mogą być tego warte ze względu na zwiększenie szybkości.
Smoothsort Dijkstry to świetne sortowanie już posortowanych danych. Jest to wariant heapsort, który działa w O (n lg n) w najgorszym przypadku i O (n) w najlepszym przypadku. I napisał analizę algorytmu, w przypadku jesteś ciekawy jak to działa.
Naturalne scalanie jest kolejnym naprawdę dobrym rozwiązaniem do tego celu - jest to oddolny wariant scalania, który działa, traktując dane wejściowe jako konkatenację wielu różnych posortowanych zakresów, a następnie łącząc je ze sobą za pomocą algorytmu scalania. Powtarzasz ten proces, dopóki cały zakres wejściowy nie zostanie posortowany. Działa to w czasie O (n), jeśli dane są już posortowane i O (n lg n) w najgorszym przypadku. Jest bardzo elegancki, choć w praktyce nie jest tak dobry, jak inne rodzaje adaptacyjne, takie jak Timsort lub smoothsort.
jakie są stałe czasu wykonywania funkcji smoothsort w porównaniu z innymi algorytmami sortowania? (tj. runtime (smoothsort) / runtime (insertionsort) dla tych samych danych)
Arne Babenhauserheide
4
Jeśli elementy są już posortowane lub jest ich niewiele, byłby to idealny przypadek użycia sortowania przez wstawianie!
Sortowanie przez wstawianie zajmuje czas O (n + liczba inwersji).
Inwersja to para (i, j) takich, że i < j && a[i] > a[j]. To znaczy para nieczynna.
Jedną z miar bycia „prawie posortowanym” jest liczba inwersji - można przyjąć, że „prawie posortowane dane” oznaczają dane z kilkoma inwersjami. Jeśli wiadomo, że liczba inwersji jest liniowa (na przykład właśnie dodałeś elementy O (1) do posortowanej listy), sortowanie przez wstawianie zajmuje O (n) czasu.
Jak wszyscy mówili, uważaj na naiwny Quicksort - który może mieć wydajność O (N ^ 2) w przypadku posortowanych lub prawie posortowanych danych. Niemniej jednak, z odpowiednim algorytmem wyboru przestawienia (losowym lub medianą z trzech - zobacz Wybieranie obrotu do szybkiego sortowania) ), funkcja Quicksort będzie nadal działać normalnie.
Ogólnie rzecz biorąc, trudność z wyborem algorytmów, takich jak sortowanie przez wstawianie, polega na podjęciu decyzji, kiedy dane są na tyle nieuporządkowane, aby funkcja Quicksort była naprawdę szybsza.
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.
Jeśli potrzebujesz konkretnej implementacji algorytmów sortowania, struktur danych lub czegokolwiek, co ma związek z powyższymi, czy mógłbym polecić Ci doskonały projekt "Struktury danych i algorytmy" na CodePlex?
Będzie miał wszystko, czego potrzebujesz, bez odkrywania na nowo koła.
Ten niezły zbiór algorytmów sortujących w tym celu w odpowiedziach wydaje się nie zawierać Gnome Sort , który również byłby odpowiedni i prawdopodobnie wymaga najmniejszego wysiłku wdrożeniowego.
Sortowanie przez wstawianie jest najlepszym przypadkiem O (n) na posortowanych danych wejściowych. I jest bardzo blisko na większości posortowanych danych wejściowych (lepsze niż szybkie sortowanie).
Spójność nie ma tutaj znaczenia. Heapsort da O (n lg n) nawet dla posortowanych danych i nie jest tak naprawdę adaptacyjny. Dostępne opcje to: sortowanie przez wstawianie, sortowanie w czasie i sortowanie bąbelkowe.
Maksymalnie
0
Sortowanie bąbelkowe (lub, jeszcze bezpieczniejsze, dwukierunkowe sortowanie bąbelkowe) jest prawdopodobnie idealne dla większości sortowanych list, chociaż założę się, że zmodyfikowane sortowanie grzebieniowe (ze znacznie mniejszym początkowym rozmiarem odstępu) byłoby trochę szybsze, gdyby lista nie była '' t równie doskonale posortowane. Sortowanie grzebieniowe degraduje się do sortowania bąbelkowego.
cóż, zależy to od przypadku użycia. Jeśli wiesz, które elementy są zmieniane, jeśli o mnie chodzi, najlepszym rozwiązaniem będzie usunięcie i włożenie.
Ten "o ile mi wiadomo" test wydajności algorytmu rozjaśnił mój dzień :) Ale mówiąc poważnie, pisząc "usuń i wstaw" miałeś na myśli Sortowanie przez wstawianie (o czym była już mowa w poprzednich odpowiedziach), czy też oferujesz nowy rodzaj algorytmu? Jeśli tak, proszę rozszerzyć swoją odpowiedź.
yoniLavi
0
Sortowanie bąbelkowe jest zdecydowanie zwycięzcą Następnym na radarze będzie sortowanie przez wstawianie.
Proponuję zapoznać się z dostępnymi odpowiedziami przed wysłaniem, aby uniknąć duplikatów.
angainor
-1
Trzymaj się z dala od QuickSort - jest to bardzo nieefektywne w przypadku wstępnie posortowanych danych. Sortowanie przez wstawianie dobrze radzi sobie z prawie posortowanymi danymi, przenosząc jak najmniejszą liczbę wartości.
Odpowiedzi:
Opierając się na wysoce naukowej metodzie oglądania animowanych gifów , powiedziałbym, że rodzaje Insertion i Bubble są dobrymi kandydatami.
źródło
Tylko kilka pozycji => SORTOWANIE WSTAWIANIA
Przedmioty są w większości już posortowane => SORTOWANIE WSTAWIANIA
W trosce o najgorsze scenariusze => SORTOWANIE HEAP
Zainteresowany dobrym wynikiem przeciętnym => QUICKSORT
Przedmioty pochodzą z gęstego wszechświata => SORTOWANIE ŁYŻKI
Chęć napisania jak najmniejszego kodu => SORTOWANIE WSTAWIANIA
źródło
sortowanie czasu
Timsort jest "adaptacyjnym, stabilnym, naturalnym scalaniem" z " nadprzyrodzoną wydajnością na wielu rodzajach częściowo uporządkowanych tablic (potrzeba mniej niż lg (N!) Porównań, a zaledwie N-1)". Wbudowany Python
sort()używa tego algorytmu od jakiegoś czasu, najwyraźniej z dobrymi wynikami. Jest specjalnie zaprojektowany do wykrywania i wykorzystywania częściowo posortowanych podciągów w danych wejściowych, które często występują w rzeczywistych zbiorach danych. W prawdziwym świecie często bywa, że porównania są znacznie droższe niż zamiana pozycji na liście, ponieważ zwykle zamienia się tylko wskaźnikami, co bardzo często sprawia, że sortowanie czasu jest doskonałym wyborem. Jeśli jednak wiesz, że twoje porównania są zawsze bardzo tanie (na przykład napisanie programu zabawkowego do sortowania 32-bitowych liczb całkowitych), istnieją inne algorytmy, które prawdopodobnie będą działać lepiej. Najłatwiejszym sposobem wykorzystania sortowania czasu jest oczywiście użycie Pythona, ale ponieważ Python jest open source, możesz także pożyczyć kod. Alternatywnie, powyższy opis zawiera więcej niż wystarczająco dużo szczegółów, aby napisać własną implementację.źródło
lg(n!)porównania na prawie posortowanej tablicy, aż doO(n)! | @behrooz: Żadne sortowanie porównawcze nie może mieć średniej wielkości przypadku lepszej niżO(n log n)ilg(n!)jestO(n log n). Tak więc najgorszy przypadek sortowania czasu jest asymptotycznie nie gorszy niż w przypadku jakiegokolwiek innego rodzaju porównania. Ponadto jego najlepszy przypadek jest lepszy lub równy jakiemukolwiek innemu sortowaniu porównawczemu.Sortowanie przez wstawianie z następującym zachowaniem:
kw gniazdach1..nnajpierw sprawdź, czyel[k] >= el[k-1]. Jeśli tak, przejdź do następnego elementu. (Oczywiście pomiń pierwszy element).1..k-1aby określić miejsce wstawienia, a następnie przewiń elementy. (Możesz to zrobić tylko wtedy, gdyk>TgdzieTjest jakaś wartość progowa; przy małychkjest to przesada.)Ta metoda zapewnia najmniejszą liczbę porównań.
źródło
Spróbuj sortowania introspekcyjnego. http://en.wikipedia.org/wiki/Introsort
Jest oparty na szybkim sortowaniu, ale pozwala uniknąć najgorszego przypadku, jaki ma szybkie sortowanie dla prawie posortowanych list.
Sztuczka polega na tym, że ten algorytm sortowania wykrywa przypadki, w których quicksort przechodzi w tryb najgorszego przypadku i przełącza się do sortowania stosowego lub scalającego. Prawie posortowane partycje są wykrywane przez jakąś nienaiwną metodę partycji, a małe partycje są obsługiwane za pomocą sortowania przez wstawianie.
Otrzymujesz najlepsze ze wszystkich głównych algorytmów sortowania za cenę większej ilości kodu i większej złożoności. I możesz być pewien, że nigdy nie napotkasz najgorszego zachowania, niezależnie od tego, jak wyglądają Twoje dane.
Jeśli jesteś programistą C ++, sprawdź algorytm std :: sort. Może już wewnętrznie używać sortowania introspekcyjnego.
źródło
Splaysort to mało znana metoda sortowania oparta na drzewach typu splay , typie adaptacyjnego drzewa binarnego. Splaysort jest dobry nie tylko dla danych częściowo posortowanych, ale także dla danych częściowo posortowanych odwrotnie, a nawet dla wszystkich danych, które mają wcześniej istniejącą kolejność. W ogólnym przypadku jest to O (nlogn) i O (n) w przypadku, gdy dane są w jakiś sposób posortowane (do przodu, do tyłu, organ-piszczałka itp.).
Jego wielką zaletą w porównaniu z sortowaniem przez wstawianie jest to, że nie powraca do zachowania O (n ^ 2), gdy dane nie są w ogóle posortowane, więc nie musisz mieć absolutnej pewności, że dane są częściowo posortowane przed ich użyciem .
Jego wadą jest dodatkowa przestrzeń nad strukturą drzewa splay, której potrzebuje, a także czas wymagany do zbudowania i zniszczenia drzewa splay. Ale w zależności od oczekiwanej wielkości danych i ilości wstępnie posortowanych danych, koszty ogólne mogą być tego warte ze względu na zwiększenie szybkości.
Papieru na splaysort został opublikowany w Software - Praktyka i doświadczenie.
źródło
wstawianie lub sortowanie powłoki!
źródło
Smoothsort Dijkstry to świetne sortowanie już posortowanych danych. Jest to wariant heapsort, który działa w O (n lg n) w najgorszym przypadku i O (n) w najlepszym przypadku. I napisał analizę algorytmu, w przypadku jesteś ciekawy jak to działa.
Naturalne scalanie jest kolejnym naprawdę dobrym rozwiązaniem do tego celu - jest to oddolny wariant scalania, który działa, traktując dane wejściowe jako konkatenację wielu różnych posortowanych zakresów, a następnie łącząc je ze sobą za pomocą algorytmu scalania. Powtarzasz ten proces, dopóki cały zakres wejściowy nie zostanie posortowany. Działa to w czasie O (n), jeśli dane są już posortowane i O (n lg n) w najgorszym przypadku. Jest bardzo elegancki, choć w praktyce nie jest tak dobry, jak inne rodzaje adaptacyjne, takie jak Timsort lub smoothsort.
źródło
Jeśli elementy są już posortowane lub jest ich niewiele, byłby to idealny przypadek użycia sortowania przez wstawianie!
źródło
Sortowanie przez wstawianie zajmuje czas O (n + liczba inwersji).
Inwersja to para
(i, j)takich, żei < j && a[i] > a[j]. To znaczy para nieczynna.Jedną z miar bycia „prawie posortowanym” jest liczba inwersji - można przyjąć, że „prawie posortowane dane” oznaczają dane z kilkoma inwersjami. Jeśli wiadomo, że liczba inwersji jest liniowa (na przykład właśnie dodałeś elementy O (1) do posortowanej listy), sortowanie przez wstawianie zajmuje O (n) czasu.
źródło
Jak wszyscy mówili, uważaj na naiwny Quicksort - który może mieć wydajność O (N ^ 2) w przypadku posortowanych lub prawie posortowanych danych. Niemniej jednak, z odpowiednim algorytmem wyboru przestawienia (losowym lub medianą z trzech - zobacz Wybieranie obrotu do szybkiego sortowania) ), funkcja Quicksort będzie nadal działać normalnie.
Ogólnie rzecz biorąc, trudność z wyborem algorytmów, takich jak sortowanie przez wstawianie, polega na podjęciu decyzji, kiedy dane są na tyle nieuporządkowane, aby funkcja Quicksort była naprawdę szybsza.
źródło
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.
źródło
Jeśli potrzebujesz konkretnej implementacji algorytmów sortowania, struktur danych lub czegokolwiek, co ma związek z powyższymi, czy mógłbym polecić Ci doskonały projekt "Struktury danych i algorytmy" na CodePlex?
Będzie miał wszystko, czego potrzebujesz, bez odkrywania na nowo koła.
Tylko moje małe ziarnko soli.
źródło
Ten niezły zbiór algorytmów sortujących w tym celu w odpowiedziach wydaje się nie zawierać Gnome Sort , który również byłby odpowiedni i prawdopodobnie wymaga najmniejszego wysiłku wdrożeniowego.
źródło
Sortowanie przez wstawianie jest najlepszym przypadkiem O (n) na posortowanych danych wejściowych. I jest bardzo blisko na większości posortowanych danych wejściowych (lepsze niż szybkie sortowanie).
źródło
rozważ Wypróbuj Heap. Uważam, że jest to najbardziej spójny z rodzajów O (n lg n).
źródło
Sortowanie bąbelkowe (lub, jeszcze bezpieczniejsze, dwukierunkowe sortowanie bąbelkowe) jest prawdopodobnie idealne dla większości sortowanych list, chociaż założę się, że zmodyfikowane sortowanie grzebieniowe (ze znacznie mniejszym początkowym rozmiarem odstępu) byłoby trochę szybsze, gdyby lista nie była '' t równie doskonale posortowane. Sortowanie grzebieniowe degraduje się do sortowania bąbelkowego.
źródło
cóż, zależy to od przypadku użycia. Jeśli wiesz, które elementy są zmieniane, jeśli o mnie chodzi, najlepszym rozwiązaniem będzie usunięcie i włożenie.
źródło
Sortowanie bąbelkowe jest zdecydowanie zwycięzcą Następnym na radarze będzie sortowanie przez wstawianie.
źródło
Trzymaj się z dala od QuickSort - jest to bardzo nieefektywne w przypadku wstępnie posortowanych danych. Sortowanie przez wstawianie dobrze radzi sobie z prawie posortowanymi danymi, przenosząc jak najmniejszą liczbę wartości.
źródło