Sortowanie szybkie

Zadanie 5 z 7 · rozdział 21Trudność: 2 z 3sortingquick-sortrecursion

Treść zadania

Napisz rekurencyjną funkcję sortowanie_szybkie(lista), która zwraca nową, posortowaną rosnąco listę, korzystając z algorytmu Quick Sort:

  1. Jeśli lista ma mniej niż 2 elementy — jest posortowana, zwróć ją.
  2. Jako pivot wybierz pierwszy element listy.
  3. Podziel elementy listy na trzy grupy (zachowując ich kolejność z listy):
    • mniejsze — mniejsze od pivota,
    • rowne — równe pivotowi (w tym sam pivot),
    • wieksze — większe od pivota.
  4. Wypisz trzy grupy w jednej linii: print(mniejsze, rowne, wieksze).
  5. Rekurencyjnie posortuj najpierw grupę mniejsze, a potem wieksze.
  6. Zwróć sklejony wynik: posortowane mniejsze + rowne + posortowane wieksze.

Program wczytuje listę, sortuje ją i na końcu wypisuje posortowaną listę.

Dane wejściowe

  • 1. linia: liczba całkowita $n$ — liczba elementów
  • 2. linia: $n$ liczb całkowitych oddzielonych spacjami

Dane wyjściowe

  • Dla każdego podziału (w kolejności wykonywania) jedna linia z trzema listami oddzielonymi spacją, np. [2, 1, 4] [6] [27]. Pusta grupa to [].
  • Ostatnia linia: posortowana lista w formacie listy Pythona.

Ograniczenia

  • $2 \le n \le 20$
  • Elementy są liczbami całkowitymi z przedziału $[-1000, 1000]$.

Uwagi

Uwagi o algorytmie:

  • Średnio: $O(n \log n)$, w pesymistycznym przypadku (np. lista już posortowana przy pivocie z początku): $O(n^2)$.
  • Wybór pivota ma wpływ na wydajność.

Przykład

Wejście
5
6 2 1 4 27
Wyjście
[2, 1, 4] [6] [27]
[1] [2] [4]
[1, 2, 4, 6, 27]

Pierwszy podział (pivot 6) daje grupy [2, 1, 4], [6], [27]. Grupa [2, 1, 4] jest dzielona dalej (pivot 2). Grupy jednoelementowe są już posortowane, więc nie są dzielone.

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 21

Zadania w tym rozdziale polegają na samodzielnym zaimplementowaniu klasycznych algorytmów sortowania i wyszukiwania. Żeby było widać, że program naprawdę wykonuje dany algorytm, w każdym zadaniu wypisujesz stany pośrednie — listę po kolejnych krokach algorytmu albo kolejno sprawdzane pozycje.

Konwencje wspólne:

  • Każde zadanie to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście.
  • Wejście ma zawsze tę samą postać: w 1. linii liczba elementów $n$, w 2. linii $n$ liczb całkowitych oddzielonych spacjami. Jeśli algorytm potrzebuje dodatkowej wartości (np. szukanego klucza), znajduje się ona w 3. linii.
  • Listę wypisuj w formacie Pythona — dokładnie tak, jak robi to print(lista), np. [1, 2, 4, 6, 27].
  • Sortujemy zawsze rosnąco (niemalejąco — liczby mogą się powtarzać).
  • Zaimplementuj algorytm samodzielnie. Nie używaj sorted(), list.sort(), list.index(), operatora in na liście ani innych gotowych funkcji sortujących i wyszukujących.
  • Program nie wypisuje komunikatów typu „Podaj liczbę:”.

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Python uruchomi się w przeglądarce przy pierwszym teście.

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
2
2 1
Oczekiwane wyjście
[1] [2] []
[1, 2]

Test 2

Nie uruchomiono
Wejście
2
1 2
Oczekiwane wyjście
[] [1] [2]
[1, 2]

Test 3

Nie uruchomiono
Wejście
5
1 2 3 4 5
Oczekiwane wyjście
[] [1] [2, 3, 4, 5]
[] [2] [3, 4, 5]
[] [3] [4, 5]
[] [4] [5]
[1, 2, 3, 4, 5]

Test 4

Nie uruchomiono
Wejście
7
3 -1 3 0 -5 2 -1
Oczekiwane wyjście
[-1, 0, -5, 2, -1] [3, 3] []
[-5] [-1, -1] [0, 2]
[] [0] [2]
[-5, -1, -1, 0, 2, 3, 3]

Test 5

Nie uruchomiono
Wejście
4
7 7 7 7
Oczekiwane wyjście
[] [7, 7, 7, 7] []
[7, 7, 7, 7]

Test 6

Nie uruchomiono
Wejście
8
5 1 4 2 8 0 2 9
Oczekiwane wyjście
[1, 4, 2, 0, 2] [5] [8, 9]
[0] [1] [4, 2, 2]
[2, 2] [4] []
[] [2, 2] []
[] [8] [9]
[0, 1, 2, 2, 4, 5, 8, 9]
Uruchom z własnymi danymi