Sortowanie przez scalanie

Zadanie 4 z 7 · rozdział 21Trudność: 2 z 3sortingmerge-sortrecursion

Treść zadania

Napisz rekurencyjną funkcję sortowanie_przez_scalanie(lista), która zwraca nową, posortowaną rosnąco listę, korzystając z algorytmu sortowania przez scalanie:

  1. Jeśli lista ma mniej niż 2 elementy — jest posortowana, zwróć ją.
  2. Podziel listę na dwie części: lewa to pierwsze $\lfloor n/2 \rfloor$ elementów (lista[:n // 2]), prawa — pozostałe.
  3. Rekurencyjnie posortuj najpierw lewą, a potem prawą część.
  4. Scal obie posortowane części w jedną posortowaną listę (pomocnicza funkcja scal(lewa, prawa)), wypisz wynik scalenia i go zwróć.

Scalanie: dopóki obie listy mają elementy, porównuj ich pierwsze (najmniejsze) nieużyte elementy i dopisuj do wyniku mniejszy z nich; na koniec dopisz pozostałe elementy.

Dane wejściowe

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

Dane wyjściowe

$n - 1$ linii: wynik każdego scalenia, w kolejności wykonywania, w formacie listy Pythona. Ostatnie scalenie daje całą posortowaną listę.

Ograniczenia

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

Uwagi

Uwagi o algorytmie:

  • Złożoność czasowa: $O(n \log n)$.

Przykład

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

Lista dzieli się na [6, 2] i [1, 4, 27]. Lewa część daje scalenie [6] + [2] → [2, 6]. Prawa dzieli się na [1] i [4, 27]; najpierw scalane są [4] + [27], potem [1] + [4, 27]. Na końcu scalane są obie połowy.

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]

Test 2

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

Test 3

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

Test 4

Nie uruchomiono
Wejście
7
3 -1 3 0 -5 2 -1
Oczekiwane wyjście
[-1, 3]
[-1, 3, 3]
[-5, 0]
[-1, 2]
[-5, -1, 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, 5]
[2, 4]
[1, 2, 4, 5]
[0, 8]
[2, 9]
[0, 2, 8, 9]
[0, 1, 2, 2, 4, 5, 8, 9]
Uruchom z własnymi danymi