---
title: WDI zad2 lista6
---

'''
w każdej iteracji pętli wybieramy najmniejszy element listy i ustawiamy go na pozycji odpowiadającej numerowi iteracji
po każdym przejściu pętli zamieniamy indeks iteracji z indeksem elementu najmniejszego
b) złożoność czasowa O(n^2)
c) instrukcja dominująca:

for j in range(i + 1, n):
            if T[index_min] > T[j]:
                index_min = j

d) liczba porównań dla jakiegokolwiek ciągu: n + (n-1) + (n-2)+...+ 2 + 1 = (n(n-1))/2 = O($n^2$)
liczba podstawień dla ciągu niemalejącego ($a_1 \leq a_2...\leq a_n$): 0
liczba podstawień dla ciągu nierosnącego ($a_1 \geq a_2...\geq a_n$): (n(n-1))/2

'''

def select_sort(T):
    n = len(T)
    index_min = 0
    for i in range(n-1):
        index_min = i
        for j in range(i + 1, n):
            if T[index_min] > T[j]:
                index_min = j
        if index_min != i:
            temp = T[index_min]
            T[index_min] = T[i]
            T[i] = temp
    return T

print(select_sort([4, 6, 1, 3, 2, 5, 7, 4, 155, 0, 3, 5, 94, 2]))