Film samouczek
Sortowanie pozycyjne liczb
W tej sekcji zaimplementujemy algorytm sortowania pozycyjnego liczb wykorzystujący sortowanie przez zliczaniesortowanie przez zliczanie. Algorytm sortowania przez zliczaniesortowania przez zliczanie jest algorytmem stabilnymalgorytmem stabilnym, co oznacza, że po posortowaniu elementy o równej wartości będą ułożone w takiej samej kolejności, w jakiej były w nieposortowanym zbiorze. Jest to warunek niezbędny w sortowaniu pozycyjnym.
W lipcu 2008 roku CBOS przeprowadziło ankietę. Treść brzmiała następująco:
Niedawno Irlandczycy odrzucili w referendum traktat lizboński. Czy pana/pani zdaniem prezydent Polski powinien w tej sytuacji ratyfikować traktat lizboński, czy też nie?
Wyniki ankiety:
34% odpowiedziało: „Trudno powiedzieć”,
29% odpowiedziało: „Raczej tak”,
23% odpowiedziało: „Zdecydowanie tak”,
10% odpowiedziało: „Raczej nie”,
4% odpowiedziało: „Zdecydowanie nie”.
Napisz program sortujący niemalejąco wyniki ankiety, dotyczącej opinii o traktacie lizbońskim, wykorzystując sortowanie pozycyjne liczb (radix sort). W implementacji użyj stabilnego algorytmu sortowania przez zliczaniealgorytmu sortowania przez zliczanie (counting sort).
Specyfikacja:
Dane:
dane[]– jednowymiarowa tablica liczb naturalnych; dane do posortowanialiczbaElementow– liczba naturalna; długość tablicydaneliczbaCyfr– liczba naturalna dodatnia; liczba cyfr tworzących największą liczbę z tablicydane
Wynik:
dane– posortowana niemalejąco tablica liczb naturalnych
Porównaj swoje rozwiązanie z przedstawionym w filmie.
Film dostępny pod adresem /preview/resource/R11oyFi2YbPVj
Lekcja poświęcona sortowaniu pozycyjnemu liczb w języku C++.
Kod programu zaprezentowanego w filmie:
Dodaj do swojego programu komentarze tak, żeby był zrozumiały dla osoby, która nie potrafi programować.