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

버블 정렬(Bubble Sort)은 인접한 두 요소를 비교하여 교환(Swap)하면서 정렬하는 방식

큰 값이 점점 뒤로 (또는 작은 값이 점점 앞으로) 이동하기 때문에, 거품(Bubble)이 올라가는 모습과 유사해서 버블 정렬이라고 불린다.

 

버블 정렬 동작 방식

1. 첫 번째 패스 (pass 1)

- 배열의 첫 번째 요소부터 인접한 요소를 비교하며 큰 값을 뒤로 보냄

- 한 번의 패스가 끝나면 가장 큰 값이 배열의 끝으로 이동

2. 두 번째 패스 (pass2)

- 다시 처음부터 비교하되, 마지막 값은 이미 정렬되었으므로 제외

- 두 번째로 큰 값이 그 전 위치로 이동

3. 반복 수행

- 총 (n-1) 번 반복하면 모든 요소가 정렬됨

 

버블 정렬의 예제

배열[5, 3, 8, 4, 2]를 버블로 정렬하는 과정

패스	비교 과정	결과(한 패스 후)
1	(5 ,3) -> (5, 8) -> (8, 4) -> (8, 2)	[3, 5, 4, 2, 8]
2	(3, 5) -> (5, 4) -> (5, 2)	[3, 4, 2, 5, 8]
3	(3, 4) -> (4, 2)	[3, 2, 4, 5, 8]
4	(3, 2)	[2, 3, 4, 5, 8]

 

버블 정렬 코드 구현(Python)

1.기본 버블 정렬

def bubble_sort(arr):
	n = len(arr)
    for i in range(n-1): # n-1번 반복
    	for j in range(n-1-i): # 이미 정렬된 부분 제외하고 반복
        	if arr[j]>arr[j+1]: # 인접한 값 비교
            	arr[j], arr[j+1] = arr[j+1],arr[j] #값 교환
    return arr
    
#테스트
arr = [5, 3, 8, 4, 2]
print(bubble_sort(arr)) #[2, 3, 4, 5, 8]

 

2.최적화된 버블 정렬(불필요한 반복 방지)

기본 정렬은 항상 n-1번 반복하지만, 이미 정렬된 경우에도 불필요한 반복을 한다.

이를 방지하기 위해 swap이 발생하지 않으면 조기 종료하는 기능을 추가.

def optimized_bubble_sort(arr):
	n = len(arr)
    for i in range(n-1):
   		swapped = False # 교환 발생 여부 체크
        for j in range(n-1-i):
        	if arr[j] > arr[j+1]:
            	arr[j],arr[j+1] = arr[j+1],arr[j]
                swapped = True # 교환 발생
        if not swapped: #교환이 없으면 정렬 완료
        	break
    return arr
    
#테스트
arr = [5, 3, 8, 4, 2]
print(optimized_bubble_sor(arr)) #[2, 3, 4, 5, 8]