Napisz program, który wykorzystując algorytm sortowania szybkiego, wypisze wartość minimalną oraz maksymalną z podanej tablicy. Przetestuj działanie programu dla tablicy tab = [9, 11, 0, -8, 11, 5, 20, 45, 0, 100].
Specyfikacja problemu:
Dane:
n – liczba naturalna; liczba elementów tablicy tab
tab – n-elementowa tablica liczb całkowitych
Wynik:
minimum i maksimum dla tablicy tab; liczby całkowite
Przykładowe wyjście:
Linia 1. minus 8 100.
-8 100
RQIyd2pTMGhN9
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.
Przykładowe rozwiązanie zadania:
Linia 1. def podziel podkreślnik tablice otwórz nawias okrągły tab przecinek indeks podkreślnik poczatkowy przecinek indeks podkreślnik koncowy zamknij nawias okrągły dwukropek.
Linia 2. piwot znak równości tab otwórz nawias kwadratowy indeks podkreślnik koncowy zamknij nawias kwadratowy.
Linia 3. indeks podkreślnik mniejszego podkreślnik elementu znak równości indeks podkreślnik poczatkowy minus 1.
Linia 5. for j in range otwórz nawias okrągły indeks podkreślnik poczatkowy przecinek indeks podkreślnik koncowy zamknij nawias okrągły dwukropek.
Linia 6. if tab otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias ostrokątny piwot dwukropek.
Linia 7. indeks podkreślnik mniejszego podkreślnik elementu plus znak równości 1.
Linia 8. tab otwórz nawias kwadratowy indeks podkreślnik mniejszego podkreślnik elementu zamknij nawias kwadratowy przecinek tab otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości tab otwórz nawias kwadratowy j zamknij nawias kwadratowy przecinek tab otwórz nawias kwadratowy indeks podkreślnik mniejszego podkreślnik elementu zamknij nawias kwadratowy.
Linia 10. tab otwórz nawias kwadratowy indeks podkreślnik mniejszego podkreślnik elementu plus 1 zamknij nawias kwadratowy przecinek tab otwórz nawias kwadratowy indeks podkreślnik koncowy zamknij nawias kwadratowy znak równości tab otwórz nawias kwadratowy indeks podkreślnik koncowy zamknij nawias kwadratowy przecinek tab otwórz nawias kwadratowy indeks podkreślnik mniejszego podkreślnik elementu plus 1 zamknij nawias kwadratowy.
Linia 12. return indeks podkreślnik mniejszego podkreślnik elementu plus 1.
Linia 15. def sortowanie podkreślnik szybkie otwórz nawias okrągły tab przecinek indeks podkreślnik poczatkowy przecinek indeks podkreślnik koncowy zamknij nawias okrągły dwukropek.
Linia 16. if indeks podkreślnik poczatkowy otwórz nawias ostrokątny indeks podkreślnik koncowy dwukropek.
Linia 17. a znak równości podziel podkreślnik tablice otwórz nawias okrągły tab przecinek indeks podkreślnik poczatkowy przecinek indeks podkreślnik koncowy zamknij nawias okrągły.
Linia 19. sortowanie podkreślnik szybkie otwórz nawias okrągły tab przecinek indeks podkreślnik poczatkowy przecinek a minus 1 zamknij nawias okrągły.
Linia 20. sortowanie podkreślnik szybkie otwórz nawias okrągły tab przecinek a plus 1 przecinek indeks podkreślnik koncowy zamknij nawias okrągły.
Linia 24. tab znak równości otwórz nawias kwadratowy 9 przecinek 11 przecinek 0 przecinek minus 8 przecinek 11 przecinek 5 przecinek 20 przecinek 45 przecinek 0 przecinek 100 zamknij nawias kwadratowy.
Linia 25. n znak równości len otwórz nawias okrągły tab zamknij nawias okrągły.
Linia 26. sortowanie podkreślnik szybkie otwórz nawias okrągły tab przecinek 0 przecinek n minus 1 zamknij nawias okrągły.
Linia 28. print otwórz nawias okrągły tab otwórz nawias kwadratowy 0 zamknij nawias kwadratowy przecinek tab otwórz nawias kwadratowy n minus 1 zamknij nawias kwadratowy zamknij nawias okrągły.
def podziel_tablice(tab, indeks_poczatkowy, indeks_koncowy):
piwot = tab[indeks_koncowy]
indeks_mniejszego_elementu = indeks_poczatkowy - 1
for j in range(indeks_poczatkowy, indeks_koncowy):
if tab[j] < piwot:
indeks_mniejszego_elementu += 1
tab[indeks_mniejszego_elementu], tab[j] = tab[j], tab[indeks_mniejszego_elementu]
tab[indeks_mniejszego_elementu + 1], tab[indeks_koncowy] = tab[indeks_koncowy], tab[indeks_mniejszego_elementu + 1]
return indeks_mniejszego_elementu + 1
def sortowanie_szybkie(tab, indeks_poczatkowy, indeks_koncowy):
if indeks_poczatkowy < indeks_koncowy:
a = podziel_tablice(tab, indeks_poczatkowy, indeks_koncowy)
sortowanie_szybkie(tab, indeks_poczatkowy, a - 1)
sortowanie_szybkie(tab, a + 1, indeks_koncowy)
tab = [9, 11, 0, -8, 11, 5, 20, 45, 0, 100]
n = len(tab)
sortowanie_szybkie(tab, 0, n - 1)
print(tab[0], tab[n - 1])
21
Ćwiczenie 2
Napisz program, który przy użyciu algorytmu sortowania szybkiego uporządkuje zbiór podanych liter alfabetu łacińskiego w kolejności odwrotnej do alfabetycznej. Przetestuj działanie programu dla następującego zbioru liter tab = [a, f, e, o, b, l, q, y].
Specyfikacja problemu:
Dane:
n – liczba naturalna; liczba elementów tablicy tab
tab – n-elementowa tablica zawierająca małe litery alfabetu łacińskiego
Wynik:
tab – tablica znaków posortowana w kolejności odwrotnej do kolejności alfabetycznej; elementy oddzielone są pojedynczym znakiem spacji
Przykładowe wyjście:
Linia 1. y q o l f e b a.
y q o l f e b a
RMW3Pa6MZSt7X
Wymyśl pytanie na kartkówkę związane z tematem materiału.
Wymyśl pytanie na kartkówkę związane z tematem materiału.
Przykładowe rozwiązanie zadania:
Linia 1. def podziel podkreślnik tablice otwórz nawias okrągły tab przecinek indeks podkreślnik poczatkowy przecinek indeks podkreślnik koncowy zamknij nawias okrągły dwukropek.
Linia 2. piwot znak równości ord otwórz nawias okrągły tab otwórz nawias kwadratowy indeks podkreślnik koncowy zamknij nawias kwadratowy zamknij nawias okrągły.
Linia 3. indeks podkreślnik mniejszego podkreślnik elementu znak równości indeks podkreślnik poczatkowy minus 1.
Linia 5. for j in range otwórz nawias okrągły indeks podkreślnik poczatkowy przecinek indeks podkreślnik koncowy zamknij nawias okrągły dwukropek.
Linia 6. if ord otwórz nawias okrągły tab otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias ostrokątny piwot dwukropek.
Linia 7. indeks podkreślnik mniejszego podkreślnik elementu plus znak równości 1.
Linia 8. tab otwórz nawias kwadratowy indeks podkreślnik mniejszego podkreślnik elementu zamknij nawias kwadratowy przecinek tab otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości tab otwórz nawias kwadratowy j zamknij nawias kwadratowy przecinek tab otwórz nawias kwadratowy indeks podkreślnik mniejszego podkreślnik elementu zamknij nawias kwadratowy.
Linia 10. tab otwórz nawias kwadratowy indeks podkreślnik mniejszego podkreślnik elementu plus 1 zamknij nawias kwadratowy przecinek tab otwórz nawias kwadratowy indeks podkreślnik koncowy zamknij nawias kwadratowy znak równości tab otwórz nawias kwadratowy indeks podkreślnik koncowy zamknij nawias kwadratowy przecinek tab otwórz nawias kwadratowy indeks podkreślnik mniejszego podkreślnik elementu plus 1 zamknij nawias kwadratowy.
Linia 12. return indeks podkreślnik mniejszego podkreślnik elementu plus 1.
Linia 15. def sortowanie podkreślnik szybkie otwórz nawias okrągły tab przecinek indeks podkreślnik poczatkowy przecinek indeks podkreślnik koncowy zamknij nawias okrągły dwukropek.
Linia 16. if indeks podkreślnik poczatkowy otwórz nawias ostrokątny indeks podkreślnik koncowy dwukropek.
Linia 17. a znak równości podziel podkreślnik tablice otwórz nawias okrągły tab przecinek indeks podkreślnik poczatkowy przecinek indeks podkreślnik koncowy zamknij nawias okrągły.
Linia 18. sortowanie podkreślnik szybkie otwórz nawias okrągły tab przecinek indeks podkreślnik poczatkowy przecinek a minus 1 zamknij nawias okrągły.
Linia 19. sortowanie podkreślnik szybkie otwórz nawias okrągły tab przecinek a plus 1 przecinek indeks podkreślnik koncowy zamknij nawias okrągły.
Linia 22. tab znak równości otwórz nawias kwadratowy apostrof a apostrof przecinek apostrof f apostrof przecinek apostrof e apostrof przecinek apostrof o apostrof przecinek apostrof b apostrof przecinek apostrof l apostrof przecinek apostrof q apostrof przecinek apostrof y apostrof zamknij nawias kwadratowy.
Linia 23. n znak równości len otwórz nawias okrągły tab zamknij nawias okrągły.
Linia 24. sortowanie podkreślnik szybkie otwórz nawias okrągły tab przecinek 0 przecinek n minus 1 zamknij nawias okrągły.
Linia 26. for i in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek.
Linia 27. print otwórz nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły.
def podziel_tablice(tab, indeks_poczatkowy, indeks_koncowy):
piwot = ord(tab[indeks_koncowy])
indeks_mniejszego_elementu = indeks_poczatkowy - 1
for j in range(indeks_poczatkowy, indeks_koncowy):
if ord(tab[j]) > piwot:
indeks_mniejszego_elementu += 1
tab[indeks_mniejszego_elementu], tab[j] = tab[j], tab[indeks_mniejszego_elementu]
tab[indeks_mniejszego_elementu + 1], tab[indeks_koncowy] = tab[indeks_koncowy], tab[indeks_mniejszego_elementu + 1]
return indeks_mniejszego_elementu + 1
def sortowanie_szybkie(tab, indeks_poczatkowy, indeks_koncowy):
if indeks_poczatkowy < indeks_koncowy:
a = podziel_tablice(tab, indeks_poczatkowy, indeks_koncowy)
sortowanie_szybkie(tab, indeks_poczatkowy, a - 1)
sortowanie_szybkie(tab, a + 1, indeks_koncowy)
tab = ['a', 'f', 'e', 'o', 'b', 'l', 'q', 'y']
n = len(tab)
sortowanie_szybkie(tab, 0, n - 1)
for i in range(n):
print(tab[i], end=" ")
31
Ćwiczenie 3
W ramach badania zapytano grupę respondentów o zarobki. Odpowiedzi umieszczono w tablicy. Użyj algorytmu sortowania szybkiego, aby znaleźć medianę zarobków w tej grupie. Program powinien wydrukować wynik na standardowe wyjście.
Ważne!
Mediana to wartość środkowa. Aby wyznaczyć medianę jakiegoś zbioru liczb, musimy najpierw wypisać te liczby w kolejności niemalejącej, a następnie wybrać liczbę środkową (w przypadku, gdy mamy nieparzystą liczbę liczb w zbiorze). Jeśli mamy parzystą liczbę liczb w zbiorze, to mediana jest równa średniej arytmetycznej dwóch środkowych liczb.
Przetestuj jego działanie dla tablicy zarobki = [8500.57, 6400.32, 2800.56, 3500.12, 12870.67, 3300.45, 7020.0, 3000.01, 8100.29].
Specyfikacja problemu:
Dane:
n – liczba naturalna; liczba elementów tablicy zarobki