[알고리즘] 버블정렬(Bubble Sort) (Python)

1. 기본 원리

• 두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, swap 해주는 원리
• 결국 처음부터 끝까지 한번 훑으면 맨 마지막에 가장 큰 값이 위치하게 됨

 

2. 코드 구현 전 생각정리

• 그럼 한번 훑을 때 마다 정렬된 데이터가 끝부터 하나씩 쌓이게 되네?
• 반복문을 짜되, 이미 정렬이 된 부분은 이후에 훑지 않아도 되네?

 

3. 코드 구현

def bubble(input):
    
    for i in range(len(input)-1):
        for j in range(0,len(input)-1-i):
            if input[j]>=input[j+1]:
                input[j],input[j+1] = input[j+1],input[j]
                
    return input

 

4. 시간 복잡도

• 이중 for문이 있으므로 O(n^2)