Strefa wyzwań

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 ....

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. 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

  • 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