Startuj z nami!

www.szkolnictwo.pl

praca, nauka, rozrywka....

mapa polskich szkół
Nauka Nauka
Uczelnie Uczelnie
Mój profil / Znajomi Mój profil/Znajomi
Poczta Poczta/Dokumenty
Przewodnik Przewodnik
Nauka Konkurs
uczelnie

zamów reklamę
zobacz szczegóły
uczelnie

Nie znaleziono szukanej frazy! Poniżej znajduje się fraza najbardziej przypominająca szukaną.

Sortowanie przez zliczanie

Sortowanie przez zliczanie

Sortowanie przez zliczanie – metoda sortowania danych, która polega na sprawdzeniu ile wystąpień kluczy mniejszych od danego występuje w sortowanej tablicy.

Algorytm zakłada, że klucze elementów należą do skończonego zbioru (np. są to liczby całkowite z przedziału 0..100), co ogranicza możliwości jego zastosowania.

Spis treści

Zalety i wady

Główną zaletą tej metody jest liniowa złożoność obliczeniowa algorytmu – O(n+k) (n – oznacza liczebność zbioru, k – rozpiętość danych, czyli w przypadku liczb: powiększoną o 1 różnicę między maksymalną, a minimalną wartością, np. rozpiętość liczb w Dużym Lotku wynosi (49-1) + 1 = 49).

Największymi ograniczeniami algorytmu są konieczność uprzedniej znajomości zakresu danych i złożoność pamięciowa (wymaga dodatkowo O(k) lub O(n+k) pamięci).

Implementacje

Istnieją dwie implementacje algorytmu:

  • prostsza – sortująca in situ (w miejscu), zakłada, że elementy o równych kluczach są nierozróżnialne, nie mogą zatem być to klucze danych (każdy z nich jest bowiem powiązany z przenoszoną wartością – zatem, mimo iż są one równe, muszą pozostawać rozróżnialne);
  • standardowa – gwarantuje stabilność i nie wymaga dodatkowego założenia. Potrzebuje natomiast O(n) więcej pamięci;

Przykładowa implementacja w języku C++

Wersja ta sortuje n-elementową tablicę liczb całkowitych.

const int k = 77; // elementami tablicy T są liczby całkowite z                               // z przedziału 0..76const int n = 1000;int T[n]; // tablica zawierająca elementy do posortowaniaint Tp[n]; // tablica zawierająca elementy posortowaneint TPom[k]; // zawiera liczbę elementów o danej wartości int i; // zmienna pomocnicza   for(i = 0 ; i < k ; ++i)    TPom[i] = 0;                // zerowanie tablicy   for(i = 0 ; i < n ; ++i)    ++TPom[T[i]];               // po tych operacjach TPom[i] będzie zawierała                                 // liczbę wystąpień elementów o kluczach mniejszych od i  for(i = 1 ; i < k ; ++i)    TPom[i] += TPom[i-1];       // teraz TPom[i] zawiera pozycje w posortowanej                                // tablicy ostatniego elementu o kluczu i  for(i = n-1 ; i >= 0 ; --i)     Tp[--TPom[T[i]]] = T[i];   // wstawienie elementu na odpowiednią pozycję                                 // i aktualizacja TPom

Linki zewnętrzne


Inne hasła zawierające informacje o "Sortowanie przez zliczanie":

Podróżnik ...

Dziady (zwyczaj) ...

Pęcice ...

Zambezi ...

Rodzimy Kościół Polski ...

Ren ...

Dzień Zmarłych ...

Dzień Zaduszny ...

Muzeum Zoologiczne Tadasa Ivanauskasa w Kownie ...

II wiek ...


Inne lekcje zawierające informacje o "Sortowanie przez zliczanie":

Potęgi (plansza 2) ...

10b Wyprzedzanie - część 2 (plansza 11) ...

01 Znaki drogowe - tabliczki do znaków drogowych - część 2 (plansza 20) ...





Zachodniopomorskie Pomorskie Warmińsko-Mazurskie Podlaskie Mazowieckie Lubelskie Kujawsko-Pomorskie Wielkopolskie Lubuskie Łódzkie Świętokrzyskie Podkarpackie Małopolskie Śląskie Opolskie Dolnośląskie