Bubble Sort (버블 정렬)

def bubble(lst):
    for i in range(len(lst)-1):
        if lst[i] > lst[i+1]:
            lst[i], lst[i+1] = lst[i+1], lst[i]
	

a = [3, 1, 5, 9, 7, 10]
bubble(a)
print(a)
	

# Bubble Sort
# 서로 인접한 두 원소의 대소를 비교해가면서 자리를 교환해 정렬하는 방식
# 시간복잡도: O(n^2)
# 공간복잡도: n
# 장점: 구현이 쉽다. memory가 추가로 들지 않는다(in-place). 중복된 값들이 있을 경우 원래 순서를 보장한다(stable).
# 단점: 정렬이 되어 있건 안 되어 있건 무조건 비교 연산을 수행하기 때문에 수행시간이 무조건 n^2이다.