Login lub e-mail Hasło   

Sortowanie przez zliczanie

Wprowadzenie Sortowanie przez zliczanie ( counting sort ) jest jednym z najszybszych algorytmów sortowania danych (szybszy nawet niż QuickSort ), a przy tym bardzo prosty...
Wyświetlenia: 7.630 Zamieszczono 29/10/2006

Wprowadzenie

Sortowanie przez zliczanie (counting sort) jest jednym z najszybszych algorytmów sortowania danych (szybszy nawet niż QuickSort), a przy tym bardzo prostym do wytłumaczenia. Zostało wynalezione w 1954 r. przez H.H. Sewarda. Algorytm ten działa w czasie O(n), tak więc jest to sortowanie w czasie liniowym. Mimo swoich zalet, sortowanie przez zliczanie ma swoje dwie poważne wady. Po pierwsze - do tego sortowania potrzebna jest dodatkowa pamięć(czyli nie jest to sortowanie w miejscu), a po drugie - tym sposobem można sortować tylko liczby całkowite z określonego przedziału. Nie wiem dlaczego, ale algorytm ten mimo swojej prostoty nie jest powszechnie znany, a tym bardziej używany.

 

Przykład

Wyobraźmy sobie, że mamy do posortowania następującą tablicę liczb:

0 1 1 1 0 0 1 0 0 1

Moglibyśmy posortować ją jedną ze znanych metod, jednakże nie lepiej jest policzyć ile jest elementów tablicy z wartością 0 i ile z wartością 1, a potem zapisać odpowiednią ilość pól w tej tablicy? W powyższym przypadku otrzymujemy: 5 elementów z wartością 0 i również 5 z wartością 1. Teraz po prostu zapisujemy 5 pierwszych elementów tablicy wartością 0 i 5 następnych wartością 1. W ten sposób otrzymujemy:

0 0 0 0 0 1 1 1 1 1

I po wszystkim. Tablica jest już jest posortowana! Proste, co? Jednakże ten przypadek był wyidealizowany. W prawdziwym sortowaniu liczby nie będą przyjmować tylko wartości 0, czy 1. Zakres wartości elementów tablicy przeznaczonej do sortowania może być dużo większy. W powyższym przypadku do zliczania potrzebne były nam tylko dwie zmienne (jedna do liczenia ilości 0, a druga - ilości 1). W prawdziwym sortowaniu na zliczanie elementów należy przeznaczyć tablicę o wielkości równej rozpiętości liczb z tablicy do posortowania. Na przykład, gdy elementami tablicy przeznaczonej do sortowania są elementy typu Word lub Integer (short int w C) to tablica do zliczania powinna zawierać 65536 elementów (tyle bowiem różnych wartości może przyjąć zmienna Word, czy Integer). To jest właśnie powód, dlaczego sortowaniem przez zliczanie nie można posortować liczb rzeczywistych, a jedynie liczby całkowite. Proszę zwrócić uwagę na to, że sortowanie przez zliczanie nie wykonuje żadnych porównań. Jego ważną własnością jest jego stabilność.

Podobne artykuły


49
komentarze: 18 | wyświetlenia: 64978
37
komentarze: 9 | wyświetlenia: 28520
50
komentarze: 27 | wyświetlenia: 63526
41
komentarze: 19 | wyświetlenia: 32981
32
komentarze: 12 | wyświetlenia: 26675
12
komentarze: 3 | wyświetlenia: 29779
11
komentarze: 2 | wyświetlenia: 33152
11
komentarze: 1 | wyświetlenia: 86405
9
komentarze: 2 | wyświetlenia: 6134
19
komentarze: 10 | wyświetlenia: 21324
21
komentarze: 9 | wyświetlenia: 12474
18
komentarze: 11 | wyświetlenia: 9268
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