Sortowanie przez wybieranie

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

Treść zadania

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

Dla każdej pozycji $i = 0, 1, \dots, n-2$:

  1. znajdź najmniejszy element we fragmencie od pozycji $i$ do końca listy — jeśli najmniejsza wartość występuje w nim kilka razy, wybierz jej pierwsze wystąpienie (o najmniejszym indeksie),
  2. zamień ten element z elementem na pozycji $i$ (jeśli to ta sama pozycja, lista się nie zmienia),
  3. 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 każdym kroku $i$, 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$ na pozycjach $0, \dots, i$ stoją już najmniejsze elementy listy w kolejności rosnącej.
  • Złożoność czasowa: $O(n^2)$ — niezależnie od danych.

Przykład

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

Krok $i = 0$: najmniejszy element to 1 — zamieniamy go z 6. Krok $i = 1$: najmniejszy z [2, 6, 4, 27] to 2, stoi już na swoim miejscu. Krok $i = 2$: zamieniamy 4 z 6.

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
[1, 5, 4, 3, 2, 6]
[1, 2, 4, 3, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]

Test 4

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