Wątek zablokowany 2016-04-21 15:08 przez ŁF.

Sortowanie listy

0

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.

0

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 ?

0

Radix + count?

0

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?

0

@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.

0

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.

0

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)

0

@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.

0

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

1 użytkowników online, w tym zalogowanych: 0, gości: 1