Codzienność wymaga skutecznego wyszukiwania i przyswajania informacji. Problemem jednak jest ilość danych, do których mamy dostęp, a także ich niedostateczne uporządkowanie. Jednym z podstawowych sposobów przetwarzania dużej liczby danych jest ich sortowanie. Dane uporządkowane względem jakiejś cechy, np. niemalejąco lub alfabetycznie, są łatwiejsze do przeszukania. W jednym z poprzednich materiałów poznaliśmy już algorytm sortowania przez wybieranie. W tym materiale zajmiemy się metodą porządkowania przez zliczanie.

Zliczanie ocen

Policzymy, ile poszczególnych ocen otrzymał uczeń w trakcie roku szkolnego. Wyniki przedstawimy w postaci listy (liczby wystąpień danej oceny) oraz listy uporządkowanych ocen.

Jak zrealizować takie zadanie przy użyciu kartki i długopisu? Najprostsza metoda polega na przeglądaniu kolejnych ocen i ich zliczaniu. Zliczanie może polegać na stawianiu kresek pod etykietami ocen, ale to wymagało będzie późniejszego ich policzenia. Możemy też zapisywać kolejną liczbę wystąpień danej oceny pod etykietą. Poniżej przykład wykorzystujący ten drugi sposób.

indeksy  = [0, 1, 2, 3, 4, 5, 6]
liczniki = [0, 1, 2, 2, 2, 2, 1]

indeksy  = [0, 1, 2, 3, 4, 5, 6]
liczniki = [0, 1, 3, 2, 2, 2, 1]

indeksy  = [0, 1, 2, 3, 4, 5, 6]
liczniki = [0, 1, 3, 5, 2, 2, 1]

indeksy  = [0, 1, 2, 3, 4, 5, 6]
liczniki = [0, 1, 3, 5, 7, 2, 1]

indeksy  = [0, 1, 2, 3, 4, 5, 6]
liczniki = [0, 1, 3, 5, 7, 9, 1]

indeksy  = [0, 1, 2, 3, 4, 5, 6]
liczniki = [0, 1, 3, 5, 7, 9, 10]

Zliczenie liczników to jednak nie koniec. Konieczne jest posortowanie elementów na podstawie zliczonych liczników.

oceny = [3, 2, 3, 1, 6, 4, 5, 4, 2, 5]
liczniki = [0, 1, 3, 5, 7, 9, 10]
posortowane = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

oceny = [3, 2, 3, 1, 6, 4, 5, 4, 2, 5]
liczniki = [0, 1, 3, 5, 7, 8, 10]
posortowane = [0, 0, 0, 0, 0, 0, 0, 0, 5, 0]

oceny = [3, 2, 3, 1, 6, 4, 5, 4, 2, 5]
liczniki = [0, 1, 2, 5, 7, 8, 10]
posortowane = [0, 0, 2, 0, 0, 0, 0, 0, 5, 0]

Algorytm porządkowania metodą przez zliczanie

Napiszemy program, który uporządkuje w sposób niemalejący listę ocen z wykorzystaniem algorytmu porządkowania metodą przez zliczanie.

Algorytm porządkowania metodą przez zliczanie nadaje się do sortowania liczb całkowitych z dowolnego przedziału, w tym materiale podajemy specyfikację oraz implementację, zakładając, że porządkujemy liczby naturalne większe od 0.

Specyfikacja algorytmu:

Dane wejściowe:

• oceny – lista ocen z zakresu <1;6>

• n – dodatnia liczba naturalna, liczba ocen

Wynik:

• liczniki – lista zawierająca liczby wystąpień poszczególnych ocen

• posortowane – lista uporządkowanych niemalejąco ocen

Zmienne pomocnicze:

• ocena – liczba naturalna z zakresu <1;6> – kolejne oceny z listy

• liczba_licznikow – liczba naturalna, liczba liczników

• i – liczba naturalna, indeks elementów listy

Zapiszemy algorytm w postaci listy kroków.

1. Do liczba_licznikow przypisz wartość max(oceny) + 1.

2. Utwórz listę liczniki zawierającą liczba_licznikow wartości 0.

3. Dla każdego elementu ocena listy oceny wykonaj:

   3.1. Zwiększ wartość liczniki[ocena] o 1.

4. Wypisz listę liczniki.

5. Dla elementów listy liczniki o indeksach i od 1 do liczba_licznikow - 1 wykonaj:

   5.1. Zwiększ wartość liczniki[i] o wartość liczniki[i - 1].

6. Utwórz listę posortowane zawierającą n wartości 0.

7. Dla elementów listy oceny o indeksach i od n - 1 do 0 wykonaj:

   7.1. Zmiennej ocena przypisz wartość oceny[i].

   7.2. Zmiennej licznik przypisz wartość liczniki[ocena].

   7.3. Zmiennej posortowane[licznik - 1] przypisz wartość ocena.

   7.4. Zmniejsz wartość liczniki[ocena] o 1.

8. Wypisz listę posortowane.

W algorytmie można wyróżnić kilka operacji:

1. Zliczanie – indeksy elementów listy liczniki odpowiadają zliczanym wartościom, w tym wypadku ocenom. Np. w elemencie liczniki[1] będą zliczane oceny 1. Indeks ostatniego elementu musi być więc równy maksymalnej zliczanej wartości – max(oceny), a liczba elementów listy liczniki musi być większa o 1, ponieważ pierwszy element listy ma indeks 0. Dodatkowo początkowe wartości liczników muszą równać się 0. Z każdym wystąpieniem danej oceny, odpowiedni indeks listy liczniki będzie zwiększany o 1.

2. Sumowanie – po zliczeniu sumujemy wartości licznika i licznika go poprzedzającego, zaczynając od licznika o indeksie 1, wynik zastępuje dotychczasową wartość licznika.

3. Porządkowanie – odczytujemy z listy oceny zaczynając od ostatniej, z listy liczników odczytujemy wartość indeksu wskazaną przez ocenę, ocenę wstawiamy do listy posortowane pod odczytanym indeksem pomniejszonym o jeden, indeks w liście liczników pomniejszamy o 1 i przechodzimy do kolejnej oceny.

Implementacja programu

Napiszemy teraz program, który zrealizuje opisany algorytm.

Zaczniemy od kodu, w którym podamy listę ocen i ich liczbę.

oceny = [3, 2, 3, 1, 6, 4, 5, 4, 2, 5]
n = 10
print("Oceny:", oceny)

n = len(oceny)

Zliczanie ocen

Do zliczania użyjemy listy, której indeksy odpowiadają zliczanym wartościom. Każdy element listy – licznik – zainicjujemy wartością 0. Zadanie takie realizuje się zazwyczaj w pętli. W języku Python możliwe jest również użycie następującej instrukcji:

lista = [wartość] * liczba

gdzie [wartość] oznacza pojedynczy element powielony w liście, a liczba określa, ile razy element [wartość] zostanie umieszczony na liście.

liczby = [9, 4, 8, 4, 5]
liczniki = [0] * (max(liczby) + 1)
liczniki
len(liczniki)
liczniki[4] += 1
liczniki[4] += 1
liczniki

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
10
[0, 0, 0, 0, 2, 0, 0, 0, 0, 0]

Długość listy liczniki zależy od maksymalnej zliczanej wartości. Powyżej użyliśmy wbudowanej instrukcji max(), ale w implementacji użyjemy następującej funkcji:

def znajdz_maks(lista):
    maks_e = lista[0]
    for i in range(1, n):
        if lista[i] > maks_e:
            maks_e = lista[i]
    return maks_e

def znajdz_maks(lista):
    maks_e = lista[0]
    for i in range(1, n):
        if lista[i] > maks_e:
            maks_e = lista[i]
    return maks_e

oceny = [3, 2, 3, 1, 6, 4, 5, 4, 2, 5]
n = 10
print("Oceny:", oceny)

# przygotowanie listy liczników
liczba_licznikow = znajdz_maks(oceny) + 1
liczniki = liczba_licznikow * [0]
print ("Lista liczniki po zainicjowaniu:", liczniki)

# zliczanie ocen
for ocena in oceny:
    liczniki[ocena] += 1  # inkrementacja o 1
print("Liczniki – lista zawierająca liczby wystąpień poszczególnych ocen:", liczniki)

Następną operacją jest zaktualizowanie listy liczniki według zasady, że wartość licznika zastępowana jest jego wartością powiększoną o wartość licznika poprzedniego. W pętli for za pomocą funkcji range() generujemy indeksy od 1 do liczba_licznikow - 1, tj. 6. Wewnątrz pętli zwiększamy wartości liczników.

# sumowanie liczników
for i in range(1, liczba_licznikow):
    liczniki[i] = liczniki[i] + liczniki[i - 1]
print("Zawartość listy liczniki po zsumowaniu liczby wystąpień wcześniejszych ocen:", liczniki)

Porządkowanie ocen

Rozpoczynamy od przygotowania listy dla posortowanych ocen, której elementy inicjujemy wartością 0. Listę nazwiemy posortowane. Wykorzystujemy podobny kod, jak w przypadku listy liczniki. Do programu dopisujemy:

# lista dla posortowanych ocen
posortowane = n * [0]

Następnie w pętli for przeglądamy listę oceny zaczynając od końca. Instrukcja range(n - 1, -1, -1) zwraca liczby od wartości n - 1, czyli indeksu ostatniego elementu listy ocen, do wartości 0 – indeksu pierwszej oceny, z krokiem -1.

Do programu dopisujemy:

# sortowanie ocen
for i in range(n-1, -1, -1):
    ocena = oceny[i]

W kolejnym kroku za pomocą zmiennej pomocniczejzmienna pomocniczazmiennej pomocniczej ocena odczytujemy licznik, tj liczbę wystąpień tej oceny w liście oceny: licznik = liczniki[ocena]. Wartość licznika pomniejszona o jeden jest indeksem, pod którym umieszczamy ocenę w liście posortowanych ocen: posortowane[licznik - 1] = ocena. Na koniec dekrementujemydekrementacjadekrementujemy wartość licznika: liczniki[ocena] -= 1, aby można było wyznaczyć pozycję, na której należy umieścić kolejną taką samą ocenę.

Kod realizujący opisane operacje dopisujemy do instrukcji wykonywanych w omawianej pętli for. Po wykonaniu pętli wypisujemy listę posortowanych ocen:

# sortowanie ocen
for i in range(n - 1, -1, -1):
    ocena = oceny[i]
    licznik = liczniki[ocena]
    posortowane[licznik - 1] = ocena
    liczniki[ocena] -= 1

print("Posortowane:", posortowane)

Pełny kod programu:

def znajdz_maks(lista):
    maks_e = lista[0]
    for i in range(1, n):
        if lista[i] > maks_e:
            maks_e = lista[i]
    return maks_e

oceny = [3, 2, 3, 1, 6, 4, 5, 4, 2, 5]
n = 10
print("Oceny:", oceny)

# przygotowanie listy liczników
liczba_licznikow = znajdz_maks(oceny) + 1
liczniki = liczba_licznikow * [0]
print ("Lista liczniki po zainicjowaniu:", liczniki)

# zliczanie ocen
for ocena in oceny:
    liczniki[ocena] += 1  # inkrementacja o 1
print("Liczniki – lista zawierająca liczby wystąpień poszczególnych ocen:", liczniki)

# sumowanie liczników
for i in range(1, liczba_licznikow):
    liczniki[i] = liczniki[i] + liczniki[i - 1]
print("Zawartość listy liczniki po zsumowaniu liczby wystąpień wcześniejszych ocen:", liczniki)
# lista dla posortowanych ocen
posortowane = n * [0]

# sortowanie ocen
for i in range(n-1, -1, -1):
    ocena = oceny[i]
    licznik = liczniki[ocena]
    posortowane[licznik - 1] = ocena
    liczniki[ocena] -= 1

print("Posortowane:", posortowane)

Oceny: [3, 2, 3, 1, 6, 4, 5, 4, 2, 5]
Lista liczniki po zainicjowaniu: [0, 0, 0, 0, 0, 0, 0]
Liczniki: [0, 1, 2, 2, 2, 2, 1]
Zawartość listy liczniki po zsumowaniu liczby wystąpień wcześniejszych ocen: [0, 1, 3, 5, 7, 9, 10]
Posortowane: [1, 2, 2, 3, 3, 4, 4, 5, 5, 6]

[(3, 1), (2, 2), (3, 3), (1, 4), (2, 5)]

[(1, 4), (2, 2), (2, 5), (3, 1), (3, 3)]

Notatnik

Gra edukacyjna

[0,0,0,3,0,1,0,2,0,2]

Zestaw ćwiczeń interaktywnych

Słownik