algorytm.org

Sortowanie przez zliczanie (countingsort)

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Sortowanie przez zliczanie (countingsort)
Ocena użytkowników:***** / 44
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 13 sierpnia 2005 10:45

Sortowanie przez zliczanie ma jedną potężną zaletę i jedną równie potężną wadę:
  • Zaleta: działa w czasie liniowym (jest szybki)
  • Wada: może sortować wyłącznie liczby całkowite
Obydwie te cechy wynikają ze sposobu sortowania. Polega ono na liczeniu, ile razy dana liczba występuje w ciągu, który mamy posortować. Następnie wystarczy utworzyć nowy ciąg, korzystając z danych zebranych wcześniej. Np. mamy posortować ciąg: 3,6,3,2,7,1,7,1. Po zliczeniu (w jednym korku) operujemy danymi na temat liczności poszczególnych liczb:
  • Liczba 1 występuje 2 razy
  • Liczba 2 występuje 1 raz
  • Liczba 3 występuje 2 razy
  • Liczba 4 występuje 0 razy
  • Liczba 5 występuje 0 razy
  • Liczba 6 występuje 1 raz
  • Liczba 7 występuje 2 razy
Na podstawie tych danych tworzymy ciąg: 1,1,2,3,3,6,7,7. Jest to ciąg wejściowy, ale posortowany. Należy zauważyć trzy ważne rzeczy:
  1. Proces zliczania odbył się w jednym kroku
  2. Nie doszło do ani jednej zamiany elementów
  3. Proces tworzenia tablicy wynikowej odbył się w jednym kroku
Algorytmy ten posiada jednak również wady:
  1. Do przechowywania liczby wyrazów ciągu musimy użyć tablicy, o liczbie elementów równej największemu elementowi ciągu
  2. Sortować można jedynie liczby całkowite

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Michał KnasieckiC/C++
.cpp
.cpp
***** / 16
MarianC/C++C++
.cpp
.cpp
***** / 11
Michał KnasieckiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 3
Tomasz LubińskiJava
.java
.java
***** / 6
Maciej LipińskiJavaScriptfunkcja sortująca + test
.js
.js
***** / 2
Jakub KoniecznyJava_Block
.jbf
.jbf
***** / 1
Rafał GawlikPythonPython2, Python3
.py
.py
***** / 3
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 27 maja 2011 08:46
Komentarze
photo
+1 # rafał 2009-11-14 15:42
...zliczeniu (w jednym korku) operujemy... taką literówkę złapałem
pozdrawiam
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz