버블 정렬(Bubble Sort)의 개념
버블 정렬은 인접한 두 값을 비교하여 한쪽의 값이 더 큰 경우에는 자리를 바꾸는 과정을 반복해 정렬하는 방식입니다. 아래와 같은 흐름을 가집니다.
- 배열의 첫 번째 원소부터 시작하여 인접한 원소와 비교합니다.
- 현재 원소가 인접한 원소보다 크면, 두 원소의 위치를 서로 바꿉니다. (Swap)
- 다음 원소로 이동하여 위의 과정을 반복합니다.
- 배열의 끝에 도달하면, 배열의 크기를 하나 줄이고, 다시 첫 번째 원소부터 비교를 시작합니다.
- 배열의 크기가 1이 될 때까지 위의 과정을 반복합니다.
버블 정렬의 Python 구현
Python 으로 버블 정렬을 아래와 같이 구현할 수 있습니다.
def bubble_sort(arr):
n = len(arr)
# 배열의 모든 요소를 순회
for i in range(n):
# 마지막 i개의 요소는 이미 정렬되어 있으므로, n-i-1까지만 순회
for j in range(0, n - i - 1):
# 현재 요소가 다음 요소보다 크면, 위치를 교환
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
위의 코드는 어떻게 동작할까요? 아래와 같은 리스트를 정렬할 때,
^
[20, 10, 40, 30, 50]먼저 20과 10을 비교한 후 10과 20을 스왑하게 됩니다.
^
[10, 20, 40, 30, 50]이제 20과 40을 비교하는데, 20보다 40이 크므로 스왑하지 않습니다.
^
[10, 20, 40, 30, 50]40과 30을 비교한 후, 서로를 스왑합니다.
^
[10, 20, 30, 40, 50]40과 50을 비교하지만, 스왑하지 않습니다.
^
[10, 20, 30, 40, 50]이렇게 하면, 결과적으로 제일 큰 값인 50을 맨 뒤로 보낼 수 있습니다.
이제 두 번째 순회 시작점인 20부터 위의 과정을 반복하지만, 이미 정렬은 완료되었습니다. (이는 최적화의 여지가 있다는 의미이기도 합니다.)
버블 정렬의 최적화
위의 과정에서는 첫 번째 패스를 끝냈는데도 정렬이 모두 완료되었습니다. 그 말은 첫 번째 패스만 끝마치고, 나머지 (20과 30 비교, 30과 40 비교 … 하여 모든 원소에 대해 가장 큰 요소를 맨 끝으로 위치시키는 작업) 패스는 생략해도 되죠.
def bubble_sort_optimized(arr):
n = len(arr)
for i in range(n):
is_changed = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
is_changed = True
if not is_changed:
break
데이터가 정렬되었다는 것은 어떤 인접한 두 데이터를 비교해도 자리바꿈이 발생하지 않는다는 뜻이기 때문에, 어떤 패스에서 자리바꿈이 전혀 발생하지 않았다면 그것은 정렬이 끝났음을 의미하는 것입니다.
하여, 위와 같이 is_changed 와 같은 변수를 만들어 버블 정렬이 불필요한 루프를 돌지 않도록 최적화할 수 있습니다.
버블 정렬의 성능 분석과 특징
- 버블 정렬은 이중 루프로 구성됩니다. 바깥 루프에서 배열을 순회하고(
n-1 번), 안쪽 루프에서i값에 따라n-2번부터 … 1번까지 비교를 수행하게 됩니다. 결과적으로O(n^2)의 시간 복잡도를 가집니다. - 버블 정렬은 안정적 정렬 알고리즘입니다.
- 버블 정렬은 제자리 정렬 알고리즘입니다. 입력 배열과 입력 크기 n 을 위한 저장공간 외에 필요한 저장공간은 상수 개입니다. 입력 배열의 크기가 늘어나도 추가로 필요한 저장공간이 늘어나지 않습니다.
- 선택 정렬에 비해서 데이터 교환이 많이 발생합니다.
- 최적화한 경우, 데이터가 이미 원하는 순서대로 정렬되었다면
O(n)의 시간 복잡도를 가집니다.