Sortowanie bąbelkowe

Zadanie 1 z 7 · rozdział 21Trudność: 1 z 3sortingbubble-sortlist

Treść zadania

Napisz funkcję sortowanie_babelkowe(lista), która sortuje listę rosnąco (w miejscu) algorytmem sortowania bąbelkowego.

Algorytm wykonuje kolejne przebiegi. W jednym przebiegu porównuje kolejne pary sąsiednich elementów — na pozycjach $(0, 1)$, $(1, 2)$, $(2, 3)$, … — i zamienia je miejscami, jeśli lewy element jest większy od prawego. Przebiegi powtarza tak długo, aż w całym przebiegu nie zajdzie żadna zamiana — wtedy lista jest posortowana i algorytm się kończy.

Po każdym przebiegu (także po ostatnim, w którym nie było już żadnej zamiany) funkcja wypisuje 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

Stan listy po każdym przebiegu — każdy w osobnej linii, 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 każdym przebiegu największy z nieposortowanych elementów „wypływa” na swoje miejsce na końcu listy, dlatego w kolejnych przebiegach możesz zmniejszać zakres sprawdzania o 1 — nie zmienia to wypisywanych stanów.
  • Złożoność czasowa: $O(n^2)$, a dla listy już posortowanej — tylko jeden przebieg, czyli $O(n)$.

Przykład

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

W 1. przebiegu zamieniane są pary $(6, 2)$, $(6, 1)$ i $(6, 4)$; w 2. przebiegu para $(2, 1)$; w 3. przebiegu nie ma żadnej zamiany, więc algorytm się kończy.

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

Test 3

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

Test 6

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