Przeczytaj

Sortowanie przez zliczanie

Zapiszemy w języku Python algorytm sortowania liczb całkowitych za pomocą algorytmu sortowania przez zliczanie.

Specyfikacja problemu:

Dane:

lista_wejsciowa – zbiór elementów do posortowania; lista liczb całkowitych

Wynik:

lista_wynikowa – posortowana niemalejąco lista liczb całkowitych

Wyszukiwanie największego i najmniejszego elementu zapiszemy w funkcji znajdz_min_max().

def znajdz_min_max(lista_wejsciowa):
    minimum = lista_wejsciowa[0]
    maksimum = lista_wejsciowa[0]
    
    for i in range(1, len(lista_wejsciowa)):
        if lista_wejsciowa[i] < minimum:
            minimum = lista_wejsciowa[i]
        if lista_wejsciowa[i] > maksimum:
            maksimum = lista_wejsciowa[i]
    
    return minimum, maksimum

Po wyszukaniu najmniejszego i największego elementu należy zliczyć elementy.

Wykorzystamy do tego funkcję zlicz(). Realizację tego kroku zaczniemy od weryfikacji, ile różnych elementów mamy do zliczenia. W tym celu odejmujemy od elementu największego element najmniejszy i dodajemy 1 (listy w języku Python indeksujemy od 0).

Przykład 1

Wiemy już, że dla listy lista_wejsciowa = [1, -5, -6, 4, 5, 2] elementem największym jest 5, a najmniejszym: -6. Możemy policzyć, że lista zliczeń będzie składać się z 5 - (-6) + 1 = 12 elementów.

Na podstawie uzyskanego wyniku zerujemy listę lista_zliczajaca.

def znajdz_min_max(lista_wejsciowa):
    minimum = lista_wejsciowa[0]
    maksimum = lista_wejsciowa[0]
    
    for i in range(1, len(lista_wejsciowa)):
        if lista_wejsciowa[i] < minimum:
            minimum = lista_wejsciowa[i]
        if lista_wejsciowa[i] > maksimum:
            maksimum = lista_wejsciowa[i]
    
    return minimum, maksimum

def zlicz(minimum, maksimum, lista_wejsciowa):
    lista_zliczajaca = [0] * (maksimum - minimum + 1)

Następnie zliczamy elementy. W tym celu iterujemy po wszystkich elementach listy lista_wejsciowa. Wyznaczamy indeks komórki w liście lista_zliczajaca, której wartość będziemy inkrementować. Odejmujemy od aktualnie przetwarzanej wartości listy lista_wejsciowa wartość odczytaną ze zmiennej minımum.

Zwracamy listę lista_zliczajaca.

def znajdz_min_max(lista_wejsciowa):
    minimum = lista_wejsciowa[0]
    maksimum = lista_wejsciowa[0]
    
    for i in range(1, len(lista_wejsciowa)):
        if lista_wejsciowa[i] < minimum:
            minimum = lista_wejsciowa[i]
        if lista_wejsciowa[i] > maksimum:
            maksimum = lista_wejsciowa[i]
    
    return minimum, maksimum

def zlicz(minimum, maksimum, lista_wejsciowa):
    lista_zliczajaca = [0] * (maksimum - minimum + 1)
    for i in range(len(lista_wejsciowa)):
        lista_zliczajaca[listaa_wejsciowa[i] - minimum] += 1
    return lista_zliczajaca

Przykład 2

Dla listy lista_wejsciowa = [1, -5, -6, 4, 5, 2] możemy wygenerować następującą listę lista_zliczajaca:

Indeks	Jaki kluczkluczklucz reprezentuje	Zawartość `lista_zliczajaca[indeks]`
0	-6	1
1	-5	1
2	-4	0
3	-3	0
4	-2	0
5	-1	0
6	0	0
7	1	1
8	2	1
9	3	0
10	4	1
11	5	1

Funkcja zlicz_nie_wieksze() modyfikuje listę lista_zliczajaca tak, aby każdy element zawierał liczbę elementów nie większych od niego.

Zaczynając od komórki o indeksie 1, sumujemy kolejne elementy listy lista_zliczajaca, dodając do aktualnie zapisanej wartości zawartość komórki o indeksie o jeden mniejszym. Uzyskujemy w ten sposób pozycję, na której powinien zostać umieszczony ostatni element o wskazanym kluczu.

Linia 1. def znajdz podkreślnik min podkreślnik max otwórz nawias okrągły lista podkreślnik wejsciowa zamknij nawias okrągły dwukropek. Linia 2. minimum znak równości lista podkreślnik wejsciowa otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 3. maksimum znak równości lista podkreślnik wejsciowa otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 5. for i in range otwórz nawias okrągły 1 przecinek len otwórz nawias okrągły lista podkreślnik wejsciowa zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 6. if lista podkreślnik wejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny minimum dwukropek. Linia 7. minimum znak równości lista podkreślnik wejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 8. if lista podkreślnik wejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny maksimum dwukropek. Linia 9. maksimum znak równości lista podkreślnik wejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 11. return minimum przecinek maksimum. Linia 13. def zlicz otwórz nawias okrągły minimum przecinek maksimum przecinek lista podkreślnik wejsciowa zamknij nawias okrągły dwukropek. Linia 14. lista podkreślnik zliczajaca znak równości otwórz nawias kwadratowy 0 zamknij nawias kwadratowy asterysk otwórz nawias okrągły maksimum minus minimum plus 1 zamknij nawias okrągły. Linia 15. for i in range otwórz nawias okrągły len otwórz nawias okrągły lista podkreślnik wejsciowa zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 16. lista podkreślnik zliczajaca otwórz nawias kwadratowy lista podkreślnik wejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy minus minimum zamknij nawias kwadratowy plus znak równości 1. Linia 17. return lista podkreślnik zliczajaca. Linia 19. def zlicz podkreślnik nie podkreślnik wieksze otwórz nawias okrągły lista podkreślnik zliczajaca zamknij nawias okrągły dwukropek. Linia 20. for i in range otwórz nawias okrągły 1 przecinek len otwórz nawias okrągły lista podkreślnik zliczajaca zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 21. lista podkreślnik zliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy plus znak równości lista podkreślnik zliczajaca otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy.

def znajdz_min_max(lista_wejsciowa):
    minimum = lista_wejsciowa[0]
    maksimum = lista_wejsciowa[0]
    
    for i in range(1, len(lista_wejsciowa)):
        if lista_wejsciowa[i] < minimum:
            minimum = lista_wejsciowa[i]
        if lista_wejsciowa[i] > maksimum:
            maksimum = lista_wejsciowa[i]
    
    return minimum, maksimum

def zlicz(minimum, maksimum, lista_wejsciowa):
    lista_zliczajaca = [0] * (maksimum - minimum + 1)
    for i in range(len(lista_wejsciowa)):
        lista_zliczajaca[lista_wejsciowa[i] - minimum] += 1
    return lista_zliczajaca

def zlicz_nie_wieksze(lista_zliczajaca):
    for i in range(1, len(lista_zliczajaca)):
        lista_zliczajaca[i] += lista_zliczajaca[i - 1]

Przykład 3

Po przeprowadzeniu operacji sumowania dla listy lista_wejsciowa = [1, -5, -6, 4, 5, 2], otrzymujemy następującą listę lista_zliczajaca:

Indeks	Jaki klucz reprezentuje	Zawartość `lista_zliczajaca[indeks]`
0	-6	1
1	-5	2
2	-4	2
3	-3	2
4	-2	2
5	-1	2
6	0	2
7	1	3
8	2	4
9	3	4
10	4	5
11	5	6

Zapiszemy funkcję posortuj().

Na początku funkcja wywołuje funkcję znajdz_min_max(), aby znaleźć wartość minimalną i maksymalną w liście wejściowej. Te wartości są potrzebne do stworzenia listy zliczającej.

Następnie funkcja wywołuje funkcję zlicz(), aby stworzyć listę zliczającą o rozmiarze równej liczbie elementów w zakresie wartości w liście wejściowej. Dla każdej wartości w liście wejściowej funkcja zlicza, ile razy ta wartość występuje i zapisuje to w liście zliczającej.

W trzecim kroku funkcja wywołuje funkcję zlicz_nie_wieksze(), która modyfikuje listę zliczającą tak, aby każdy element zawierał liczbę elementów nie większych od niego. Dzięki temu można uzyskać indeksy elementów posortowanej listy wynikowej.

Następnie tworzona jest lista wynikowa o takim samym rozmiarze jak lista wejściowa lista_wejsciowa.

Algorytm sortowania przez zliczanie polega na przeglądaniu listy wejściowej lista_wejsciowa od końca i wstawianiu elementów na odpowiednie miejsca w liście wynikowej lista_wynikowa. Dlatego funkcja posortuj() przegląda listę wejściową w pętli od końca, a następnie dla każdej liczby znajduje jej indeks w liście wynikowej i liście zliczającej, a następnie wpisuje ją na odpowiednie miejsce w liście wynikowej.

Na końcu funkcja zwraca posortowaną listę wynikową.

W tej implementacji zostały zawarte komunikaty przeprowadzające użytkownika przez każdy krok algorytmu.

Kod programu:

Linia 1. lista podkreślnik wejsciowa znak równości otwórz nawias kwadratowy minus 2 przecinek 0 przecinek 3 przecinek 1 przecinek 1 przecinek 3 przecinek 2 zamknij nawias kwadratowy. Linia 3. def znajdz podkreślnik min podkreślnik max otwórz nawias okrągły lista podkreślnik wejsciowa zamknij nawias okrągły dwukropek. Linia 4. minimum znak równości lista podkreślnik wejsciowa otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 5. maksimum znak równości lista podkreślnik wejsciowa otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 7. for i in range otwórz nawias okrągły 1 przecinek len otwórz nawias okrągły lista podkreślnik wejsciowa zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 8. if lista podkreślnik wejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny minimum dwukropek. Linia 9. minimum znak równości lista podkreślnik wejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 10. if lista podkreślnik wejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny maksimum dwukropek. Linia 11. maksimum znak równości lista podkreślnik wejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 13. return minimum przecinek maksimum. Linia 15. def zlicz otwórz nawias okrągły minimum przecinek maksimum przecinek lista podkreślnik wejsciowa zamknij nawias okrągły dwukropek. Linia 16. lista podkreślnik zliczajaca znak równości otwórz nawias kwadratowy 0 zamknij nawias kwadratowy asterysk otwórz nawias okrągły maksimum minus minimum plus 1 zamknij nawias okrągły. Linia 17. for i in range otwórz nawias okrągły len otwórz nawias okrągły lista podkreślnik wejsciowa zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 18. lista podkreślnik zliczajaca otwórz nawias kwadratowy lista podkreślnik wejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy minus minimum zamknij nawias kwadratowy plus znak równości 1. Linia 19. return lista podkreślnik zliczajaca. Linia 21. def zlicz podkreślnik nie podkreślnik wieksze otwórz nawias okrągły lista podkreślnik zliczajaca zamknij nawias okrągły dwukropek. Linia 22. for i in range otwórz nawias okrągły 1 przecinek len otwórz nawias okrągły lista podkreślnik zliczajaca zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 23. lista podkreślnik zliczajaca otwórz nawias kwadratowy i zamknij nawias kwadratowy plus znak równości lista podkreślnik zliczajaca otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy. Linia 25. def posortuj otwórz nawias okrągły lista podkreślnik wejsciowa zamknij nawias okrągły dwukropek. Linia 26. minimum przecinek maksimum znak równości znajdz podkreślnik min podkreślnik max otwórz nawias okrągły lista podkreślnik wejsciowa zamknij nawias okrągły. Linia 27. lista podkreślnik zliczajaca znak równości zlicz otwórz nawias okrągły minimum przecinek maksimum przecinek lista podkreślnik wejsciowa zamknij nawias okrągły. Linia 28. zlicz podkreślnik nie podkreślnik wieksze otwórz nawias okrągły lista podkreślnik zliczajaca zamknij nawias okrągły. Linia 29. lista podkreślnik wynikowa znak równości otwórz nawias kwadratowy 0 zamknij nawias kwadratowy asterysk len otwórz nawias okrągły lista podkreślnik wejsciowa zamknij nawias okrągły. Linia 30. for i in range otwórz nawias okrągły len otwórz nawias okrągły lista podkreślnik wejsciowa zamknij nawias okrągły minus 1 przecinek minus 1 przecinek minus 1 zamknij nawias okrągły dwukropek. Linia 31. print otwórz nawias okrągły cudzysłów Badana liczba dwukropek cudzysłów przecinek lista podkreślnik wejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły. Linia 32. print otwórz nawias okrągły cudzysłów lista podkreślnik wynikowa przed wykonaniem kroku dwukropek cudzysłów przecinek lista podkreślnik wynikowa zamknij nawias okrągły. Linia 33. print otwórz nawias okrągły cudzysłów lista podkreślnik zliczajaca przed wykonaniem kroku dwukropek cudzysłów przecinek lista podkreślnik zliczajaca zamknij nawias okrągły. Linia 34. print otwórz nawias okrągły cudzysłów Wykonanie algorytmu kropka cudzysłów zamknij nawias okrągły. Linia 35. indeks podkreślnik lista podkreślnik zliczajaca znak równości lista podkreślnik wejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy minus minimum. Linia 36. indeks podkreślnik lista podkreślnik wynikowa znak równości lista podkreślnik zliczajaca otwórz nawias kwadratowy indeks podkreślnik lista podkreślnik zliczajaca zamknij nawias kwadratowy minus 1. Linia 37. lista podkreślnik wynikowa otwórz nawias kwadratowy indeks podkreślnik lista podkreślnik wynikowa zamknij nawias kwadratowy znak równości lista podkreślnik wejsciowa otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 38. lista podkreślnik zliczajaca otwórz nawias kwadratowy indeks podkreślnik lista podkreślnik zliczajaca zamknij nawias kwadratowy minus znak równości 1. Linia 39. print otwórz nawias okrągły cudzysłów lista podkreślnik wynikowa po wykonaniu kroku dwukropek cudzysłów przecinek lista podkreślnik wynikowa zamknij nawias okrągły. Linia 40. print otwórz nawias okrągły cudzysłów lista podkreślnik zliczajaca po wykonaniu kroku dwukropek cudzysłów przecinek lista podkreślnik zliczajaca zamknij nawias okrągły. Linia 41. print otwórz nawias okrągły zamknij nawias okrągły. Linia 42. return lista podkreślnik wynikowa. Linia 44. lista podkreślnik wynikowa znak równości posortuj otwórz nawias okrągły lista podkreślnik wejsciowa zamknij nawias okrągły. Linia 46. print otwórz nawias okrągły cudzysłów Po wykonaniu algorytmu lista podkreślnik wynikowa wyglada nastepujaco dwukropek cudzysłów zamknij nawias okrągły. Linia 47. print otwórz nawias okrągły lista podkreślnik wynikowa zamknij nawias okrągły.

lista_wejsciowa = [-2, 0, 3, 1, 1, 3, 2]

def znajdz_min_max(lista_wejsciowa):
    minimum = lista_wejsciowa[0]
    maksimum = lista_wejsciowa[0]
    
    for i in range(1, len(lista_wejsciowa)):
        if lista_wejsciowa[i] < minimum:
            minimum = lista_wejsciowa[i]
        if lista_wejsciowa[i] > maksimum:
            maksimum = lista_wejsciowa[i]
    
    return minimum, maksimum

def zlicz(minimum, maksimum, lista_wejsciowa):
    lista_zliczajaca = [0] * (maksimum - minimum + 1)
    for i in range(len(lista_wejsciowa)):
        lista_zliczajaca[lista_wejsciowa[i] - minimum] += 1
    return lista_zliczajaca

def zlicz_nie_wieksze(lista_zliczajaca):
    for i in range(1, len(lista_zliczajaca)):
        lista_zliczajaca[i] += lista_zliczajaca[i - 1]

def posortuj(lista_wejsciowa):
    minimum, maksimum = znajdz_min_max(lista_wejsciowa)
    lista_zliczajaca = zlicz(minimum, maksimum, lista_wejsciowa)
    zlicz_nie_wieksze(lista_zliczajaca)
    lista_wynikowa = [0] * len(lista_wejsciowa)
    for i in range(len(lista_wejsciowa) - 1, -1, -1):
        print("Badana liczba:", lista_wejsciowa[i])
        print("lista_wynikowa przed wykonaniem kroku:", lista_wynikowa)
        print("lista_zliczajaca przed wykonaniem kroku:", lista_zliczajaca)
        print("Wykonanie algorytmu.")
        indeks_lista_zliczajaca = lista_wejsciowa[i] - minimum
        indeks_lista_wynikowa = lista_zliczajaca[indeks_lista_zliczajaca] - 1
        lista_wynikowa[indeks_lista_wynikowa] = lista_wejsciowa[i]
        lista_zliczajaca[indeks_lista_zliczajaca] -= 1
        print("lista_wynikowa po wykonaniu kroku:", lista_wynikowa)
        print("lista_zliczajaca po wykonaniu kroku:", lista_zliczajaca)
        print()
    return lista_wynikowa

lista_wynikowa = posortuj(lista_wejsciowa)

print("Po wykonaniu algorytmu lista_wynikowa wyglada nastepujaco:")
print(lista_wynikowa)

Wynik wykonywania kodu będzie następujący:

Linia 1. Badana liczba dwukropek 2. Linia 2. lista podkreślnik wynikowa przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 3. lista podkreślnik zliczajaca przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 4 przecinek 5 przecinek 7 zamknij nawias kwadratowy. Linia 4. Wykonanie algorytmu kropka. Linia 5. lista podkreślnik wynikowa po wykonaniu kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 2 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 6. lista podkreślnik zliczajaca po wykonaniu kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 4 przecinek 4 przecinek 7 zamknij nawias kwadratowy. Linia 8. Badana liczba dwukropek 3. Linia 9. lista podkreślnik wynikowa przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 2 przecinek 0 przecinek 0 zamknij nawias kwadratowy. Linia 10. lista podkreślnik zliczajaca przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 4 przecinek 4 przecinek 7 zamknij nawias kwadratowy. Linia 11. Wykonanie algorytmu kropka. Linia 12. lista podkreślnik wynikowa po wykonaniu kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 2 przecinek 0 przecinek 3 zamknij nawias kwadratowy. Linia 13. lista podkreślnik zliczajaca po wykonaniu kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 4 przecinek 4 przecinek 6 zamknij nawias kwadratowy. Linia 15. Badana liczba dwukropek 1. Linia 16. lista podkreślnik wynikowa przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 0 przecinek 2 przecinek 0 przecinek 3 zamknij nawias kwadratowy. Linia 17. lista podkreślnik zliczajaca przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 4 przecinek 4 przecinek 6 zamknij nawias kwadratowy. Linia 18. Wykonanie algorytmu kropka. Linia 19. lista podkreślnik wynikowa po wykonaniu kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 1 przecinek 2 przecinek 0 przecinek 3 zamknij nawias kwadratowy. Linia 20. lista podkreślnik zliczajaca po wykonaniu kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 3 przecinek 4 przecinek 6 zamknij nawias kwadratowy. Linia 22. Badana liczba dwukropek 1. Linia 23. lista podkreślnik wynikowa przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 0 przecinek 1 przecinek 2 przecinek 0 przecinek 3 zamknij nawias kwadratowy. Linia 24. lista podkreślnik zliczajaca przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 3 przecinek 4 przecinek 6 zamknij nawias kwadratowy. Linia 25. Wykonanie algorytmu kropka. Linia 26. lista podkreślnik wynikowa po wykonaniu kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 2 przecinek 0 przecinek 3 zamknij nawias kwadratowy. Linia 27. lista podkreślnik zliczajaca po wykonaniu kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 2 przecinek 4 przecinek 6 zamknij nawias kwadratowy. Linia 29. Badana liczba dwukropek 3. Linia 30. lista podkreślnik wynikowa przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 2 przecinek 0 przecinek 3 zamknij nawias kwadratowy. Linia 31. lista podkreślnik zliczajaca przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 2 przecinek 4 przecinek 6 zamknij nawias kwadratowy. Linia 32. Wykonanie algorytmu kropka. Linia 33. lista podkreślnik wynikowa po wykonaniu kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 2 przecinek 3 przecinek 3 zamknij nawias kwadratowy. Linia 34. lista podkreślnik zliczajaca po wykonaniu kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 2 przecinek 4 przecinek 5 zamknij nawias kwadratowy. Linia 36. Badana liczba dwukropek 0. Linia 37. lista podkreślnik wynikowa przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 2 przecinek 3 przecinek 3 zamknij nawias kwadratowy. Linia 38. lista podkreślnik zliczajaca przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 2 przecinek 2 przecinek 4 przecinek 5 zamknij nawias kwadratowy. Linia 39. Wykonanie algorytmu kropka. Linia 40. lista podkreślnik wynikowa po wykonaniu kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 2 przecinek 3 przecinek 3 zamknij nawias kwadratowy. Linia 41. lista podkreślnik zliczajaca po wykonaniu kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 1 przecinek 2 przecinek 4 przecinek 5 zamknij nawias kwadratowy. Linia 43. Badana liczba dwukropek minus 2. Linia 44. lista podkreślnik wynikowa przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 0 przecinek 0 przecinek 1 przecinek 1 przecinek 2 przecinek 3 przecinek 3 zamknij nawias kwadratowy. Linia 45. lista podkreślnik zliczajaca przed wykonaniem kroku dwukropek otwórz nawias kwadratowy 1 przecinek 1 przecinek 1 przecinek 2 przecinek 4 przecinek 5 zamknij nawias kwadratowy. Linia 46. Wykonanie algorytmu kropka. Linia 47. lista podkreślnik wynikowa po wykonaniu kroku dwukropek otwórz nawias kwadratowy minus 2 przecinek 0 przecinek 1 przecinek 1 przecinek 2 przecinek 3 przecinek 3 zamknij nawias kwadratowy. Linia 48. lista podkreślnik zliczajaca po wykonaniu kroku dwukropek otwórz nawias kwadratowy 0 przecinek 1 przecinek 1 przecinek 2 przecinek 4 przecinek 5 zamknij nawias kwadratowy. Linia 50. Po wykonaniu algorytmu lista podkreślnik wynikowa wyglada nastepujaco dwukropek. Linia 51. otwórz nawias kwadratowy minus 2 przecinek 0 przecinek 1 przecinek 1 przecinek 2 przecinek 3 przecinek 3 zamknij nawias kwadratowy.

Badana liczba: 2
lista_wynikowa przed wykonaniem kroku: [0, 0, 0, 0, 0, 0, 0]
lista_zliczajaca przed wykonaniem kroku: [1, 1, 2, 4, 5, 7]
Wykonanie algorytmu.
lista_wynikowa po wykonaniu kroku: [0, 0, 0, 0, 2, 0, 0]
lista_zliczajaca po wykonaniu kroku: [1, 1, 2, 4, 4, 7]

Badana liczba: 3
lista_wynikowa przed wykonaniem kroku: [0, 0, 0, 0, 2, 0, 0]
lista_zliczajaca przed wykonaniem kroku: [1, 1, 2, 4, 4, 7]
Wykonanie algorytmu.
lista_wynikowa po wykonaniu kroku: [0, 0, 0, 0, 2, 0, 3]
lista_zliczajaca po wykonaniu kroku: [1, 1, 2, 4, 4, 6]

Badana liczba: 1
lista_wynikowa przed wykonaniem kroku: [0, 0, 0, 0, 2, 0, 3]
lista_zliczajaca przed wykonaniem kroku: [1, 1, 2, 4, 4, 6]
Wykonanie algorytmu.
lista_wynikowa po wykonaniu kroku: [0, 0, 0, 1, 2, 0, 3]
lista_zliczajaca po wykonaniu kroku: [1, 1, 2, 3, 4, 6]

Badana liczba: 1
lista_wynikowa przed wykonaniem kroku: [0, 0, 0, 1, 2, 0, 3]
lista_zliczajaca przed wykonaniem kroku: [1, 1, 2, 3, 4, 6]
Wykonanie algorytmu.
lista_wynikowa po wykonaniu kroku: [0, 0, 1, 1, 2, 0, 3]
lista_zliczajaca po wykonaniu kroku: [1, 1, 2, 2, 4, 6]

Badana liczba: 3
lista_wynikowa przed wykonaniem kroku: [0, 0, 1, 1, 2, 0, 3]
lista_zliczajaca przed wykonaniem kroku: [1, 1, 2, 2, 4, 6]
Wykonanie algorytmu.
lista_wynikowa po wykonaniu kroku: [0, 0, 1, 1, 2, 3, 3]
lista_zliczajaca po wykonaniu kroku: [1, 1, 2, 2, 4, 5]

Badana liczba: 0
lista_wynikowa przed wykonaniem kroku: [0, 0, 1, 1, 2, 3, 3]
lista_zliczajaca przed wykonaniem kroku: [1, 1, 2, 2, 4, 5]
Wykonanie algorytmu.
lista_wynikowa po wykonaniu kroku: [0, 0, 1, 1, 2, 3, 3]
lista_zliczajaca po wykonaniu kroku: [1, 1, 1, 2, 4, 5]

Badana liczba: -2
lista_wynikowa przed wykonaniem kroku: [0, 0, 1, 1, 2, 3, 3]
lista_zliczajaca przed wykonaniem kroku: [1, 1, 1, 2, 4, 5]
Wykonanie algorytmu.
lista_wynikowa po wykonaniu kroku: [-2, 0, 1, 1, 2, 3, 3]
lista_zliczajaca po wykonaniu kroku: [0, 1, 1, 2, 4, 5]

Po wykonaniu algorytmu lista_wynikowa wyglada nastepujaco:
[-2, 0, 1, 1, 2, 3, 3]

Słownik

klucz

w kontekście sortowania przez zliczanie może być rozumiany jako coś jednoznacznie identyfikującego obiekt; przykładem klucza jest wartość lub słowo

sortowanie stabilne

rodzaj sortowania gwarantujący umieszczenie w tablicy (liście) wynikowej elementów o tej samej wartości, względem siebie, w takiej samej kolejności jak w tablicy (liście) wejściowej

sortowanie niestabilne

sortowanie niezachowujące kolejności występowania elementów w tablicy (liście) o tej samej wartości w posortowanej tablicy (liście) wynikowej

Wprowadzenie

Prezentacja multimedialna

Sortowanie przez zliczanie

Słownik