Wymyśl pytanie na kartkówkę związane z tematem materiału.
21
Ćwiczenie 2
Uzupełnij luki w odpowiednich miejscach w kodzie, tak aby cyfry na kolejnych pozycjach były sortowane metodą sortowania przez zliczanie. Zbiór ma być posortowany niemalejąco.
Specyfikacja problemu:
Dane:
dane – lista zawierająca liczby całkowite; lista do posortowania
Wynik:
posortowane – lista zawierająca liczby całkowite; posortowana lista wejściowa
Program przetestuj dla listy: [876,111,412,908,765,321,765,23,3]
Rry6WNevUiFyz
Wymyśl pytanie na kartkówkę związane z tematem materiału.
Wymyśl pytanie na kartkówkę związane z tematem materiału.
Uzupełnij luki w odpowiednich miejscach w kodzie, tak aby program wykonywał poprawne sortowanie zadanego zbioru za pomocą algorytmu sortowania pozycyjnego przy wykorzystaniu algorytmu sortowania przez zliczanie.
Zdefiniowanie funkcji radix_sort.
Zdefiniowanie funkcji sortowanie_przez_zliczanie.
Funkcja zwraca tablicę posortowaną dla danych wejściowych [876,111,412,908,765,321,765,23,3]
Do napisania programu wykorzystaj dowolny edytor i poniższy kod.
Linia 1. def radix podkreślnik sort otwórz nawias okrągły dane zamknij nawias okrągły dwukropek.
Linia 2. liczba podkreślnik cyfr znak równości max otwórz nawias okrągły otwórz nawias kwadratowy len otwórz nawias okrągły str otwórz nawias okrągły liczba zamknij nawias okrągły zamknij nawias okrągły for liczba in dane zamknij nawias kwadratowy zamknij nawias okrągły.
Linia 4. for i in range otwórz nawias okrągły liczba podkreślnik cyfr zamknij nawias okrągły dwukropek.
Linia 5. sortowanie podkreślnik przez podkreślnik zliczanie otwórz nawias okrągły dane przecinek i zamknij nawias okrągły.
Linia 7. return dane.
Linia 10. def sortowanie podkreślnik przez podkreślnik zliczanie otwórz nawias okrągły dane przecinek pozycja podkreślnik cyfry zamknij nawias okrągły dwukropek.
Linia 11. tablica podkreślnik zliczen podkreślnik liczb znak równości otwórz nawias kwadratowy 0 for x in range otwórz nawias okrągły 10 zamknij nawias okrągły zamknij nawias kwadratowy.
Linia 12. temp znak równości otwórz nawias kwadratowy 0 for liczba in dane zamknij nawias kwadratowy.
Linia 14. wspolczynnik podkreślnik cyfry znak równości pow otwórz nawias okrągły 10 przecinek pozycja podkreślnik cyfry zamknij nawias okrągły.
Linia 16. for liczba in dane dwukropek.
Linia 17. kratka Tu uzupełnij kod.
Linia 19. for i in range otwórz nawias okrągły 1 przecinek len otwórz nawias okrągły tablica podkreślnik zliczen podkreślnik liczb zamknij nawias okrągły zamknij nawias okrągły dwukropek.
Linia 20. tablica podkreślnik zliczen podkreślnik liczb otwórz nawias kwadratowy i zamknij nawias kwadratowy plus znak równości tablica podkreślnik zliczen podkreślnik liczb otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy.
Linia 22. for i in range otwórz nawias okrągły len otwórz nawias okrągły dane zamknij nawias okrągły minus 1 przecinek minus 1 przecinek minus 1 zamknij nawias okrągły dwukropek.
Linia 23. kratka Tu uzupełnij kod.
Linia 25. for i in range otwórz nawias okrągły len otwórz nawias okrągły temp zamknij nawias okrągły zamknij nawias okrągły dwukropek.
Linia 26. dane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości temp otwórz nawias kwadratowy i zamknij nawias kwadratowy.
Linia 28. dane znak równości otwórz nawias kwadratowy 876 przecinek 111 przecinek 412 przecinek 908 przecinek 765 przecinek 321 przecinek 765 przecinek 23 przecinek 3 zamknij nawias kwadratowy.
def radix_sort(dane):
liczba_cyfr = max([len(str(liczba)) for liczba in dane])
for i in range(liczba_cyfr):
sortowanie_przez_zliczanie(dane, i)
return dane
def sortowanie_przez_zliczanie(dane, pozycja_cyfry):
tablica_zliczen_liczb = [0 for x in range(10)]
temp = [0 for liczba in dane]
wspolczynnik_cyfry = pow(10, pozycja_cyfry)
for liczba in dane:
# Tu uzupełnij kod
for i in range(1, len(tablica_zliczen_liczb)):
tablica_zliczen_liczb[i] += tablica_zliczen_liczb[i - 1]
for i in range(len(dane) - 1, -1, -1):
# Tu uzupełnij kod
for i in range(len(temp)):
dane[i] = temp[i]
dane = [876, 111, 412, 908, 765, 321, 765, 23, 3]
Przykładowe rozwiązanie zadania:
Linia 1. def sortowanie podkreślnik pozycyjne otwórz nawias okrągły dane zamknij nawias okrągły dwukropek.
Linia 2. liczba podkreślnik cyfr znak równości max otwórz nawias okrągły otwórz nawias kwadratowy len otwórz nawias okrągły str otwórz nawias okrągły liczba zamknij nawias okrągły zamknij nawias okrągły for liczba in dane zamknij nawias kwadratowy zamknij nawias okrągły.
Linia 4. for i in range otwórz nawias okrągły liczba podkreślnik cyfr zamknij nawias okrągły dwukropek.
Linia 5. sortowanie podkreślnik przez podkreślnik zliczanie otwórz nawias okrągły dane przecinek i zamknij nawias okrągły.
Linia 7. return dane.
Linia 9. def sortowanie podkreślnik przez podkreślnik zliczanie otwórz nawias okrągły dane przecinek pozycja podkreślnik cyfry zamknij nawias okrągły dwukropek.
Linia 10. lista podkreślnik zliczen podkreślnik liczb znak równości otwórz nawias kwadratowy 0 for podkreślnik in range otwórz nawias okrągły 10 zamknij nawias okrągły zamknij nawias kwadratowy.
Linia 11. lista podkreślnik tymczasowa znak równości otwórz nawias kwadratowy 0 for podkreślnik in dane zamknij nawias kwadratowy.
Linia 13. podzielnik znak równości 10 asterysk asterysk pozycja podkreślnik cyfry.
Linia 15. for liczba in dane dwukropek.
Linia 16. odczytana podkreślnik cyfra znak równości otwórz nawias okrągły liczba prawy ukośnik prawy ukośnik podzielnik zamknij nawias okrągły procent 10.
Linia 17. lista podkreślnik zliczen podkreślnik liczb otwórz nawias kwadratowy odczytana podkreślnik cyfra zamknij nawias kwadratowy plus znak równości 1.
Linia 19. for i in range otwórz nawias okrągły 1 przecinek len otwórz nawias okrągły lista podkreślnik zliczen podkreślnik liczb zamknij nawias okrągły zamknij nawias okrągły dwukropek.
Linia 20. lista podkreślnik zliczen podkreślnik liczb otwórz nawias kwadratowy i zamknij nawias kwadratowy plus znak równości lista podkreślnik zliczen podkreślnik liczb otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy.
Linia 22. for i in range otwórz nawias okrągły len otwórz nawias okrągły dane zamknij nawias okrągły minus 1 przecinek minus 1 przecinek minus 1 zamknij nawias okrągły dwukropek.
Linia 23. odczytana podkreślnik cyfra znak równości otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy prawy ukośnik prawy ukośnik podzielnik zamknij nawias okrągły procent 10.
Linia 24. indeks podkreślnik w podkreślnik liscie podkreślnik wynikowej znak równości lista podkreślnik zliczen podkreślnik liczb otwórz nawias kwadratowy odczytana podkreślnik cyfra zamknij nawias kwadratowy minus 1.
Linia 25. lista podkreślnik tymczasowa otwórz nawias kwadratowy indeks podkreślnik w podkreślnik liscie podkreślnik wynikowej zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy.
Linia 26. lista podkreślnik zliczen podkreślnik liczb otwórz nawias kwadratowy odczytana podkreślnik cyfra zamknij nawias kwadratowy minus znak równości 1.
Linia 28. for i in range otwórz nawias okrągły len otwórz nawias okrągły lista podkreślnik tymczasowa zamknij nawias okrągły zamknij nawias okrągły dwukropek.
Linia 29. dane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości lista podkreślnik tymczasowa otwórz nawias kwadratowy i zamknij nawias kwadratowy.
Linia 31. dane znak równości otwórz nawias kwadratowy 876 przecinek 111 przecinek 412 przecinek 908 przecinek 765 przecinek 321 przecinek 765 przecinek 23 przecinek 3 zamknij nawias kwadratowy.
Linia 32. posortowane znak równości sortowanie podkreślnik pozycyjne otwórz nawias okrągły dane zamknij nawias okrągły.
Linia 33. print otwórz nawias okrągły posortowane zamknij nawias okrągły.
def sortowanie_pozycyjne(dane):
liczba_cyfr = max([len(str(liczba)) for liczba in dane])
for i in range(liczba_cyfr):
sortowanie_przez_zliczanie(dane, i)
return dane
def sortowanie_przez_zliczanie(dane, pozycja_cyfry):
lista_zliczen_liczb = [0 for _ in range(10)]
lista_tymczasowa = [0 for _ in dane]
podzielnik = 10**pozycja_cyfry
for liczba in dane:
odczytana_cyfra = (liczba // podzielnik) % 10
lista_zliczen_liczb[odczytana_cyfra] += 1
for i in range(1, len(lista_zliczen_liczb)):
lista_zliczen_liczb[i] += lista_zliczen_liczb[i - 1]
for i in range(len(dane) - 1, -1, -1):
odczytana_cyfra = (dane[i] // podzielnik) % 10
indeks_w_liscie_wynikowej = lista_zliczen_liczb[odczytana_cyfra] - 1
lista_tymczasowa[indeks_w_liscie_wynikowej] = dane[i]
lista_zliczen_liczb[odczytana_cyfra] -= 1
for i in range(len(lista_tymczasowa)):
dane[i] = lista_tymczasowa[i]
dane = [876, 111, 412, 908, 765, 321, 765, 23, 3]
posortowane = sortowanie_pozycyjne(dane)
print(posortowane)
21
Ćwiczenie 3
Napisz program sortujący pozycyjnie, tak aby cyfry na kolejnych pozycjach były sortowane metodą sortowania przez wstawianie. Zbiór ma być posortowany nierosnąco.
Specyfikacja problemu:
Dane:
dane – lista zawierająca liczby całkowite; lista do posortowania
Wynik:
posortowane – lista zawierająca liczby całkowite; posortowana lista wejściowa
Program przetestuj dla listy: [5000,23,567,34909,2,98,1010,8,90]
R18PLGnCOv0z8
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Napisz program sortujący pozycyjnie tak, aby cyfry na kolejnych pozycjach były sortowane metodą sortowania przez wstawianie. Zbiór ma być posortowany malejąco.
Zdefiniowanie funkcji radix_sort. Zdefiniowanie funkcji sortowanie_przez_wstawianie. Funkcja zwraca tablicę posortowaną malejąco dla danych wejściowych [5000,23,567,34909,2,98,1010,8,90]
Do napisania programu wykorzystaj dowolny edytor i poniższy kod.
Linia 1. def sortowanie podkreślnik przez podkreślnik wstawianie otwórz nawias okrągły dane przecinek pozycja podkreślnik cyfry zamknij nawias okrągły dwukropek.
Linia 2. wspolczynnik podkreślnik cyfry znak równości pow otwórz nawias okrągły 10 przecinek pozycja podkreślnik cyfry zamknij nawias okrągły.
Linia 4. kratka Tu uzupełnij kod.
Linia 7. def radix podkreślnik sort otwórz nawias okrągły dane zamknij nawias okrągły dwukropek.
Linia 8. liczba podkreślnik cyfr znak równości max otwórz nawias okrągły otwórz nawias kwadratowy len otwórz nawias okrągły str otwórz nawias okrągły liczba zamknij nawias okrągły zamknij nawias okrągły for liczba in dane zamknij nawias kwadratowy zamknij nawias okrągły.
Linia 10. for i in range otwórz nawias okrągły liczba podkreślnik cyfr zamknij nawias okrągły dwukropek.
Linia 11. sortowanie podkreślnik przez podkreślnik wstawianie otwórz nawias okrągły dane przecinek i zamknij nawias okrągły.
Linia 13. return dane.
Linia 15. dane znak równości otwórz nawias kwadratowy 5000 przecinek 23 przecinek 567 przecinek 34909 przecinek 2 przecinek 98 przecinek 1010 przecinek 8 przecinek 90 zamknij nawias kwadratowy.
def sortowanie_przez_wstawianie(dane, pozycja_cyfry):
wspolczynnik_cyfry = pow(10, pozycja_cyfry)
# Tu uzupełnij kod
def radix_sort(dane):
liczba_cyfr = max([len(str(liczba)) for liczba in dane])
for i in range(liczba_cyfr):
sortowanie_przez_wstawianie(dane, i)
return dane
dane = [5000, 23, 567, 34909, 2, 98, 1010, 8, 90]
Przykładowe rozwiązanie zadania:
Linia 1. def sortowanie podkreślnik przez podkreślnik wstawianie otwórz nawias okrągły dane przecinek pozycja podkreślnik cyfry zamknij nawias okrągły dwukropek.
Linia 2. podzielnik znak równości 10 asterysk asterysk pozycja podkreślnik cyfry.
Linia 4. for i in range otwórz nawias okrągły 1 przecinek len otwórz nawias okrągły dane zamknij nawias okrągły zamknij nawias okrągły dwukropek.
Linia 5. odczytana podkreślnik cyfra znak równości otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy prawy ukośnik prawy ukośnik podzielnik zamknij nawias okrągły procent 10.
Linia 6. liczba znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy.
Linia 7. j znak równości i minus 1.
Linia 9. while j zamknij nawias ostrokątny znak równości 0 and otwórz nawias okrągły otwórz nawias okrągły dane otwórz nawias kwadratowy j zamknij nawias kwadratowy prawy ukośnik prawy ukośnik podzielnik zamknij nawias okrągły procent 10 zamknij nawias okrągły otwórz nawias ostrokątny odczytana podkreślnik cyfra dwukropek.
Linia 10. dane otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy j zamknij nawias kwadratowy.
Linia 11. j znak równości j minus 1.
Linia 12. dane otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy znak równości liczba.
Linia 15. def sortowanie podkreślnik pozycyjne otwórz nawias okrągły dane zamknij nawias okrągły dwukropek.
Linia 16. liczba podkreślnik cyfr znak równości max otwórz nawias okrągły otwórz nawias kwadratowy len otwórz nawias okrągły str otwórz nawias okrągły liczba zamknij nawias okrągły zamknij nawias okrągły for liczba in dane zamknij nawias kwadratowy zamknij nawias okrągły.
Linia 18. for i in range otwórz nawias okrągły liczba podkreślnik cyfr zamknij nawias okrągły dwukropek.
Linia 19. sortowanie podkreślnik przez podkreślnik wstawianie otwórz nawias okrągły dane przecinek i zamknij nawias okrągły.
Linia 21. return dane.
Linia 23. dane znak równości otwórz nawias kwadratowy 5000 przecinek 23 przecinek 567 przecinek 34909 przecinek 2 przecinek 98 przecinek 1010 przecinek 8 przecinek 90 zamknij nawias kwadratowy.
Linia 24. posortowane znak równości sortowanie podkreślnik pozycyjne otwórz nawias okrągły dane zamknij nawias okrągły.
Linia 25. print otwórz nawias okrągły posortowane zamknij nawias okrągły.
def sortowanie_przez_wstawianie(dane, pozycja_cyfry):
podzielnik = 10**pozycja_cyfry
for i in range(1, len(dane)):
odczytana_cyfra = (dane[i] // podzielnik) % 10
liczba = dane[i]
j = i - 1
while j >= 0 and ((dane[j] // podzielnik) % 10) < odczytana_cyfra:
dane[j + 1] = dane[j]
j = j - 1
dane[j + 1] = liczba
def sortowanie_pozycyjne(dane):
liczba_cyfr = max([len(str(liczba)) for liczba in dane])
for i in range(liczba_cyfr):
sortowanie_przez_wstawianie(dane, i)
return dane
dane = [5000, 23, 567, 34909, 2, 98, 1010, 8, 90]
posortowane = sortowanie_pozycyjne(dane)
print(posortowane)