[알고리즘 공부] 1. Bubble Sort (버블 정렬)

Bubble Sort

Bubble Sort(이하 버블 정렬)은 가장 구현하기 쉬운 형태의 정렬 알고리즘입니다.

 

앞에서부터 숫자 2개씩 비교하여 작은 원소와 큰 원소의 자리만 바꿔주며 반복하는 형태입니다.

 

버블 정렬은 구현하기도 정말 쉽지만 쉬운 대가로 시간 복잡도를 잃었습니다. ㅠㅠ 

 

버블 정렬의 시간 복잡도는 O(n^2) 입니다. 

 

대부분의 경우에서 쓰이지 않는다고 하니 간단하게 구현만 하고 거품 정렬은 넘어가도록 하겠습니다. 

---

def BubbleSort(input):
    
    # 두개씩 비교하므로 길이에서 -1
    length = len(input) -1
    
    # 한바퀴 돌때마다 가장 큰 수는 맨 뒤로 가니까 
    # 비교해도 되는 숫자는 하나씩 줄여도 된다.
    for x in range(length, 0, -1):        
        for y in range(x):        
            if input[y] > input[y+1]:                
                input[y] , input[y+1] = input[y+1], input[y]
                
    return input