Chciałbym wiedzieć, czy istnieje jakiś szybszy sposób sortowania takich tablic niż quicksort/mergesort.Jaki byłby najszybszy sposób sortowania tablicy słów zawierających a-z i spacjami?
Maksymalna długość tablicy to 10^6. Długość słowa wynosi> = 10 i < = 100, a słowo może zawierać a-z i spacje (łącznie 27 różnych znaków). Znaki nie są unikalne w słowach (mogą się powtarzać). Wszystkie słowa w tablicy są jednakowo długie.
Możesz umieścić wszystkie słowa w trie (lub radix tree), a następnie wydrukować go w DFS kolejności, zaczynając od „mniejszego” leksykograficznej litery na każdym poziomie w DFS.
To rozwiązanie będzie O(n* |S|) gdzie średnia długość ciągu wynosi |S|.
Prosty przykład:
Niech zbiór ciągów być [ac,ab,aca]:
Powstały trie będą:
a
/\
/ \
b c
| /\
$ $ a
|
$
I DFS (która preferuje leksykograficznie mniejszych znaków): the DFS rozpocznie się od a, przejdź do b, a następnie do znaku końcowego ($) i najpierw wydrukuje ab, a następnie wrócić do a, a prawo do c, a do następnego $ znak i będzie drukować ac, a obok a i jego $ i wypisze aca, w wyniku drukowania:
ab
ac
aca
Jak expexted .
Bravoooooooo !!! – hsalimi
Ale drzewo radix jest jednym z bardziej skomplikowanych algorytmów do wdrożenia, a koszt zarządzania pamięcią masową może z łatwością zamortyzować rzekome zyski w wydajności "O". –
Wartości ascii można obliczyć w ten sposób, że jest to rodzaj całkowity. Procedury sortowania oparte na porównywaniu w najlepszym wypadku dadzą ci O (n lg n) - Merge Sort (z dodatkową przestrzenią potrzebną do utworzenia dwóch dodatkowych tablic o rozmiarze n/2) lub O (n^2) w najgorszym (sortowanie wtrącone, quicksort, ale nie mają dodatkowej złożoności przestrzeni). Są one asymptotycznie wolniejsze niż algorytm sortowania liniowego. Polecam patrząc na CLRS (http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844). Rozdział dotyczący sortowania w czasie liniowym. O (n) to prawdopodobnie najlepsze, co możesz zrobić w tym scenariuszu. Również ten post może pomóc. Sorting in linear time?
Sprawdziłbym sortowanie radix. http://en.wikipedia.org/wiki/Radix_sort
Dolną granicą dla dowolnego sortowania opartego na porównaniu jest O (nlog (n)). Nie możesz mieć żadnego algorytmu sortowania opartego na porównywaniu elementów ze sobą, który działa w najgorszym przypadku niższym niż ten limit.
zarówno sortowanie scalone, jak i sortowanie sterty mają najgorszy czas działania O (nlog (n)) ... A sortowanie szybkie ma najgorszy czas działania O (n^2), ale średni czas działania jest O (n^log (n)).
Warto nadmienić, że chociaż szybki sortowanie ma najgorszy czas działania O (N^2), to czasami bije inne algorytmy o czasie działania O (nlog (n)) (jak heapsort) ze względu na posiadanie mały stały współczynnik i przydatność do wydajnego wykonywania na aktualnych architekturach maszyn.
liniowy algorytmów sortowania, który umożliwia sortowanie całkowite (ale nie ograniczają się tylko do nich) w liniowym O czas (n) w nie porównawczą (przykład: zliczania rodzaju wiadra sortowania i sortowanie pozycyjne)
MSD Sortowanie radix może sortować ciągi używając leksykograficznej kolejności cyfr (w tym przypadku znaków) i od lewej do prawej.
Najpierw sortuje wszystkie ciągi za pomocą lewego skrajnego znaku za pomocą innego algorytmu sortowania liniowego (np. Sortowanie wiadra), a następnie sortuj je ponownie za pomocą znaku drugiego od lewego znaku i tak dalej, aż zostaną posortowane według znaku znajdującego się najbardziej na prawo. Na końcu tablica zostanie całkowicie posortowana.
Ten algorytm będzie miał czas pracy O (k * N), gdzie N jest liczbą elementów, a k jest średnią długość klucza długość (słowo w tym przypadku będzie to> = 10 & & < = 100).
Cóż, czytałem (i przegłosowałem) odpowiedzi na temat sortowania radix i radix, bardzo pouczające.
Ale.
W przypadku sortowania radix - należy wykonać 91 przebiegów N elementów, więc będzie to 91 * N. Nie mówię o dodatkowej przestrzeni.
W przypadku mergesortu masz N * dziennik N porównuje, a od czasu zalogowania N = log 1000000 ~ 20 masz porównanie 20 * N.
Który z nich jest szybszy? :) A może się gdzieś pomyliłem?
Ale mergesort wymaga przeczytania całego łańcucha w każdej iteracji (najgorszy przypadek, chyba że można zapewnić lepszą analizę), a w sortowaniu radix, każde porównanie jest wykonywane na jednym znaku w ciągu znaków, więc jeśli masz więcej porównań operacji, każdy jest znacznie tańszy, ponieważ nie musi czytać całego ciągu znaków. [P.S. dzięki za przegrywanie :)] – amit
masz rację, mergesort porównuje i radix właśnie przechodzą. To banalne, dziękuję za wskazanie tego. Mergesort na pewno zrobi trochę lepiej niż czytanie całego łańcucha w każdej iteracji, ale nie sądzę, że pomoże to wyprzedzić sortowanie radix. –
Dlaczego nie sortowanie dystrybucji na trzy znaki: to wymagałoby przechowywania zliczającego 19683 (27 * 27 * 27) elementów, co powinno być wykonalne, a następnie potrzeba co najwyżej 34 przejścia.
Jednak już wkrótce podlisty na klucz (wiele z trzech znaków) będą na tyle krótkie, aby użyć sortowania wstawiania lub podobnego do pozostałego ciągu. 1.000.000/(27^3) to około 50
Ten sam mechanizm może być używany z dłuższymi klawiszami, jeśli mają wspólne wspólne przedrostki, tzn. Pierwsze 30 znaków dzieliłoby listę tylko na 20 lub 30 podlist. Wtedy nie reprezentujesz kluczy jako liczb, lecz jako struny i przechowujesz je w dicimeryzacji, która jest wolniejsza, ale potrzeba wtedy mniej przejść, a może i mniej pamięci. Również potrzebowałoby wyszukiwań N * log (M) z M liczbą różnych kluczy w drzewie binairy, ale mieszanie jest również możliwością.
Nie ma "najszybszego" sposobu, jeśli nie masz informacji o możliwej kolejności przychodzących danych. Musisz wybrać jeden z popularnych algorytmów na podstawie najlepszej możliwej i najgorszej możliwej wydajności (i prawdopodobieństwa, że tak) oraz ograniczenia dostępu do pamięci/danych. –
Czy założono, że cała tablica mieści się w pamięci? – goat