Sortowanie bąbelkowe w Python

powrót

Zasada działania algorytmu została opisana w tym miejscu.

Najważniejsze cechy algorytmu:

• złożoność czasowa wynosi $$O(n^2),$$
• algorytm jest stabilny, czyli elementy o tych samych wartościach nie są ze sobą zamieniane,
• sortowanie wykonuje się w miejscu, czyli niepotrzebna jest dodatkowa tablica do uporządkowania zbioru,
• porównywane są dwa sąsiadujące ze sobą elementy,
• jest łatwy w implementacji.

Zadanie

Napisz program, który uporządkuje niemalejąco n liczb całkowitych.

Wejście

W pierwszym wierszu jedna liczba n nie większa niż 1000, określająca ilość liczb do uporządkowania. W drugim wierszu n liczb całkowitych, których wartość bezwzględna jest nie większa niż 10¹⁰.

Wyjście

W jednym wierszu n liczb uporządkowanych niemalejąco.

# --------algorytm.edu.pl----------
def sortowanie_babelkowe(liczby, n):

    for i in range(n):
        for j in range(1, n - i): # i końcowych liczb jest już uporządkowanych, więc je pommijamy
            if liczby[j-1] > liczby[j]: # jeśli dwie sąsiednie liczby stoją w złej kolejności
                liczby[j - 1], liczby[j] = liczby[j], liczby[j - 1] # to zamień je ze sobą miejscami
# główna część programu

n = int(input()) # wczytanie liczby elementów

liczby = list(map(int, input().split())) # wczytanie całego wiersza liczb

sortowanie_babelkowe(liczby, n)

for i in liczby: # wypisanie posortowanego ciągu liczb
    print(i, end = ' ')