Przeczytaj

Polecenie 1

Zapoznaj się z animacją przedstawiającą sortowanie kubełkowe.

Rcz1Xt1KeUHUU

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Polecenie 2

Prześledź działanie algorytmu w praktyce. W tym celu przygotuj zestaw przedmiotów do posortowania. Mogą to być żetony, korki, kapsle czy inne małe przedmioty, mające charakterystyczną cechę, według której można je posortować.

Następnie ułóż je w losowej kolejności w jednej linii. Powstanie w ten sposób zbiór, który posortujesz.

Wszystkie ułożone w linii przedmioty pogrupuj w zbiory. Elementy można zidentyfikować poprzez ich charakterystyczną cechę. W przykładzie przedstawionym w animacji był to rodzaj przyboru szkolnego. W twoim przypadku może być to kolor, rozmiar czy inne dowolne kryterium.

Następnie wybierz zbiór i zacznij układać jego elementy, jeden po drugim, w linii. Gdy dany zbiór się skończy, wybierz następny i powtarzaj proces. Przedłużaj układaną linię aż do momentu, gdy skończą się wszystkie zbiory.

Sortowanie kubełkowe

Algorytm sortowania kubełkowego polega na zliczeniu wystąpień danych wartości w liście wejściowej, a następnie na wygenerowaniu listy wyjściowej, zawierającej dane w odpowiednich kubełkachkubełekkubełkach, posortowane zgodnie z ich liczbą.

Sortowanie liczb całkowitych

Specyfikacja problemu:

Dane:

liczby – nieposortowana lista liczb całkowitych zawierająca dane do posortowania

Wynik:

posortowane_elem – posortowana niemalejąco lista liczb całkowitych

Zaczynamy od odnalezienia najmniejszej i największej liczby należącej do listy wejściowej.

Ważne!

Aby odnaleźć odpowiednie wartości, możemy skorzystać z wbudowanych funkcji min() oraz max().

# znajdowanie wartości minimalnej i maksymalnej
min_elem = min(liczby)
max_elem = max(liczby)

W tym e‑materiale wykorzystamy jednak implementację zaprezentowaną w e‑materiale Sortowanie kubełkowePPpmzST7zSortowanie kubełkowe.

n = len(liczby)
min_elem = liczby[0]
max_elem = liczby[0]
for i in range(1, n):
	if liczby[i] < min_elem:
		min_elem = liczby[i]
	if liczby[i] > max_elem:
		max_elem = liczby[i]

Tworzy listę zliczającą kubelek o długości max_elem - min_elem + 1, tak by każda liczba z przedziału <min_elem, max_elem> miała swój indeksindeks listyindeks, a więc kubełek. Lista służy do zliczania, ile razy każda liczba wystąpi w przedziale <min_elem, max_elem>.

Zerujemy tę listę, żeby mieć pewność co do poprawności wykonania kodu.

# przygotowanie listy zliczającej
k = max_elem - min_elem + 1
kubelek = [0] * k

Iterujemy po wszystkich elementach z listy liczby i zwiększamy o jeden wartość dla odpowiedniego indeksu w liście zliczającej kubelek. Indeks jest obliczany jako różnica między wartością liczby a minimalną liczbą.

# zliczanie wartości
for elem in liczby:
    kubelek[elem - min_elem] += 1

Następnie iterujemy po wszystkich indeksach w liście zliczającej i tworzymy nową listę: posortowane_elem, dodając liczbę odpowiadającą temu indeksowi tyle razy, ile jest zliczona w liście zliczającej.

Na koniec program zwraca posortowaną listę posortowane_elem.

# porządkowanie
posortowane_elem = []
for i in range(k):
    while kubelek[i] > 0:
        posortowane_elem.append(i + min_elem)
        kubelek[i] -= 1
return posortowane_elem

Kompletny kod programu:

Linia 1. def sort podkreślnik kubelk otwórz nawias okrągły liczby zamknij nawias okrągły dwukropek. Linia 2. kratka znajdowanie wartości minimalnej i maksymalnej. Linia 3. n znak równości len otwórz nawias okrągły liczby zamknij nawias okrągły. Linia 4. min podkreślnik elem znak równości liczby otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 5. max podkreślnik elem znak równości liczby otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 6. for i in range otwórz nawias okrągły 1 przecinek n zamknij nawias okrągły dwukropek. Linia 7. if liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny min podkreślnik elem dwukropek. Linia 8. min podkreślnik elem znak równości liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 9. if liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny max podkreślnik elem dwukropek. Linia 10. max podkreślnik elem znak równości liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 11. kratka przygotowanie listy zliczającej. Linia 12. k znak równości max podkreślnik elem minus min podkreślnik elem plus 1. Linia 13. kubelek znak równości otwórz nawias kwadratowy 0 zamknij nawias kwadratowy asterysk k. Linia 14. kratka zliczanie wartości. Linia 15. for elem in liczby dwukropek. Linia 16. kubelek otwórz nawias kwadratowy elem minus min podkreślnik elem zamknij nawias kwadratowy plus znak równości 1. Linia 17. kratka porządkowanie. Linia 18. posortowane podkreślnik elem znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 19. for i in range otwórz nawias okrągły k zamknij nawias okrągły dwukropek. Linia 20. while kubelek otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny 0 dwukropek. Linia 21. posortowane podkreślnik elem kropka append otwórz nawias okrągły i plus min podkreślnik elem zamknij nawias okrągły. Linia 22. kubelek otwórz nawias kwadratowy i zamknij nawias kwadratowy minus znak równości 1. Linia 23. return posortowane podkreślnik elem. Linia 25. liczby znak równości otwórz nawias kwadratowy 3 przecinek 2 przecinek 3 przecinek 4 przecinek minus 4 przecinek 2 przecinek 3 przecinek 2 przecinek 0 przecinek minus 5 zamknij nawias kwadratowy. Linia 26. print otwórz nawias okrągły sort podkreślnik kubelk otwórz nawias okrągły liczby zamknij nawias okrągły zamknij nawias okrągły. Linia 28. kratka posortowana lista. Linia 29. kratka otwórz nawias kwadratowy minus 5 przecinek minus 4 przecinek 0 przecinek 2 przecinek 2 przecinek 2 przecinek 3 przecinek 3 przecinek 3 przecinek 4 zamknij nawias kwadratowy.

def sort_kubelk(liczby):
    # znajdowanie wartości minimalnej i maksymalnej
    n = len(liczby)
    min_elem = liczby[0]
    max_elem = liczby[0]
    for i in range(1, n):
        if liczby[i] < min_elem:
            min_elem = liczby[i]
        if liczby[i] > max_elem:
            max_elem = liczby[i]
    # przygotowanie listy zliczającej
    k = max_elem - min_elem + 1
    kubelek = [0] * k
    # zliczanie wartości
    for elem in liczby:
        kubelek[elem - min_elem] += 1
    # porządkowanie
    posortowane_elem = []
    for i in range(k):
        while kubelek[i] > 0:
            posortowane_elem.append(i + min_elem)
            kubelek[i] -= 1
    return posortowane_elem

liczby = [3, 2, 3, 4, -4, 2, 3, 2, 0, -5]
print(sort_kubelk(liczby))

# posortowana lista
# [-5, -4, 0, 2, 2, 2, 3, 3, 3, 4]

Widzimy, że w wyniku działania algorytmu poszczególne wystąpienia liczb są ułożone w kolejności od najmniejszej do największej.

Ważne!

Aby uporządkować liczby nierosnąco, należy listę liczb odczytywać od końca. Zmieni się więc tylko kod drugiej pętli:

for i in range(k - 1, -1, -1):

Sortowanie kubełkowe jest sortowaniem stabilnym (utrzymuje kolejność występowania elementów o tym samym kluczu); wymaga zadeklarowania dodatkowej pamięci do sortowania.

Sortowanie liczb rzeczywistych

Liczby rzeczywiste również mogą być porządkowane z użyciem algorytmu sortowania kubełkowego. Będzie się on jednak różnił od wersji dla liczb całkowitych.

W przypadku algorytmu dla liczb całkowitych każda liczba ma własny osobny kubełek, który zawiera licznik jej wystąpień. Natomiast podczas sortowania liczb rzeczywistych kubełki są przedziałami, do których trafiają liczby należące do danego zakresu. Przedziały wyznaczamy, dzieląc maksymalny element listy przez liczbę elementów.

W implementacji wykorzystamy taką samą liczbę kubełków (przedziałów), jak w wersji algorytmu dla liczb całkowitych. Wartości, które trafią do danego kubełka, będą się mieścić w przedziałach [x, x + 1) dla liczb nieujemnych i (x - 1, x] dla liczb ujemnych. Liczba 3,7 trafi do kubełka reprezentującego przedział [3; 4), a liczba -4,2 do przedziału (-5; -4]. Możemy wywołać funkcję również z inną liczbą kubełków – wartości w liście zostaną odpowiednio uporządkowane dzięki wyznaczeniu przedziałów w implementacji.

Przeanalizujmy program sortujący niemalejąco liczby zmiennoprzecinkowe metodą kubełkową.

Specyfikacja problemu:

Dane:

n – liczba naturalna; liczba kubełków
liczby – nieposortowana lista nieujemnych liczb rzeczywistych zawierająca dane do posortowania

Wynik:

posortowana niemalejąco lista liczb

Linia 1. def sort podkreślnik kubelk otwórz nawias okrągły liczby przecinek n zamknij nawias okrągły dwukropek. Linia 2. kratka Tworzymy listę kubełków o rozmiarze n. Linia 3. kubelki znak równości otwórz nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy for podkreślnik in range otwórz nawias okrągły n zamknij nawias okrągły zamknij nawias kwadratowy. Linia 4. kratka Przypisujemy liczbę do odpowiedniego kubełka. Linia 5. for elem in liczby dwukropek. Linia 6. kubelek podkreślnik indeks znak równości int otwórz nawias okrągły elem asterysk n zamknij nawias okrągły. Linia 7. kubelki otwórz nawias kwadratowy kubelek podkreślnik indeks zamknij nawias kwadratowy kropka append otwórz nawias okrągły elem zamknij nawias okrągły. Linia 8. kratka Sortujemy każdy kubełek za pomocą sortowania bąbelkowego. Linia 9. for i in range otwórz nawias okrągły 0 przecinek n minus 1 zamknij nawias okrągły dwukropek. Linia 10. for j in range otwórz nawias okrągły 1 przecinek n minus i zamknij nawias okrągły dwukropek. Linia 11. if liczby otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy otwórz nawias ostrokątny liczby otwórz nawias kwadratowy j zamknij nawias kwadratowy dwukropek. Linia 12. liczby otwórz nawias kwadratowy j zamknij nawias kwadratowy przecinek liczby otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy znak równości liczby otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy przecinek liczby otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 13. kratka Inicjalizujemy zmienną do przechowywania wyniku. Linia 14. posortowane podkreślnik liczby znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 15. kratka Przeglądamy kubełki i dodajemy liczby do wyniku. Linia 16. for kubelek in kubelki dwukropek. Linia 17. for elem in kubelek dwukropek. Linia 18. posortowane podkreślnik liczby kropka append otwórz nawias okrągły elem zamknij nawias okrągły. Linia 19. return posortowane podkreślnik liczby. Linia 21. liczby znak równości otwórz nawias kwadratowy 0 kropka 1 przecinek 0 kropka 4 przecinek 0 kropka 2 przecinek 0 kropka 9 przecinek 0 kropka 5 przecinek 0 kropka 8 przecinek 0 kropka 3 przecinek 0 kropka 7 przecinek 0 kropka 6 zamknij nawias kwadratowy. Linia 22. n znak równości len otwórz nawias okrągły liczby zamknij nawias okrągły. Linia 23. print otwórz nawias okrągły sort podkreślnik kubelk otwórz nawias okrągły liczby przecinek n zamknij nawias okrągły zamknij nawias okrągły.

def sort_kubelk(liczby, n):
    # Tworzymy listę kubełków o rozmiarze n
    kubelki = [[] for _ in range(n)]
    # Przypisujemy liczbę do odpowiedniego kubełka
    for elem in liczby:
        kubelek_indeks = int(elem * n)
        kubelki[kubelek_indeks].append(elem)
    # Sortujemy każdy kubełek za pomocą sortowania bąbelkowego
    for i in range(0, n - 1):
        for j in range(1, n - i):
            if liczby[j - 1] < liczby[j]:
                liczby[j], liczby[j - 1] = liczby[j - 1], liczby[j]
    # Inicjalizujemy zmienną do przechowywania wyniku
    posortowane_liczby = []
    # Przeglądamy kubełki i dodajemy liczby do wyniku
    for kubelek in kubelki:
        for elem in kubelek:
            posortowane_liczby.append(elem)
    return posortowane_liczby

liczby = [0.1, 0.4, 0.2, 0.9, 0.5, 0.8, 0.3, 0.7, 0.6]
n = len(liczby)
print(sort_kubelk(liczby, n))

Ważne!

Stworzymy dodatkową funkcję sort_babelkowo(), którą zrealizujemy sortowanie elementów wewnątrz kubełka. Wykorzystamy ją w trakcie działania funkcji sort_kubelk().

def sort_babelkowo(liczby):
    n = len(liczby)
    for i in range(0, n - 1):
        for j in range(1, n - i):
            if liczby[j - 1] > liczby[j]:
                liczby[j], liczby[j - 1] = liczby[j - 1], liczby[j]
    return liczby

Implementujemy funkcję sort_kubelk przyjmującą jako parametry listę liczb zmiennoprzecinkowych liczby oraz liczbę kubełków n.

def sort_kubelk(liczby, n):

Tworzymy listę kubelki o rozmiarze n+1, aby zapobiec błędom IndexError: list assignment index out of range. Służy ona do przechowywania liczb w odpowiednich kubełkach. Używamy standardowego generatora listowego w Pythonie.

# Tworzymy listę kubełków o rozmiarze n+1
kubelki = [[] for _ in range(n+1)]

Dla każdej liczby z wejściowej listy obliczamy indeks kubełka, dzieląc całkowicie dany element listy (elem) przez rozmiar kubełka (size) i zmieniając wynik na liczbę całkowitą.

 # Przypisujemy liczbę do odpowiedniego kubełka
for elem in liczby:
	kubelek_indeks = int(elem // size)
    
# np. int(1.1 // 0.2) = 5

Dodajemy liczbę do odpowiedniego kubełka.

kubelki[kubelek_indeks].append(elem)

W kolejnym kroku sortujemy elementy poszczególnych niepustych kubełków. Elementy wypisujemy w kolejności od najmniejszego do największego. Możemy w tym celu użyć dowolnego stabilnego algorytmu sortującego. W omawianym przykładzie posłużymy się algorytmem sortowania bąbelkowegoPoYAEP8llalgorytmem sortowania bąbelkowego.

Do przypisania uporządkowanej zawartości kubełka użyjemy standardowej funkcji enumerate(), która zwraca dwie wartości: indeks elementu listy i jego wartość. W ten sposób możemy przypisać posortowany kubełek bez konieczności alokowania pamięci dla kolejnej listy kubełków.

for ind, val in enumerate(kubelki):
    kubelki[ind] = sort_babelkowo(val)

Wyjaśnijmy najpierw, w jakim celu dzielimy elementy na kubełki, skoro i tak skorzystamy z innego algorytmu sortowania.

Przeanalizujmy sytuację, w której mamy 100 kubełków – w każdym z nich znajduje się 10 elementów, co oznacza, że mamy w sumie 1000 elementów do posortowania.

Gdybyśmy do posortowania tych elementów zastosowali jedynie sortowanie bąbelkowe, algorytm miałby złożoność czasowązłożoność czasowazłożoność czasową rzędu $n^{2}$ , czyli $1000^{2}$ , co jest równe $1 000 000$ .

W rozwiązaniu polegającym na osobnym sortowaniu każdego z kubełków złożoność czasowa algorytmu sortowania bąbelkowego wyniesie $100 \cdot 10^{2}$ , czyli $10 000$ .

Porównajmy ze sobą dwie liczby:

(1)

1000^{2} > 100 \cdot 10^{2}

Możemy zauważyć, że zastosowanie sortowania bąbelkowego w tym przypadku wymaga większej liczby operacji.

Należy jednak pamiętać, że nie zawsze liczba elementów w każdym z kubełków będzie taka sama.

Inicjalizujemy listę posortowane_liczby, którą wykorzystamy do zapisania wyniku.

# Inicjalizujemy zmienną do przechowywania wyniku
posortowane_liczby = []

Iterujemy po zawartości każdego z kubełków i dodajemy liczby do wyniku.

# Przeglądamy kubełki i dodajemy liczby do wyniku
for kubelek in kubelki:
	for elem in kubelek:
		posortowane_liczby.append(elem)
	return posortowane_liczby

Wypisujemy posortowaną listę.

print(sort_kubelk(liczby, n))

Przykład 1

Wykonajmy program, w którym pokażemy zawartość kubełków podczas sortowania. Do sortowania zawartości kubełka użyjemy standardowej funkcji języka Python sorted() oraz funkcji enumerate(), która zwraca dwie wartości: indeks elementu listy i jego wartość.

Wbudowana funkcja sorted() wykorzystuje algorytm Timsort. Jest to algorytm hybrydowy, który dla dostatecznie małych zestawów danych przełącza się z algorytmu sortowania przez scalanie na algorytm sortowania przez wstawianie.

Linia 1. def sort podkreślnik babelkowo otwórz nawias okrągły liczby zamknij nawias okrągły dwukropek. Linia 2. n znak równości len otwórz nawias okrągły liczby zamknij nawias okrągły. Linia 3. for i in range otwórz nawias okrągły 0 przecinek n minus 1 zamknij nawias okrągły dwukropek. Linia 4. for j in range otwórz nawias okrągły 1 przecinek n minus i zamknij nawias okrągły dwukropek. Linia 5. if liczby otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy zamknij nawias ostrokątny liczby otwórz nawias kwadratowy j zamknij nawias kwadratowy dwukropek. Linia 6. liczby otwórz nawias kwadratowy j zamknij nawias kwadratowy przecinek liczby otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy znak równości liczby otwórz nawias kwadratowy j minus 1 zamknij nawias kwadratowy przecinek liczby otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 7. return liczby. Linia 9. def sort podkreślnik kubelk otwórz nawias okrągły liczby przecinek n zamknij nawias okrągły dwukropek. Linia 10. n znak równości len otwórz nawias okrągły liczby zamknij nawias okrągły. Linia 11. max podkreślnik elem znak równości liczby otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 12. for i in range otwórz nawias okrągły 1 przecinek n zamknij nawias okrągły dwukropek. Linia 13. if liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny max podkreślnik elem dwukropek. Linia 14. max podkreślnik elem znak równości liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 15. kratka Tworzymy listę kubełków o rozmiarze n plus 1 przecinek aby zapobiec błędowi przy przypisaniu kubelki otwórz nawias kwadratowy n zamknij nawias kwadratowy. Linia 16. kubelki znak równości otwórz nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy for podkreślnik in range otwórz nawias okrągły n plus 1 zamknij nawias okrągły zamknij nawias kwadratowy. Linia 17. kratka obliczamy rozmiar kubełka przecinek dzielimy największą wartość przez liczbę kubełków. Linia 18. size znak równości max podkreślnik elem prawy ukośnik n. Linia 19. kratka Przypisujemy liczbę do odpowiedniego kubełka. Linia 20. for elem in liczby dwukropek. Linia 21. kubelek podkreślnik indeks znak równości int otwórz nawias okrągły elem prawy ukośnik prawy ukośnik size zamknij nawias okrągły kratka wykonamy dzielenie bez reszty przecinek a int otwórz nawias okrągły zamknij nawias okrągły da wartość przecinek która może być indeksem. Linia 22. kubelki otwórz nawias kwadratowy kubelek podkreślnik indeks zamknij nawias kwadratowy kropka append otwórz nawias okrągły elem zamknij nawias okrągły. Linia 23. kratka Sortujemy każdy kubełek za pomocą sortowania bąbelkowego. Linia 24. kratka oraz funkcji enumerate. Linia 25. for ind przecinek val in enumerate otwórz nawias okrągły kubelki zamknij nawias okrągły dwukropek. Linia 26. kubelki otwórz nawias kwadratowy ind zamknij nawias kwadratowy znak równości sort podkreślnik babelkowo otwórz nawias okrągły val zamknij nawias okrągły. Linia 27. kratka Inicjalizujemy zmienną do przechowywania wyniku. Linia 28. posortowane podkreślnik liczby znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 29. kratka Przeglądamy kubełki i dodajemy liczby do wyniku. Linia 30. for kubelek in kubelki dwukropek. Linia 31. for elem in kubelek dwukropek. Linia 32. posortowane podkreślnik liczby kropka append otwórz nawias okrągły elem zamknij nawias okrągły. Linia 33. return posortowane podkreślnik liczby. Linia 35. liczby znak równości otwórz nawias kwadratowy 0 kropka 1 przecinek 0 kropka 4 przecinek 0 kropka 2 przecinek 0 kropka 9 przecinek 0 kropka 5 przecinek 0 kropka 8 przecinek 0 kropka 3 przecinek 0 kropka 7 przecinek 0 kropka 6 zamknij nawias kwadratowy. Linia 36. n znak równości len otwórz nawias okrągły liczby zamknij nawias okrągły. Linia 37. print otwórz nawias okrągły sort podkreślnik kubelk otwórz nawias okrągły liczby przecinek n zamknij nawias okrągły zamknij nawias okrągły. Linia 39. kratka efekt. Linia 40. kratka otwórz nawias kwadratowy 0 kropka 1 przecinek 0 kropka 2 przecinek 0 kropka 3 przecinek 0 kropka 4 przecinek 0 kropka 5 przecinek 0 kropka 6 przecinek 0 kropka 7 przecinek 0 kropka 8 przecinek 0 kropka 9 zamknij nawias kwadratowy. Linia 42. kratka dodatkowo uruchomimy kod przecinek podając 3 kubełki. Linia 43. print otwórz nawias okrągły sort podkreślnik kubelk otwórz nawias okrągły liczby przecinek 3 zamknij nawias okrągły zamknij nawias okrągły. Linia 45. kratka efekt. Linia 46. kratka otwórz nawias kwadratowy 0 kropka 1 przecinek 0 kropka 2 przecinek 0 kropka 3 przecinek 0 kropka 4 przecinek 0 kropka 5 przecinek 0 kropka 6 przecinek 0 kropka 7 przecinek 0 kropka 8 przecinek 0 kropka 9 zamknij nawias kwadratowy. Linia 48. liczby znak równości otwórz nawias kwadratowy 0 kropka 1 przecinek 0 kropka 4 przecinek 9 kropka 345 przecinek 0 kropka 93 przecinek 0 kropka 2 przecinek 0 kropka 9 przecinek 1 kropka 5 przecinek 0 kropka 8 przecinek 2 kropka 3 przecinek 0 kropka 7 przecinek 0 kropka 6 przecinek 3 kropka 22 przecinek 3 kropka 4 przecinek 3 zamknij nawias kwadratowy. Linia 49. print otwórz nawias okrągły sort podkreślnik kubelk otwórz nawias okrągły liczby przecinek 3 zamknij nawias okrągły zamknij nawias okrągły. Linia 51. kratka efekt. Linia 52. kratka otwórz nawias kwadratowy 0 kropka 1 przecinek 0 kropka 2 przecinek 0 kropka 4 przecinek 0 kropka 6 przecinek 0 kropka 7 przecinek 0 kropka 8 przecinek 0 kropka 9 przecinek 0 kropka 93 przecinek 1 kropka 5 przecinek 2 kropka 3 przecinek 3 przecinek 3 kropka 22 przecinek 3 kropka 4 przecinek 9 kropka 345 zamknij nawias kwadratowy.

def sort_babelkowo(liczby):
    n = len(liczby)
    for i in range(0, n - 1):
        for j in range(1, n - i):
            if liczby[j - 1] > liczby[j]:
                liczby[j], liczby[j - 1] = liczby[j - 1], liczby[j]
    return liczby

def sort_kubelk(liczby, n):
    n = len(liczby)
    max_elem = liczby[0]
    for i in range(1, n):
        if liczby[i] > max_elem:
            max_elem = liczby[i]
    # Tworzymy listę kubełków o rozmiarze n+1, aby zapobiec błędowi przy przypisaniu kubelki[n]
    kubelki = [[] for _ in range(n+1)]
    # obliczamy rozmiar kubełka, dzielimy największą wartość przez liczbę kubełków
    size = max_elem / n
    # Przypisujemy liczbę do odpowiedniego kubełka
    for elem in liczby:
        kubelek_indeks = int(elem // size) # wykonamy dzielenie bez reszty, a int() da wartość, która może być indeksem
        kubelki[kubelek_indeks].append(elem)
    # Sortujemy każdy kubełek za pomocą sortowania bąbelkowego
    # oraz funkcji enumerate
    for ind, val in enumerate(kubelki):
        kubelki[ind] = sort_babelkowo(val)
    # Inicjalizujemy zmienną do przechowywania wyniku
    posortowane_liczby = []
    # Przeglądamy kubełki i dodajemy liczby do wyniku
    for kubelek in kubelki:
        for elem in kubelek:
            posortowane_liczby.append(elem)
    return posortowane_liczby

liczby = [0.1, 0.4, 0.2, 0.9, 0.5, 0.8, 0.3, 0.7, 0.6]
n = len(liczby)
print(sort_kubelk(liczby, n))

# efekt
# [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9]

# dodatkowo uruchomimy kod, podając 3 kubełki
print(sort_kubelk(liczby, 3))

# efekt
# [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9]

liczby = [0.1, 0.4, 9.345, 0.93, 0.2, 0.9, 1.5, 0.8, 2.3, 0.7, 0.6, 3.22, 3.4, 3]
print(sort_kubelk(liczby, 3))

# efekt
# [0.1, 0.2, 0.4, 0.6, 0.7, 0.8, 0.9, 0.93, 1.5, 2.3, 3, 3.22, 3.4, 9.345]

Ciekawostka

Możemy zauważyć, jak zmienia się rozkład kubełków, kiedy dodamy wartość mocno odbiegającą od reszty danych, np. 3.453452345234.

Linia 1. liczby znak równości otwórz nawias kwadratowy 0 kropka 7979395529003974 przecinek 3 kropka 453452345234 przecinek 0 kropka 06223874253203465 przecinek 0 kropka 7575263651547636 przecinek 0 kropka 8184646900589092 przecinek 0 kropka 00773510734757199 przecinek 0 kropka 884957901171751 przecinek 0 kropka 48560532998265327 przecinek 0 kropka 13251648080223966 przecinek 0 kropka 40327316514507294 przecinek 0 kropka 5396021490494737 przecinek 0 kropka 8757374908375566 przecinek 0 kropka 5431114783685939 przecinek 0 kropka 6515504595052689 przecinek 0 kropka 5851508345296675 przecinek 0 kropka 11551606200164644 przecinek 0 kropka 7627064515057248 przecinek 0 kropka 9561864120204504 przecinek 0 kropka 31324867565426284 przecinek 0 kropka 05430109642091918 przecinek 0 kropka 6297770656266365 przecinek 0 kropka 20410275473335304 przecinek 0 kropka 8472064540644259 przecinek 0 kropka 8027098593833801 przecinek 0 kropka 4121043216002158 przecinek 0 kropka 3029984158117578 przecinek 0 kropka 6103847194395624 przecinek 0 kropka 21094447321776189 przecinek 0 kropka 4787502959676083 przecinek 0 kropka 7134526678493234 przecinek 0 kropka 47080105239849435 przecinek 0 kropka 6888829030615161 przecinek 0 kropka 7221481031340844 przecinek 0 kropka 18863359642881405 przecinek 0 kropka 4639944842054391 przecinek 0 kropka 4433989144045307 przecinek 0 kropka 09200946113780228 przecinek 0 kropka 8878565634313789 przecinek 0 kropka 4816407227920425 przecinek 0 kropka 4340771417622189 przecinek 0 kropka 07872963378606201 zamknij nawias kwadratowy. Linia 2. print otwórz nawias okrągły sort podkreślnik kubelk podkreślnik print otwórz nawias okrągły liczby przecinek 10 zamknij nawias okrągły zamknij nawias okrągły. Linia 4. kratka efekt dwukropek. Linia 5. kratka Kubełek dwukropek otwórz nawias kwadratowy 0 kropka 00773510734757199 przecinek 0 kropka 05430109642091918 przecinek 0 kropka 06223874253203465 przecinek 0 kropka 07872963378606201 przecinek 0 kropka 09200946113780228 przecinek 0 kropka 11551606200164644 przecinek 0 kropka 13251648080223966 przecinek 0 kropka 18863359642881405 przecinek 0 kropka 20410275473335304 przecinek 0 kropka 21094447321776189 przecinek 0 kropka 3029984158117578 przecinek 0 kropka 31324867565426284 zamknij nawias kwadratowy. Linia 6. kratka Kubełek dwukropek otwórz nawias kwadratowy 0 kropka 40327316514507294 przecinek 0 kropka 4121043216002158 przecinek 0 kropka 4340771417622189 przecinek 0 kropka 4433989144045307 przecinek 0 kropka 4639944842054391 przecinek 0 kropka 47080105239849435 przecinek 0 kropka 4787502959676083 przecinek 0 kropka 4816407227920425 przecinek 0 kropka 48560532998265327 przecinek 0 kropka 5396021490494737 przecinek 0 kropka 5431114783685939 przecinek 0 kropka 5851508345296675 przecinek 0 kropka 6103847194395624 przecinek 0 kropka 6297770656266365 przecinek 0 kropka 6515504595052689 przecinek 0 kropka 6888829030615161 zamknij nawias kwadratowy. Linia 7. kratka Kubełek dwukropek otwórz nawias kwadratowy 0 kropka 7134526678493234 przecinek 0 kropka 7221481031340844 przecinek 0 kropka 7575263651547636 przecinek 0 kropka 7627064515057248 przecinek 0 kropka 7979395529003974 przecinek 0 kropka 8027098593833801 przecinek 0 kropka 8184646900589092 przecinek 0 kropka 8472064540644259 przecinek 0 kropka 8757374908375566 przecinek 0 kropka 884957901171751 przecinek 0 kropka 8878565634313789 przecinek 0 kropka 9561864120204504 zamknij nawias kwadratowy. Linia 8. kratka Kubełek dwukropek otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 9. kratka Kubełek dwukropek otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 10. kratka Kubełek dwukropek otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 11. kratka Kubełek dwukropek otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 12. kratka Kubełek dwukropek otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 13. kratka Kubełek dwukropek otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 14. kratka Kubełek dwukropek otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 15. kratka Kubełek dwukropek otwórz nawias kwadratowy 3 kropka 453452345234 zamknij nawias kwadratowy. Linia 16. kratka otwórz nawias kwadratowy 0 kropka 00773510734757199 przecinek 0 kropka 05430109642091918 przecinek 0 kropka 06223874253203465 przecinek 0 kropka 07872963378606201 przecinek 0 kropka 09200946113780228 przecinek 0 kropka 11551606200164644 przecinek 0 kropka 13251648080223966 przecinek 0 kropka 18863359642881405 przecinek 0 kropka 20410275473335304 przecinek 0 kropka 21094447321776189 przecinek 0 kropka 3029984158117578 przecinek 0 kropka 31324867565426284 przecinek 0 kropka 40327316514507294 przecinek 0 kropka 4121043216002158 przecinek 0 kropka 4340771417622189 przecinek 0 kropka 4433989144045307 przecinek 0 kropka 4639944842054391 przecinek 0 kropka 47080105239849435 przecinek 0 kropka 4787502959676083 przecinek 0 kropka 4816407227920425 przecinek 0 kropka 48560532998265327 przecinek 0 kropka 5396021490494737 przecinek 0 kropka 5431114783685939 przecinek 0 kropka 5851508345296675 przecinek 0 kropka 6103847194395624 przecinek 0 kropka 6297770656266365 przecinek 0 kropka 6515504595052689 przecinek 0 kropka 6888829030615161 przecinek 0 kropka 7134526678493234 przecinek 0 kropka 7221481031340844 przecinek 0 kropka 7575263651547636 przecinek 0 kropka 7627064515057248 przecinek 0 kropka 7979395529003974 przecinek 0 kropka 8027098593833801 przecinek 0 kropka 8184646900589092 przecinek 0 kropka 8472064540644259 przecinek 0 kropka 8757374908375566 przecinek 0 kropka 884957901171751 przecinek 0 kropka 8878565634313789 przecinek 0 kropka 9561864120204504 przecinek 3 kropka 453452345234 zamknij nawias kwadratowy.

liczby = [0.7979395529003974, 3.453452345234, 0.06223874253203465, 0.7575263651547636, 0.8184646900589092, 0.00773510734757199, 0.884957901171751, 0.48560532998265327, 0.13251648080223966, 0.40327316514507294, 0.5396021490494737, 0.8757374908375566, 0.5431114783685939, 0.6515504595052689, 0.5851508345296675, 0.11551606200164644, 0.7627064515057248, 0.9561864120204504, 0.31324867565426284, 0.05430109642091918, 0.6297770656266365, 0.20410275473335304, 0.8472064540644259, 0.8027098593833801, 0.4121043216002158, 0.3029984158117578, 0.6103847194395624, 0.21094447321776189, 0.4787502959676083, 0.7134526678493234, 0.47080105239849435, 0.6888829030615161, 0.7221481031340844, 0.18863359642881405, 0.4639944842054391, 0.4433989144045307, 0.09200946113780228, 0.8878565634313789, 0.4816407227920425, 0.4340771417622189, 0.07872963378606201]
print(sort_kubelk_print(liczby,10))

# efekt:
# Kubełek: [0.00773510734757199, 0.05430109642091918, 0.06223874253203465, 0.07872963378606201, 0.09200946113780228, 0.11551606200164644, 0.13251648080223966, 0.18863359642881405, 0.20410275473335304, 0.21094447321776189, 0.3029984158117578, 0.31324867565426284]
# Kubełek: [0.40327316514507294, 0.4121043216002158, 0.4340771417622189, 0.4433989144045307, 0.4639944842054391, 0.47080105239849435, 0.4787502959676083, 0.4816407227920425, 0.48560532998265327, 0.5396021490494737, 0.5431114783685939, 0.5851508345296675, 0.6103847194395624, 0.6297770656266365, 0.6515504595052689, 0.6888829030615161]
# Kubełek: [0.7134526678493234, 0.7221481031340844, 0.7575263651547636, 0.7627064515057248, 0.7979395529003974, 0.8027098593833801, 0.8184646900589092, 0.8472064540644259, 0.8757374908375566, 0.884957901171751, 0.8878565634313789, 0.9561864120204504]
# Kubełek: []
# Kubełek: []
# Kubełek: []
# Kubełek: []
# Kubełek: []
# Kubełek: []
# Kubełek: []
# Kubełek: [3.453452345234]
# [0.00773510734757199, 0.05430109642091918, 0.06223874253203465, 0.07872963378606201, 0.09200946113780228, 0.11551606200164644, 0.13251648080223966, 0.18863359642881405, 0.20410275473335304, 0.21094447321776189, 0.3029984158117578, 0.31324867565426284, 0.40327316514507294, 0.4121043216002158, 0.4340771417622189, 0.4433989144045307, 0.4639944842054391, 0.47080105239849435, 0.4787502959676083, 0.4816407227920425, 0.48560532998265327, 0.5396021490494737, 0.5431114783685939, 0.5851508345296675, 0.6103847194395624, 0.6297770656266365, 0.6515504595052689, 0.6888829030615161, 0.7134526678493234, 0.7221481031340844, 0.7575263651547636, 0.7627064515057248, 0.7979395529003974, 0.8027098593833801, 0.8184646900589092, 0.8472064540644259, 0.8757374908375566, 0.884957901171751, 0.8878565634313789, 0.9561864120204504, 3.453452345234]

Słownik

indeks listy

numer, dzięki któremu możemy odnieść się do konkretnego elementu w tej liście

kubełek

komórka w pamięci, obiekt, czy innego rodzaju struktura, identyfikowana jednoznacznie poprzez unikalną cechę sortowanego zbioru (w przypadku listy liczb całkowitych każdy kubełek identyfikowany byłby unikalną liczbą), w których zliczamy liczbę wystąpień elementów, zawierających daną cechę

złożoność czasowa

ilość czasu potrzebnego do wykonania zadania, wyrażona jako funkcja ilości danych

złożoność obliczeniowa

ilość zasobów komputerowych potrzebnych do wykonania zadania

Wprowadzenie

Symulacja interaktywna

Sortowanie kubełkowe

Sortowanie liczb całkowitych

Sortowanie liczb rzeczywistych

Słownik