1 Treści multimedialne - kodowanie, przetwarzanie, prezentacja Odtwarzanie treści multimedialnych Andrzej Majkowski 1 informatyka +

2 2 Sortowanie przez zliczanie Iwona i Ireneusz Bujnowscy

3 Sortowanie przez zliczanie Przedstawione dotychczas algorytmy sortowania działały stosunkowo wolno. Zarówno sortowanie bąbelkowe jak i sortowanie przez wybieranie były klasy O(n 2 ), to znaczy, że aby wykonać sortowanie n elementów należy wykonać około n 2 operacji dominujących.  Okazuje się, że możliwe jest znacznie szybsze uporządkowanie elementów: klasy O(n),.  Jedną z takich metod sortowania jest sortowanie przez zliczanie

4 Jak działa sortowanie przez zliczanie Najłatwiej będzie to prześledzić na bardzo prostym przykładzie mamy dana tablicę T do posortowania (dana powyżej) tworzymy pomocniczą tabele Pom wypełnioną zerami (rozmiar tablicy Pom jest uzależniony od zakresu danych w tablicy T) w naszym przypadku zakres od 0 do 3 czyli tablica Pom[4] indeksy Pom[4] wartości Pom[4] 0123 0000 012345 203303

5 Jak działa sortowanie przez zliczanie cd Realizujemy pętle: ( n –wymiar tablicy T) for (int k=0; k

6 Jak działa sortowanie przez zliczanie cd Realizujemy pętle cd: for (int k=0; k

7 Jak działa sortowanie przez zliczanie cd Tablica T: Tablica Pom wygląda następująco: następnie realizujemy pętle, która z tablicy Pom wypisuje indeksy tyle razy ile wynosi wartość poszczególnych elementów tablicy Pom –(z- zakres, wymiar tablicy pom) for (int j=0; j

8 sortowanie przez zliczanie Wady i zalety sortowania przez zliczanie –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 całkowitych: powiększoną o 1 różnicę między maksymalną, a minimalną wartością, –największymi ograniczeniami algorytmu są konieczność uprzedniej znajomości zakresu danych i złożoność pamięciowa

9