Film samouczek
Sortowanie pozycyjne liczb
Algorytm pozycyjnego sortowania liczb polega na wielokrotnym sortowaniu danych liczb ze względu na wartości cyfr na kolejnych pozycjach. Zaczynamy od cyfry jedności, potem porównujemy setki, tysiące itd. Po uwzględnieniu wszystkich cyfr, algorytm się kończy. Do częściowych sortowań wykorzystujemy stabilny algorytm sortowania. Nie może on zmieniać kolejności liczb o tej samej wartości. Przykłady takich algorytmów to np. sortowanie bąbelkowesortowanie bąbelkowe i sortowanie przez zliczaniesortowanie przez zliczanie.
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, wykorzystując sortowanie pozycyjne liczb (radix sort). Wykorzystaj pomocniczo sortowanie przez zliczanie. Swój program przetestuj dla tablicy z wynikami ankiety w postaci liczby punktów procentowych.
Specyfikacja:
Dane:
dane– jednowymiarowa tablica liczb naturalnych; dane do posortowanialiczbaElementow– liczba naturalna; rozmiar tablicydaneliczbaCyfr– liczba naturalna; maksymalna liczba cyfr w reprezentacji liczbowej wyników ankiety
Wynik:
dane– jednowymiarowa tablica posortowana niemalejąco
Porównaj swoje rozwiązanie z przedstawionym w filmie.
Film dostępny pod adresem /preview/resource/R1eyUpwKEILDx
Film nawiązujący do treści materiału: Algorytm i realizacja Sortowania pozycyjnego liczb w języku Java.
Kod programu zaprezentowanego w filmie:
Dodaj do swojego programu komentarze tak, żeby był zrozumiały dla osoby, która nie potrafi programować.