Sortowanie przez wstawianie

Zadanie 3 z 7 · rozdział 21Trudność: 2 z 3sortinginsertion-sortlist

Treść zadania

Napisz funkcję sortowanie_przez_wstawianie(lista), która sortuje listę rosnąco (w miejscu) algorytmem sortowania przez wstawianie.

Algorytm buduje posortowany fragment od lewej strony. Dla każdej pozycji $i = 1, 2, \dots, n-1$:

  1. zapamiętaj element lista[i] (klucz),
  2. przesuwaj o jedną pozycję w prawo te elementy posortowanego fragmentu lista[0..i-1], które są większe od klucza (idąc od prawej strony),
  3. wstaw klucz na zwolnione miejsce,
  4. wypisz aktualny stan listy.

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: stan listy po wstawieniu każdego kolejnego elementu, w formacie listy Pythona. Ostatnia linia to lista posortowana.

Ograniczenia

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

Uwagi

Uwagi o algorytmie:

  • Po kroku $i$ fragment lista[0..i] jest posortowany, a reszta listy jest jeszcze nieruszona.
  • Algorytm działa bardzo szybko dla danych prawie posortowanych; w najgorszym przypadku ma złożoność $O(n^2)$.

Przykład

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

Najpierw 2 trafia przed 6, potem 1 przed 2, potem 4 między 2 a 6; 27 zostaje na swoim miejscu.

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
5
1 2 3 4 5
Oczekiwane wyjście
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

Test 3

Nie uruchomiono
Wejście
6
6 5 4 3 2 1
Oczekiwane wyjście
[5, 6, 4, 3, 2, 1]
[4, 5, 6, 3, 2, 1]
[3, 4, 5, 6, 2, 1]
[2, 3, 4, 5, 6, 1]
[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, 3, 0, -5, 2, -1]
[-1, 3, 3, 0, -5, 2, -1]
[-1, 0, 3, 3, -5, 2, -1]
[-5, -1, 0, 3, 3, 2, -1]
[-5, -1, 0, 2, 3, 3, -1]
[-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]
[7, 7, 7, 7]

Test 6

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