Login lub e-mail Hasło   

Sortowanie pozycyjne

Wprowadzenie Sortowanie pozycyjne ( radix sort ) stosowane jest do sortowania elementów, które składają się z szeregu pozycji (mogą to być liczby, gdzie pozycjami...
Wyświetlenia: 7.566 Zamieszczono 29/10/2006

Wprowadzenie

Sortowanie pozycyjne (radix sort) stosowane jest do sortowania elementów, które składają się z szeregu pozycji (mogą to być liczby, gdzie pozycjami są poszczególne cyfry; wyrazy - w tym przypadku są to poszczególne litery; mogą to także być inne dane, np. daty). Zostało wynalezione prawdopodobnie w 1929 r. przez L. J. Comrie'a. Algorytm ten wymaga użycia innego algorytmu sortowania podczas swego działania, co ważne sortowanie to musi być stabilne. Gdy jako dodatkowego algorytmu sortowania użyjemy sortowania przez zliczanie to algorytm sortowania pozycyjnego działa w czasie O(n).

 

Przykład

Rozważmy następujący ciąg liczb do posortowania:

217
157
611
055
281
475
936
544
529
177

Intuicja podpowiada nam, aby posortować te liczby według najbardziej znaczącej cyfry, tzn. pierwszej od lewej. Jednakże potem musielibyśmy rekurencyjnie posortować liczby, które mają najbardziej znaczącą cyfrę taką samą według drugiej najbardziej znaczącej cyfry (w tym przypadku środkowej). Metoda taka wymaga dodatkowej pamięci. Jednakże moglibyśmy sortowanie zacząć od drugiej strony, czyli sortować od cyfry najmniej znaczącej. W wyniku posortowania w/w liczb według najmniej znaczącej cyfry otrzymujemy:

611
281
544
055
475
936
217
157
177
529

Cyfry według których zostały posortowane liczby powyżej są podkreślone. Tak posortowane liczby sortujemy następnie według drugiej najmniej znaczącej cyfry, czyli w tym przypadku środkowej. W ten sposób otrzymujemy:

611
217
529
936
544
055
157
475
177
281

Proszę zwrócić uwagę, że gdyby nie brać pod uwagę najbardziej znaczących cyfr to podane liczby byłyby już posortowane. Posortujmy je jeszcze według najbardziej znaczącej cyfry, czyli liczby setek:

 

055
157
177
217
281
475
529
544
611
936

Liczby są już posortowane. Do podanego sortowania pozycyjnego użyliśmy trzech sortowań pomocniczych (z tylu bowiem cyfr składały się liczby). W przypadku liczb i wyrazów do sortowań pomocniczych polecam użycie sortowania przez zliczanie.

Pojawia się w tym momencie problem - co zrobić, aby posortować liczby składające się z różnej ilości cyfr? Nic trudnego - wystarczy popatrzyć na przykład powyżej, a w szczególności na liczbę 055. Po prostu dopisujemy do każdej z liczb odpowiednią ilość zer po lewej stronie, tak by składały się one z tylu cyfr, ile ma liczba, która ma ich najwięcej w danym ciągu. W tym przypadku trzeba było dopisać tylko jedno 0, aby liczba 55 stała się liczbą 3-cyfrową (055).

 

Sortowanie wyrazów

Z sortowaniem wyrazów jest podobnie jak z sortowaniem liczb. W tym przypadku pozycjami są poszczególne litery danego wyrazu. Jednakże jest pewna różnica jeśli chodzi o sortowanie wyrazów różnej długości. W tym przypadku odpowiednią ilość znaków dopisujemy za wyrazem, a nie jak to było w przypadku liczb - przed. Znak ten musi być traktowany jako wyżej w alfabecie, niż wszystkie inne - może to być na przykład spacja.

 

Inne zastosowania

Sortowanie pozycyjne stosuje się nie tylko do sortowania liczb, czy wyrazów. W ten sposób możemy także sortować np. daty. Musimy jednak pamiętać, aby sortować od pozycji najmniej znaczących. W przypadku dat - najpierw sortujemy je według dni, potem według miesięcy, a na końcu według lat.

Sortowanie pozycyjne możemy także zastosować do sortowania rekordów baz danych. Na przykład chcemy posortować książkę telefoniczną według nazwisk, a w razie gdyby się one powtarzały to według imion, a w przypadku identyczności imion i nazwisk według numeru telefonu. Aby otrzymać taki wynik powinniśmy tą książkę telefoniczną posortować najpierw według numeru telefonu, potem według imion, a na końcu według nazwisk. Złożoność obliczeniowa takiego sortowania pozycyjnego na pewno nie będzie O(n). Wynika to z tego, że do posortowania np. nazwisk trudno jest użyć sortowania przez zliczanie.

Podobne artykuły


49
komentarze: 18 | wyświetlenia: 64970
37
komentarze: 9 | wyświetlenia: 28510
50
komentarze: 27 | wyświetlenia: 63514
41
komentarze: 19 | wyświetlenia: 32981
32
komentarze: 12 | wyświetlenia: 26671
12
komentarze: 3 | wyświetlenia: 29777
11
komentarze: 2 | wyświetlenia: 33147
11
komentarze: 1 | wyświetlenia: 86393
9
komentarze: 2 | wyświetlenia: 6129
19
komentarze: 10 | wyświetlenia: 21322
21
komentarze: 9 | wyświetlenia: 12470
18
komentarze: 11 | wyświetlenia: 9266
17
komentarze: 10 | wyświetlenia: 10596
 
Autor
Artykuł




Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska