[알고리즘] 버블 정렬

1. 버블 정렬 정의
2. 버블 정렬 개념
3. 버블 정렬 예시
4. 버블 정렬 구현 (With Python3)

 

버블 정렬 정의

• 두 인접한 원소를 검사하여 정렬하는 방법

출처 : https://en.wikipedia.org/wiki/Bubble_sort

버블 정렬 개념

• 두 인접한 원소를 검사하기 때문에 n번째는 n+1번째 값과 비교하여 교환해주는 방식으로 진행한다.
• 만일 정렬하고자 하는 대상이 [6,5,3,1,8,7,2,4]이라면, 첫번째 값인 6은 두번째 값인 5와 비교를 하고 첫번째 값이 두번째 값보다 크기 때문에 서로 값을 교환해준다. 그 결과 [5,6,3,1,8,7,2,4]가 되고 그 다음으로는 두번째 값인 6과 3을 비교해서 값을 교환해준다. 그 결과 [5,3,6,1,8,7,2,4]가 되고 그 다음으로 세번째 값인 6과 네번째 값인 1을 비교해 값을 교환해준다. 이런식으로 마지막 - 1번째 값과 마지막 값과의 비교로 정렬 한바퀴를 완료한다.
• 정렬 한바퀴를 완료했을시, 가장 큰 값이 맨 뒤로 이동한다.  
• 마찬가지로, 정렬 두바퀴를 완료했을시에는 두번째 큰 값이 가장 큰 값 앞으로 이동한다.
  • 즉, n번째 바퀴 진행시 n번째 가장 큰 값을 알 수 있다.
• 버블 정렬은 정렬하고자 하는 대상이 n개라면 총 n바퀴를 수행해야하고 처음 바퀴에는 n-1번 데이터를 비교해야하고 다음 바퀴는 n-2번 데이터를 비교하고 그 다음 바퀴에는 n-3번 데이터를 비교해야한다.

 

버블 정렬 예시

• 버블 정렬을 이용하여 [5,4,2,1,3]을 오름차순으로 정렬시

버블 정렬 예시

• 첫번째 바퀴
  • 첫번째 값과 두번째 값인 5와 4를 교환하고 두번째 값과 세번째 값인 5와 2를 교환하고 세번째 값인 5와 네번째 값인 1을 교환하고 네번째 값과 다섯번째 값인 5와 3을 교환해서 가장 큰 값인 5를 맨 마지막에 위치한다.
• 두번째 바퀴
  • 첫번째 값과 두번째 값인 4와 2를 교환하고 두번째 값과 세번째 값인 4와 1를 교환하고 세번째 값과 네번째 값인 4와 3을 교환하여 두번째로 큰 값인 4를 5 앞에 위치한다.
• 세번째 바퀴
  • 첫번째 값과 두번째 값인 2와 1을 교환하고 두번째 값과 세번째 값인 2와 3을 비교하여 세번째로 큰 값인 3을 4 앞에 위치한다.
• 네번째 바퀴
  • 첫번째 값과 두번째 값인 1과 2를 비교하여 4번째로 큰 값인 2를 3 앞에 위치시킨다.
• 원소 한개만 남으므로 최종적으로 [1,2,3,4,5]가 오름차순으로 정렬된 리스트임을 확인한다.

 

버블 정렬 구현 (with Python3)

def bubbleSort(x):
    
    for i in range(len(x) - 1):
        swap = False
        for j in range(len(x) - i - 1):
            if x[j] > x[j+1]: # n번째 값이 n+1값보다 큰 경우 swap
                x[j], x[j+1] = x[j+1], x[j]
                swap = True
        if swap == False: # 교환이 필요하지 않은 정렬된 상태
            break
    return x
        
if __name__ == "__main__":
    
    x = [5,4,2,3,1]
    
    bubbleSort(x)

 

버블 정렬 분석

• 시간 복잡도
  •  반복을 두 번 실행하므로 $$O(n^2)$$
  • 정렬이 된 경우 (swap에서 True인 경우), $$O(n)$$