Cześć,
Czy ktoś wie jaki algorytm sortowania listy jest najszybszy? Implementowałem sortowanie przez wstawianie i on ma złożoność O(n2). Czy da się to szybciej zrobić? Czy można to zrobić w czasie O(n)?
Pozdrawiam.
Teoretycznie tak, countingsortem. Ale w praktyce to wcale nie będzie takie dobre rozwiązanie, bo moze ci braknąć miejsca :P Możesz też próbowac bucketsortem ale tutaj wiele zalezy od danych do posortowania.
Nie prościej użyć quicksorta / quickersorta ?
Radix + count?
Quick sort działa na zasadzie "dziel i zwyciężaj" więc sprawuje się tylko dobrze gdy może sobie podzielić tablicę na 2 części, podtablicę na 2 części itp. Tyle, że w tablicy taka operacja zajmuje O(1) natomiast w liście trzeba najpierw przeiterować do początku tablicy. Chyba że istnieje specjalna wersja qsorta dla tablic.
Ktoś ma inne pomysły?
@efg bzdura. Jeśli lista jest jednokierunkowa to wystarczy ci użyć quicksorta Lomuto, jak dwukierunkowa to można i zwykłego. Po prostu dwie części danych wejściowych rozdzielasz na dwie listy i sortujesz w ten sam sposób, a na koniec scalasz te listy.
A może mergesort? Wykorzystując parę specyficznych cech list, można go napisać tak, że nie będzie miał O(n) dla pamięci i ogólnie będzie lepszy, niż mergesort na tablicach. Pełno się tego wala po necie.
Jeśli potrafisz napisać Merge Sort bez używania dodatkowej pamięci z zachowaniem jego czasowej złożoności
to rzeczywiście jest on dobry
Jest stabilny i dość szybki a po odpowiednim napisaniu także in situ
W przypadku list zamieniamy same wskaźniki
Czy jest tego pełno ?
Trochę tego widziałem jednak w miarę sensowny kod jest u Wałaszka
Ciekawe czemu się podniecacie tym quick sortem jak jego złożoność zależy od danych wejściowych
i może wynosić O(n^2)
Jak na podstawie danych wejściowych wykryć tzw przypadek pesymistyczny quick sorta
(Po każdym podziale jedna z podtablic/ podlist musi mieć dokładnie jeden element)
@nowy121105, użycie dodatkowej pamięci na log(n) wskaźników - to żadne dodatkowe użycie pamięci - o ile wciąż mówimy o listach, nie zaś o gotowych kontenerach, gdzie nie da się ingerować w sposób dowolny.
Jeżeli już koniecznie chcemy używać quick sorta to należy wykryć jego przypadek pesymistyczny
i w tym pesymistycznym przypadku podmienić go na inny (merge sort jest dobry)
Heap sort chyba się nie nada bo potrzeba indeksów
(na tablicach można quick sorta w przypadku pesymistycznym zastąpić heap sortem)
Kopiec jest strukturą przypominającą drzewo binarne więc ciekawe czy heap sort nadawałby się bardziej do sortowania drzew
niż list
Sortując tablicę oś wybieramy najczęściej losowo
w przypadku listy jest to pierwszy bądź ostatni element
(ostatni jeśli trzymamy wskaźnik na ogon listy)
Jeżeli quick sorta napiszemy rekurencyjnie to może on prędzej spowodować przepełnienie stosu niż merge sort