Sortowanie przez wstawianie w Pythonie

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 zostaną ze sobą zamienione,
• sortowanie wykonuje się w miejscu, czyli niepotrzebna jest dodatkowa tablica do uporządkowania zbioru,
• jest prosty w implementacji,
• dla zbioru uporządkowanego wykonuje się w czasie liniowym.

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 kolejnych n wierszach po jednej liczbie całkowitej, 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_przez_wstawianie(lista, n):

    for i in range(1, n):
        # wstawienie elementu w odpowiednie miejsce
        pom = lista[i] # ten element zostanie wstawiony w odpowiednie miejsce
        j = i - 1
        # przesuwanie elementów większych od pom
        while j >= 0 and lista[j] > pom:
            lista[j + 1] = lista[j] # przesuwanie elementów
            j -= 1
        lista[j + 1] = pom # wstawienie wartości zmiennej pom
                        # w odpowiednie miejsce

#******************Główna część programu**************************
n = int(input("Podaj wielość zbioru: "))
lista = []
for i in range(n):
    lista.append(int(input()))
sortowanie_przez_wstawianie(lista, n) # sortujemy dane
# wypisujemy listę po wykonaniu sortowania
print(*lista)

Wejście/wyjście

Podaj wielość zbioru: 7
7
6
8
1
5
3
2
1 2 3 5 6 7 8