Przeczytaj

Przykład 1

Przygotujmy program, który zrealizuje sortowanie pozycyjne liczb. Założymy, że liczby w danych wejściowych nie muszą być tej samej długości, więc jest konieczne przygotowanie funkcji pomocniczej, która sprawdzi, z ilu cyfr składa się największa liczba – będziemy to robić, wykonując dzielenie całkowite liczby przez kolejne potęgi liczby 10, dopóki iloraz nie będzie równy 0. Następnie, zaczynając od cyfry jedności, będziemy stopniowo sortować liczby po kolejnych pozycjach.

Specyfikacja problemu:

Dane:

lista_liczb – lista zawierająca liczby całkowite; lista do posortowania

Wynik:

posortowana_lista – lista zawierająca liczby całkowite; posortowana lista wejściowa

Zaczniemy od znalezienia maksymalnego podzielnika. Jest to największa potęga liczby 10, mniejsza od maksymalnej wartości z listy. Użyjemy do tego funkcji:

def sprawdz_maksimum(lista_liczb):
	maximum = lista_liczb[0]
	for i in range(1, len(lista_liczb)):
		if lista_liczb[i] > maximum:
			maximum = lista_liczb[i]
	podzielnik = 1

	while maximum > 0:
		maximum = maximum // 10
		if maximum > 0:
			podzielnik *= 10
	return podzielnik

Kolejnym krokiem będzie napisanie funkcji pomocniczej sortującej liczby na danej pozycji. Potrzebujemy dodatkowej metody sortowania, która musi być stabilna, aby liczby zachowały kolejność z sortowań na mniej znaczących pozycjach. W tym przypadku korzystamy z sortowania kubełkowegoPPpmzST7zsortowania kubełkowego, ponieważ jego złożoność jest liniowa. Liczby będziemy umieszczać w kubełkach o wartości równej ich cyfrze na aktualnie sortowanej pozycji, a następnie połączymy kubełki w jedną listę. Jako parametr funkcji będziemy przekazywać podzielnik, który będzie odpowiadał pozycji, po której chcemy sortować (np. dla cyfry jedności: 1, dla cyfry dziesiątek: 10 itd.).

def sortuj_liczby(lista, podzielnik):
	kubelki = [None] * 10
	posortowane_po_pozycji = []
	for element in lista:
		# dodajemy element do listy znajdującej się na indeksie odpowiadającym
		# jego wartości na aktualnie sprawdzanej pozycji
		wart = (element // podzielnik) % 10
		if type(kubelki[wart]) is list:
			kubelki[wart].append(element)
		else:
			kubelki[wart] = [element]
	for element in kubelki:
		# przepisujemy do nowej listy wszystkie elementy po kolei
		# z racji powyższego podziału będą już posortowane po danej pozycji
		while type(element) is list and len(element) > 0:
			posortowane_po_pozycji.append(element.pop(0))
	return posortowane_po_pozycji

Aby cała lista została posortowana, musimy posortować liczby po każdej pozycji. Zrobimy to w ten sposób:

podzielnik = sprawdz_maksimum(lista_liczb)

# sortujemy dla każdego możliwego podzielnika
p = 1
while p <= podzielnik:
	lista_liczb = sortuj_liczby(lista_liczb, p)
	p *= 10

Następnie połączymy cały program w jedną funkcję i przetestujemy go dla przykładowych danych:

Linia 1. def posortuj podkreślnik pozycyjnie podkreślnik liczby otwórz nawias okrągły lista podkreślnik liczb zamknij nawias okrągły dwukropek. Linia 2. def sprawdz podkreślnik maksimum otwórz nawias okrągły lista podkreślnik liczb zamknij nawias okrągły dwukropek. Linia 3. maximum znak równości lista podkreślnik liczb otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 4. for i in range otwórz nawias okrągły 1 przecinek len otwórz nawias okrągły lista podkreślnik liczb zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 5. if lista podkreślnik liczb otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny maximum dwukropek. Linia 6. maximum znak równości lista podkreślnik liczb otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 7. podzielnik znak równości 1. Linia 9. while maximum zamknij nawias ostrokątny 0 dwukropek. Linia 10. maximum znak równości maximum prawy ukośnik prawy ukośnik 10. Linia 11. if maximum zamknij nawias ostrokątny 0 dwukropek. Linia 12. podzielnik asterysk znak równości 10. Linia 13. return podzielnik. Linia 15. def sortuj podkreślnik liczby otwórz nawias okrągły lista przecinek podzielnik zamknij nawias okrągły dwukropek. Linia 16. kubelki znak równości otwórz nawias kwadratowy None zamknij nawias kwadratowy asterysk 10. Linia 17. posortowane podkreślnik po podkreślnik pozycji znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 18. for element in lista dwukropek. Linia 19. kratka dodajemy element do listy znajdującej się na indeksie odpowiadającym. Linia 20. kratka jego wartości na aktualnie sprawdzanej pozycji. Linia 21. wart znak równości otwórz nawias okrągły element prawy ukośnik prawy ukośnik podzielnik zamknij nawias okrągły procent 10. Linia 22. if type otwórz nawias okrągły kubelki otwórz nawias kwadratowy wart zamknij nawias kwadratowy zamknij nawias okrągły is list dwukropek. Linia 23. kubelki otwórz nawias kwadratowy wart zamknij nawias kwadratowy kropka append otwórz nawias okrągły element zamknij nawias okrągły. Linia 24. else dwukropek. Linia 25. kubelki otwórz nawias kwadratowy wart zamknij nawias kwadratowy znak równości otwórz nawias kwadratowy element zamknij nawias kwadratowy. Linia 26. for element in kubelki dwukropek. Linia 27. kratka przepisujemy do nowej listy wszystkie elementy po kolei. Linia 28. kratka z racji powyższego podziału będą już posortowane po danej pozycji. Linia 29. while type otwórz nawias okrągły element zamknij nawias okrągły is list and len otwórz nawias okrągły element zamknij nawias okrągły zamknij nawias ostrokątny 0 dwukropek. Linia 30. posortowane podkreślnik po podkreślnik pozycji kropka append otwórz nawias okrągły element kropka pop otwórz nawias okrągły 0 zamknij nawias okrągły zamknij nawias okrągły. Linia 31. return posortowane podkreślnik po podkreślnik pozycji. Linia 33. podzielnik znak równości sprawdz podkreślnik maksimum otwórz nawias okrągły lista podkreślnik liczb zamknij nawias okrągły. Linia 35. kratka sortujemy dla każdego możliwego podzielnika. Linia 36. p znak równości 1. Linia 37. while p otwórz nawias ostrokątny znak równości podzielnik dwukropek. Linia 38. lista podkreślnik liczb znak równości sortuj podkreślnik liczby otwórz nawias okrągły lista podkreślnik liczb przecinek p zamknij nawias okrągły. Linia 39. p asterysk znak równości 10. Linia 41. return lista podkreślnik liczb. Linia 43. kratka przykład wywołania. Linia 44. l znak równości otwórz nawias kwadratowy 321 przecinek 3476 przecinek 577 przecinek 85 przecinek 294 przecinek 235 przecinek 4565 przecinek 34 przecinek 547654 zamknij nawias kwadratowy. Linia 45. posortowana podkreślnik lista znak równości posortuj podkreślnik pozycyjnie podkreślnik liczby otwórz nawias okrągły l zamknij nawias okrągły. Linia 46. print otwórz nawias okrągły posortowana podkreślnik lista zamknij nawias okrągły. Linia 47. kratka otwórz nawias kwadratowy 34 przecinek 85 przecinek 235 przecinek 294 przecinek 321 przecinek 577 przecinek 3476 przecinek 4565 przecinek 547654 zamknij nawias kwadratowy. Linia 49. q znak równości otwórz nawias kwadratowy 1693 przecinek 1024 przecinek 3080 przecinek 2112 przecinek 1128 przecinek 3772 przecinek 907 przecinek 1719 przecinek 3816 przecinek 2530 przecinek 1202 przecinek 292 przecinek 918 przecinek 2247 przecinek 2076 przecinek 3636 przecinek 1604 przecinek 2307 przecinek 1424 przecinek 3990 przecinek 3515 przecinek 3664 przecinek 3377 przecinek 3393 przecinek 594 przecinek 104 przecinek 3548 przecinek 2174 przecinek 2797 przecinek 3113 przecinek 1014 przecinek 2578 przecinek 2323 przecinek 179 przecinek 2721 przecinek 15 przecinek 3349 przecinek 3583 przecinek 3922 przecinek 1074 przecinek 470 przecinek 256 przecinek 3916 przecinek 3647 przecinek 3794 przecinek 3023 przecinek 3668 przecinek 2080 przecinek 1869 przecinek 1061 przecinek 1678 przecinek 1268 przecinek 2123 przecinek 1245 przecinek 3669 przecinek 2632 przecinek 2183 przecinek 3514 przecinek 1810 przecinek 3667 zamknij nawias kwadratowy. Linia 50. posortowana podkreślnik lista znak równości posortuj podkreślnik pozycyjnie podkreślnik liczby otwórz nawias okrągły q zamknij nawias okrągły. Linia 51. print otwórz nawias okrągły posortowana podkreślnik lista zamknij nawias okrągły. Linia 52. kratka otwórz nawias kwadratowy 15 przecinek 104 przecinek 179 przecinek 256 przecinek 292 przecinek 470 przecinek 594 przecinek 907 przecinek 918 przecinek 1014 przecinek 1024 przecinek 1061 przecinek 1074 przecinek 1128 przecinek 1202 przecinek 1245 przecinek 1268 przecinek 1424 przecinek 1604 przecinek 1678 przecinek 1693 przecinek 1719 przecinek 1810 przecinek 1869 przecinek 2076 przecinek 2080 przecinek 2112 przecinek 2123 przecinek 2174 przecinek 2183 przecinek 2247 przecinek 2307 przecinek 2323 przecinek 2530 przecinek 2578 przecinek 2632 przecinek 2721 przecinek 2797 przecinek 3023 przecinek 3080 przecinek 3113 przecinek 3349 przecinek 3377 przecinek 3393 przecinek 3514 przecinek 3515 przecinek 3548 przecinek 3583 przecinek 3636 przecinek 3647 przecinek 3664 przecinek 3667 przecinek 3668 przecinek 3669 przecinek 3772 przecinek 3794 przecinek 3816 przecinek 3916 przecinek 3922 przecinek 3990 zamknij nawias kwadratowy.

def posortuj_pozycyjnie_liczby(lista_liczb):
	def sprawdz_maksimum(lista_liczb):
		maximum = lista_liczb[0]
		for i in range(1, len(lista_liczb)):
			if lista_liczb[i] > maximum:
				maximum = lista_liczb[i]
		podzielnik = 1

		while maximum > 0:
			maximum = maximum // 10
			if maximum > 0:
				podzielnik *= 10
		return podzielnik

	def sortuj_liczby(lista, podzielnik):
		kubelki = [None] * 10
		posortowane_po_pozycji = []
		for element in lista:
			# dodajemy element do listy znajdującej się na indeksie odpowiadającym
			# jego wartości na aktualnie sprawdzanej pozycji
			wart = (element // podzielnik) % 10
			if type(kubelki[wart]) is list:
				kubelki[wart].append(element)
			else:
				kubelki[wart] = [element]
		for element in kubelki:
			# przepisujemy do nowej listy wszystkie elementy po kolei
			# z racji powyższego podziału będą już posortowane po danej pozycji
			while type(element) is list and len(element) > 0:
				posortowane_po_pozycji.append(element.pop(0))
		return posortowane_po_pozycji

	podzielnik = sprawdz_maksimum(lista_liczb)

	# sortujemy dla każdego możliwego podzielnika
	p = 1
	while p <= podzielnik:
		lista_liczb = sortuj_liczby(lista_liczb, p)
		p *= 10

	return lista_liczb

# przykład wywołania
l = [321, 3476, 577, 85, 294, 235, 4565, 34, 547654]
posortowana_lista = posortuj_pozycyjnie_liczby(l)
print(posortowana_lista)
#[34, 85, 235, 294, 321, 577, 3476, 4565, 547654]

q = [1693, 1024, 3080, 2112, 1128, 3772, 907, 1719, 3816, 2530, 1202, 292, 918, 2247, 2076, 3636, 1604, 2307, 1424, 3990, 3515, 3664, 3377, 3393, 594, 104, 3548, 2174, 2797, 3113, 1014, 2578, 2323, 179, 2721, 15, 3349, 3583, 3922, 1074, 470, 256, 3916, 3647, 3794, 3023, 3668, 2080, 1869, 1061, 1678, 1268, 2123, 1245, 3669, 2632, 2183, 3514, 1810, 3667]
posortowana_lista = posortuj_pozycyjnie_liczby(q)
print(posortowana_lista)
#[15, 104, 179, 256, 292, 470, 594, 907, 918, 1014, 1024, 1061, 1074, 1128, 1202, 1245, 1268, 1424, 1604, 1678, 1693, 1719, 1810, 1869, 2076, 2080, 2112, 2123, 2174, 2183, 2247, 2307, 2323, 2530, 2578, 2632, 2721, 2797, 3023, 3080, 3113, 3349, 3377, 3393, 3514, 3515, 3548, 3583, 3636, 3647, 3664, 3667, 3668, 3669, 3772, 3794, 3816, 3916, 3922, 3990]

Ważne!

Wyjaśnijmy zapis element.pop(0). Metoda pop() usuwa i zwraca ostatni element listy, ale my – w celu zachowania kolejności elementów odkładanych do kubełka – pobieramy pierwszy element z listy, jednocześnie go z niej usuwając, zatem używamy metody pop z parametrem (jeśli chcesz dowiedzieć się więcej, informacje na ten temat znajdziesz w dostępnej w internecie dokumentacji języka Python).

Przykład 2

Korzystając z funkcji zaimplementowanej w przykładzie 1, stworzymy program pokazujący wyniki sortowania losowej listy liczb dla poszczególnych pozycji oraz wizualizujący (za pomocą modułu matplotlibmatplotlibmatplotlib) zależność liczby operacji od długości wejściowej tablicy danych oraz od wartości największego elementu w liście.

Specyfikacja problemu:

Dane:

lista_liczb – lista zawierająca liczby całkowite; lista do posortowania

Wynik:

wykres przedstawiający liczbę operacji ze względu na długość listy startowej, a także maksymalną wartość w danej liście

Program przetestujemy dla list o długościach wielokrotności liczby 10 z zakresu $⟨ 10, 100 ⟩$ o losowych wartościach z zakresu $⟨ 1, 4000 ⟩$ .

W tym celu w rozwiązaniu z poprzedniego zadania dodamy do funkcji sortującej zmienną zliczającą wykonane operacje, którą będziemy inkrementować za każdym razem, gdy będziemy dodawać lub wyciągać elementy z listy. Poza tym napiszemy kod, który przy użyciu funkcji scatter() i plot() z biblioteki matplotlib wyświetli interesujące nas dane.

Linia 1. from random import randint. Linia 2. import matplotlib kropka pyplot as plt. Linia 4. X0 znak równości otwórz nawias kwadratowy x for x in range otwórz nawias okrągły 10 przecinek 101 przecinek 10 zamknij nawias okrągły zamknij nawias kwadratowy. Linia 5. Y0 znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 6. Y1 znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 8. for x in X0 dwukropek. Linia 9. l podkreślnik test znak równości otwórz nawias kwadratowy randint otwórz nawias okrągły 1 przecinek 4000 zamknij nawias okrągły for y in range otwórz nawias okrągły x zamknij nawias okrągły zamknij nawias kwadratowy. Linia 10. l przecinek p znak równości posortuj podkreślnik pozycyjnie podkreślnik liczby podkreślnik wizualizacja otwórz nawias okrągły l podkreślnik test zamknij nawias okrągły. Linia 11. Y0 kropka append otwórz nawias okrągły p zamknij nawias okrągły. Linia 12. Y1 kropka append otwórz nawias okrągły max otwórz nawias okrągły l zamknij nawias okrągły zamknij nawias okrągły. Linia 13. lista przecinek oper znak równości posortuj podkreślnik pozycyjnie podkreślnik liczby podkreślnik wizualizacja otwórz nawias okrągły l podkreślnik test zamknij nawias okrągły. Linia 15. plt kropka plot otwórz nawias okrągły X0 przecinek Y0 przecinek label znak równości cudzysłów Liczba operacji sortowania cudzysłów zamknij nawias okrągły. Linia 16. plt kropka scatter otwórz nawias okrągły X0 przecinek Y1 przecinek label znak równości cudzysłów Maksymalna wartość w liście cudzysłów zamknij nawias okrągły. Linia 17. plt kropka xlabel otwórz nawias okrągły cudzysłów Liczba liczb do sortowania cudzysłów zamknij nawias okrągły. Linia 18. plt kropka ylabel otwórz nawias okrągły cudzysłów Liczba przeprowadzonych operacji cudzysłów zamknij nawias okrągły. Linia 19. plt kropka legend otwórz nawias okrągły zamknij nawias okrągły. Linia 20. plt kropka grid otwórz nawias okrągły True zamknij nawias okrągły. Linia 21. plt kropka show otwórz nawias okrągły zamknij nawias okrągły.

from random import randint
import matplotlib.pyplot as plt

X0 = [x for x in range(10, 101, 10)]
Y0 = []
Y1 = []

for x in X0:
	l_test = [randint(1, 4000) for y in range(x)]
	l, p = posortuj_pozycyjnie_liczby_wizualizacja(l_test)
	Y0.append(p)
	Y1.append(max(l))
	lista, oper = posortuj_pozycyjnie_liczby_wizualizacja(l_test)

plt.plot(X0, Y0, label="Liczba operacji sortowania")
plt.scatter(X0, Y1, label="Maksymalna wartość w liście")
plt.xlabel("Liczba liczb do sortowania")
plt.ylabel("Liczba przeprowadzonych operacji")
plt.legend()
plt.grid(True)
plt.show()

Cały program prezentuje się następująco:

Linia 1. def posortuj podkreślnik pozycyjnie podkreślnik liczby podkreślnik wizualizacja otwórz nawias okrągły lista podkreślnik liczb zamknij nawias okrągły dwukropek. Linia 2. def sprawdz podkreślnik maksimum otwórz nawias okrągły lista podkreślnik liczb zamknij nawias okrągły dwukropek. Linia 3. maximum znak równości lista podkreślnik liczb otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 4. for i in range otwórz nawias okrągły 1 przecinek len otwórz nawias okrągły lista podkreślnik liczb zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 5. if lista podkreślnik liczb otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny maximum dwukropek. Linia 6. maximum znak równości lista podkreślnik liczb otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 7. podzielnik znak równości 1. Linia 9. while maximum zamknij nawias ostrokątny 0 dwukropek. Linia 10. maximum znak równości maximum prawy ukośnik prawy ukośnik 10. Linia 11. if maximum zamknij nawias ostrokątny 0 dwukropek. Linia 12. podzielnik asterysk znak równości 10. Linia 13. return podzielnik. Linia 15. def sortuj podkreślnik liczby otwórz nawias okrągły lista przecinek podzielnik zamknij nawias okrągły dwukropek. Linia 16. operacje znak równości 0. Linia 17. kubelki znak równości otwórz nawias kwadratowy cudzysłów cudzysłów zamknij nawias kwadratowy asterysk 10. Linia 18. posortowane podkreślnik po podkreślnik pozycji znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 19. for element in lista dwukropek. Linia 20. wart znak równości otwórz nawias okrągły element prawy ukośnik prawy ukośnik podzielnik zamknij nawias okrągły procent 10. Linia 21. operacje plus znak równości 1. Linia 22. if type otwórz nawias okrągły kubelki otwórz nawias kwadratowy wart zamknij nawias kwadratowy zamknij nawias okrągły is list dwukropek. Linia 23. kubelki otwórz nawias kwadratowy wart zamknij nawias kwadratowy kropka append otwórz nawias okrągły element zamknij nawias okrągły. Linia 24. else dwukropek. Linia 25. kubelki otwórz nawias kwadratowy wart zamknij nawias kwadratowy znak równości otwórz nawias kwadratowy element zamknij nawias kwadratowy. Linia 26. for element in kubelki dwukropek. Linia 27. while type otwórz nawias okrągły element zamknij nawias okrągły is list and len otwórz nawias okrągły element zamknij nawias okrągły zamknij nawias ostrokątny 0 dwukropek. Linia 28. posortowane podkreślnik po podkreślnik pozycji kropka append otwórz nawias okrągły element kropka pop otwórz nawias okrągły 0 zamknij nawias okrągły zamknij nawias okrągły. Linia 29. operacje plus znak równości 1. Linia 30. return posortowane podkreślnik po podkreślnik pozycji przecinek operacje. Linia 32. podzielnik znak równości sprawdz podkreślnik maksimum otwórz nawias okrągły lista podkreślnik liczb zamknij nawias okrągły. Linia 34. kratka sortujemy dla każdego możliwego podzielnika. Linia 35. p znak równości 1. Linia 36. suma podkreślnik operacji znak równości 0. Linia 37. while p otwórz nawias ostrokątny znak równości podzielnik dwukropek. Linia 38. lista podkreślnik liczb przecinek operacje znak równości sortuj podkreślnik liczby otwórz nawias okrągły lista podkreślnik liczb przecinek p zamknij nawias okrągły. Linia 39. suma podkreślnik operacji plus znak równości operacje. Linia 40. p asterysk znak równości 10. Linia 42. return lista podkreślnik liczb przecinek suma podkreślnik operacji. Linia 45. from random import randint. Linia 46. import matplotlib kropka pyplot as plt. Linia 48. X0 znak równości otwórz nawias kwadratowy x for x in range otwórz nawias okrągły 10 przecinek 101 przecinek 10 zamknij nawias okrągły zamknij nawias kwadratowy. Linia 49. Y0 znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 50. Y1 znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 52. for x in X0 dwukropek. Linia 53. l podkreślnik test znak równości otwórz nawias kwadratowy randint otwórz nawias okrągły 1 przecinek 4000 zamknij nawias okrągły for y in range otwórz nawias okrągły x zamknij nawias okrągły zamknij nawias kwadratowy. Linia 54. l przecinek p znak równości posortuj podkreślnik pozycyjnie podkreślnik liczby podkreślnik wizualizacja otwórz nawias okrągły l podkreślnik test zamknij nawias okrągły. Linia 55. Y0 kropka append otwórz nawias okrągły p zamknij nawias okrągły. Linia 56. Y1 kropka append otwórz nawias okrągły max otwórz nawias okrągły l zamknij nawias okrągły zamknij nawias okrągły. Linia 57. lista przecinek oper znak równości posortuj podkreślnik pozycyjnie podkreślnik liczby podkreślnik wizualizacja otwórz nawias okrągły l podkreślnik test zamknij nawias okrągły. Linia 59. plt kropka plot otwórz nawias okrągły X0 przecinek Y0 przecinek label znak równości cudzysłów Liczba operacji sortowania cudzysłów zamknij nawias okrągły. Linia 60. plt kropka scatter otwórz nawias okrągły X0 przecinek Y1 przecinek label znak równości cudzysłów Maksymalna wartość w liście cudzysłów zamknij nawias okrągły. Linia 61. plt kropka xlabel otwórz nawias okrągły cudzysłów Liczba liczb do sortowania cudzysłów zamknij nawias okrągły. Linia 62. plt kropka ylabel otwórz nawias okrągły cudzysłów Liczba przeprowadzonych operacji cudzysłów zamknij nawias okrągły. Linia 63. plt kropka legend otwórz nawias okrągły zamknij nawias okrągły. Linia 64. plt kropka grid otwórz nawias okrągły True zamknij nawias okrągły. Linia 65. plt kropka show otwórz nawias okrągły zamknij nawias okrągły.

def posortuj_pozycyjnie_liczby_wizualizacja(lista_liczb):
	def sprawdz_maksimum(lista_liczb):
		maximum = lista_liczb[0]
		for i in range(1, len(lista_liczb)):
			if lista_liczb[i] > maximum:
				maximum = lista_liczb[i]
		podzielnik = 1

		while maximum > 0:
			maximum = maximum // 10
			if maximum > 0:
				podzielnik *= 10
		return podzielnik

	def sortuj_liczby(lista, podzielnik):
		operacje = 0
		kubelki = [""] * 10
		posortowane_po_pozycji = []
		for element in lista:
			wart = (element // podzielnik) % 10
			operacje += 1
			if type(kubelki[wart]) is list:
				kubelki[wart].append(element)
			else:
				kubelki[wart] = [element]
		for element in kubelki:
			while type(element) is list and len(element) > 0:
				posortowane_po_pozycji.append(element.pop(0))
				operacje += 1
		return posortowane_po_pozycji, operacje

	podzielnik = sprawdz_maksimum(lista_liczb)

	# sortujemy dla każdego możliwego podzielnika
	p = 1
	suma_operacji = 0
	while p <= podzielnik:
		lista_liczb, operacje = sortuj_liczby(lista_liczb, p)
		suma_operacji += operacje
		p *= 10

	return lista_liczb, suma_operacji


from random import randint
import matplotlib.pyplot as plt

X0 = [x for x in range(10, 101, 10)]
Y0 = []
Y1 = []

for x in X0:
	l_test = [randint(1, 4000) for y in range(x)]
	l, p = posortuj_pozycyjnie_liczby_wizualizacja(l_test)
	Y0.append(p)
	Y1.append(max(l))
	lista, oper = posortuj_pozycyjnie_liczby_wizualizacja(l_test)

plt.plot(X0, Y0, label="Liczba operacji sortowania")
plt.scatter(X0, Y1, label="Maksymalna wartość w liście")
plt.xlabel("Liczba liczb do sortowania")
plt.ylabel("Liczba przeprowadzonych operacji")
plt.legend()
plt.grid(True)
plt.show()

Program powinien narysować wykres wyglądający podobnie do tego:

RTqQvzroYTE1K

Ilustracja przedstawia wykres. Oś X oznaczona Liczba liczb do sortowania i skali od 0 do 100. Oś Y oznaczona Liczba przeprowadzonych operacji i skali od 0 do 4000. Na wykresie znajduje się linia oznaczająca liczbę operacji sortowania od 0 do około 750 na osi Y, oraz 10 punktów znajdujących się w okolicy 4000 na osi Y. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Na wykresie można zauważyć, że każda lista zawierała maksymalną liczbę większą niż 1000, a co za tym idzie, za każdym razem trzeba było wykonać sortowanie na czterech pozycjach. Przy okazji potwierdziliśmy doświadczalnie, że złożoność algorytmu jest liniowa względem liczby sortowanych liczb, co widać po liczbie operacji potrzebnych do posortowania listy.

Już wiesz

Podsumujmy najważniejsze wiadomości:

sortowanie pozycyjne jest odpowiednie do porządkowania elementów (obiektów, wielkości), w których można wyróżnić pozycje;
sortowanie pozycyjne wymaga zastosowania dodatkowego stabilnego algorytmu sortującego;
złożoność czasowa to $O (d (n + k))$ ;
sortowanie pozycyjne jest stabilnym algorytmem sortowaniastabilny algorytm sortowaniastabilnym algorytmem sortowania.

Słownik

matplotlib

biblioteka służąca do przedstawiania obrazów składających się z punktów o współrzędnych x oraz y (wykresów, histogramów, rozkładów itp.); moduł matplotlib nie jest dostępny w standardowej instalacji języka Python – należy go zainstalować, korzystając z mechanizmu pip

stabilny algorytm sortowania

typ algorytmów sortujących, które w przypadku występowania kilku obiektów o takiej samej wartości w zbiorze wejściowym, po posortowaniu zachowują ich wzajemną kolejność początkową

Wprowadzenie

Prezentacja multimedialna

Słownik