R13XFHOJPLQJ3
Fotografia przedstawia spiralne elementy w fabryce. Są wysokie, identyczne. Stoją w jednym rzędzie.

PYI_R_W14_M27 Metoda Quicksort

Źródło: Kelvyn Ornettte Sol Marte, domena publiczna.
Już wiesz

  • jak przeanalizować pseudokod, który jest zapisem algorytmu sortowania szybkiego,

  • jaki jest czas działania algorytmu quick sort, w tym dla przypadku optymistycznego i pesymistycznego,

  • jak zastosować algorytm sortowania przykładowej tablicy za pomocą algorytmu quick sort,

  • jak zaimplementować algorytm quick sort w języku Python.

Teraz czas sprawdzić swoją wiedzę i umiejętności w praktyce

Ćwiczenie 1
R1462F3T5FTR3
Co to jest sortowanie w miejscu? Możliwe odpowiedzi: 1. Jest to algorytm sortowania, do którego może być potrzebna dodatkowa pamięć., 2. Jest to algorytm sortowania, w którym elementy znajdują się cały czas w początkowej tablicy, 3. Jest to algorytm sortowania, w którym elementy w tablicy nie zmieniają swojej pozycji., 4. Jest to algorytm sortowania, którego złożoność czasowa wynosi O(n log n)
Ćwiczenie 2
R1D9LBFG46UDJ
Wskaż, jaka jest złożoność czasowa przypadku pesymistycznego sortowania szybkiego. text=O(n log2 n)
text=O(log2 n)
text=O(n2)
text=O(n)
Ćwiczenie 3
RQ177EPP9EZPM
Jaka jest złożoność czasowa przypadku optymistycznego sortowania szybkiego? Możliwe odpowiedzi: 1. O(n log2 n), 2. O(log2 n), 3. O(n2), 4. O(n)
1
Ćwiczenie 4

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.
RQIyd2pTMGhN9
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
1
Ćwiczenie 5

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.
RMW3Pa6MZSt7X
Wymyśl pytanie na kartkówkę związane z tematem materiału.
1
Ćwiczenie 6

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 w uporządkowanym zbiorze danych, dzieląca go na dwie części. W przypadku, gdy liczba obserwacji jest nieparzysta, mediana to środkowa wartość. Natomiast w zbiorach o parzystej liczbie elementów, mediana obliczana jest jako średnia arytmetyczna dwóch środkowych wartości. Dzięki tym właściwościom, mediana jest niezwykle przydatna w różnych analizach statystycznych.

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

  • zarobki – n-elementowa tablica liczb rzeczywistych

Wynik:

  • mediana posortowanej tablicy zarobki; liczba rzeczywista

Przykładowe wyjście

Linia 1. 6400 kropka 32.
RnwnTZ93isMih
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Implementacja algorytmu
PYI_R_W14_M28 Miejsca zerowe funkcji