Sortowanie przez selekcję (przez wybór) 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 niestabilny, czyli elementy o tych samych wartościach mogą być ze sobą zamienione,
• sortowanie wykonuje się w miejscu, czyli niepotrzebna jest dodatkowa tablica do uporządkowania zbioru,
• 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 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_selekcje(lista, n):

    for i in range(n):
        mn_index = i # indeks komórki z najmniejszą wartością
        for j in range(i+1, n): # pętla wyszukuje najmniejszy element w podzbiorze o pozycjach [i+1, n)
            if lista[j] < lista[mn_index]: # jeśli na pozycji j stoi mniejsza liczba niż na pozycji mn_index
                mn_index = j # to aktualizujemy mn_index

        # zamiana elementu najmniejszego w podzbiorze z pierwszą pozycją nieposortowaną
        lista[i], lista[mn_index] = lista[mn_index], lista[i]

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