버블 정렬은 가장 간단한 정렬 알고리즘으로 꼽을 수 있다. 구현이 매우 간단하여 급하게 정렬 알고리즘이 필요할 때 요긴하게 쓰인다. 하지만, 시간 복잡도에서 최악의 경우 O(n^2)이 나오기 때문에 빠른 성능을 기대하기는 어렵다. 그럼에도 불구하고, 버블 정렬도 몇가지를 개선하면 성능을 끌어올릴 수가 있다.
이것을 주제로 발표를 한적도 있었는데, 이 때 무슨 자신감이였는지 화이트보드 코딩에 도전했었다. 결과는 역시나 중간에 머리가 새까매져 단체 일시정지가 있었다. 어찌저찌 잘 마무리는 했으나 겸손이 주입될 수 있었던 경험이였다. 그때의 경험을 희석시키고자 글로써 정리해보려고 한다.
정렬
우선 정렬의 기본 연산에는 교환, 선택, 삽입이 있다. 대부분의 정렬 알고리즘은 이 세가지를 응용해서 만들어졌다. 각 정렬 알고리즘마다 주로 사용하는 연산이 있으며, 버블 정렬에는 교환 연산을 주로 쓰인다. 교환 횟수가 줄어들수록 성능을 개선시킬 수 있으며, 이번 글에서 이 점을 집중적으로 파고들 예정이다.
번외: 정렬은 그러면 왜 하는가?
정렬은 이분 탐색과 같은 특정 탐색 방법에서 필수적인 동작이다. 이분 탐색의 경우에 정렬된 상태에서만 데이터를 반복적으로 절반으로 나누면서 원하는 값을 찾을 수 있다. 또한, 그리디 알고리즘이나 특정 패턴을 찾는 문제에서도 쓰이며, 주로 대규모 데이터를 효과적으로 처리하는데에 중요한 역할을 한다.
버블 정렬
기본 동작
버블 정렬의 기본 동작(오름차순 기준)은 다음과 같다.
- 리스트의 처음부터 끝까지 이동하면서 인접한 두 요소를 비교한다.
- 만약 앞의 요소가 뒤의 요소보다 크다면, 두 요소의 위치를 교환한다.
- 이 과정을 리스트의 끝까지 반복하면 가장 큰 요소가 리스트의 끝으로 이동하게 된다.
- 이제 리스트의 끝에 있는 가장 큰 요소를 제외하고, 나머지 요소들에 대해 같은 과정을 반복한다.
- 이 과정을 리스트의 모든 요소가 정렬될 때까지 반복한다.
1
2
3
4
5
6
def bubble_sort(a_list):
n = len(a_list)
for i in range(n - 1):
for j in range(n - 1 - i):
if a_list[j] > a_list[j + 1]:
a_list[j], a_list[j + 1] = a_list[j + 1], a_list[j]
성능 측정
TODO
[x] 교환 횟수 측정
[x] 정렬이 잘 되는 지 확인
[x] 리스트의 사이즈가 클 때 확인