버블정렬

버블정렬은 앞뒤의 두개의 요소를 비교해서 교환하는 과정을 반복하는 방법이다 이 방법이 효휼적인 경우는 대부분의 원소가 정렬이 되었있을때이다 하지만 정렬이 되어있지 않는 경우에는 시간복잡도가 증가하는 방법이다.

def bubbleSorting(list):
    for i in range(len(list) - 1, 0, -1):
        beChanged = False
        # 이중 반북문안에서 교환이 일어났는지 판단하기 위한 변수이다 첫번째 반복문을 실행할때 마다 거짓으로 초기화 켜서
        # 이중반복문안에서 교환이 일어나야지만 True로 바뀌게 만들어준다.

        for e in range(i):
            if list[e] > list[e + 1]:
                list[e], list[e + 1] = list[e + 1], list[e]
                # 두개를 비교해서 더 큰게 존재한다면 두 더 큰요소를 뒤로 땡긴다.
                beChanged = True
                # 교환이 일어난걸을 확인하기 위해서 교환이 일어나면 사실로 바꿔준다.

        if beChanged == False:
            return list
            # 교환이 일어날때 까지만 실행한다.

for i in range(len(list) - 1, 0, -1): 리스트의 길이부터 시작해서 1까지만 실행한다.

beChanged = False 겉 반목문에서 만들고 이중반복문 안에서 교환이 일어났는지 환인하기 위해서 사용한다.

버블 정렬은 원소가 반대로 정렬되어 있는 경우에는 최악의 경우로 O(n**2) 시간복잡도를 가진다.