---
title: WDI zadanie 3 lista 6
---

'''
algorytm bubble sort polega na "wypychaniu" największego elementu na koniec listy w każdej iteracji pętli.
how_many - zmienna, która odzwierciedla liczbę obrotów pęli
swipe - kontroluje, czy w danym przebiegu pętli for nastąpiła jakaś zamiana elementów - jeżeli nie, to znaczy, że tablica jest już posortowana i można przerwać działanie pętli

'''

def bubble_sort(T): #argumentem tej funkcji jest lista do posortowania
    n = len(T)
    swipe = True
    how_many = 0
    temp = 0
    while (how_many < n-1) and swipe:
        swipe = False
        for i in range(n-1-how_many):   #dzięki odjęciu "how_many" nie porównujemy już posortowanych elementów z końca tablicy
            if T[i] > T[i+1]:
                temp = T[i]
                T[i] = T[i+1]
                T[i+1] = temp
                swipe = True
        how_many += 1
    return T
                
                
print(bubble_sort([4, 6, 1, 3, 2, 5, 7, 4, 155, 0, 3, 5, 94, 2]))

'''
liczba porównań dla ciągu uporządkowanego niemalejąco: n-1 ---> ponieważ już po pierwszym przejściu pętli, dzieki zmiennej swap okaże się, że nie nastąpiła żadna zamiana
liczba podstawień dla ciągu uporządkowanego niemalejąco: 0

liczba porównań dla ciągu uporządkowanego nierosąno: n^2//2
liczba podstawień dla ciągu uporządkowanego nierosąno: n^2//2

złożoność o(n^2) ponieważ, mimo usprawnień, występują dwie zagnieżdzone pętle