버블 정렬은 뭐야?

개념

버블 정렬은 배열 A[1...n]에서 인접한 두 원소를 비교하며 조건(내림차순 또는 오름차순)에 맞게 자리를 교환하는 정렬 알고리즘입니다.

구현 방법

오름차순 정렬을 기준으로 본 버블 정렬의 구현 방법은 다음과 같습니다.

1. 배열을 순환하며 가장 큰 원소를 배열의 끝에 위치시킨다.
2. 원소 하나가 정렬되었기 때문에 배열의 크기를 감소시킨다.
3. 배열의 길이만큼 1을 반복한다.

파이썬 구현 코드

def bubble_sort(number_list):
    for i in range(len(number_list) - 1):  # 1.
        for j in range(1, len(number_list) - i):  # 2.
            if number_list[j-1] > number_list[j]:  # 3.
                number_list[j-1], number_list[j] = number_list[j], number_list[j-1]  # 4.
    return number_list

1. 한번 순환할 때마다 정렬된 원소의 개수가 하나씩 증가하기 때문에 배열의 길이 - 1까지 +1씩 값을 증가시켜준다.
2. 이전 원소와 현재 원소의 대소를 비교해야하기 때문에 1부터 순환을 시작한다.
3. 두 원소의 대소를 비교하는 조건으로 부등호 방향에 따라 오름차순, 내림차순으로 정렬할 수 있다.
4. 3의 조건에 맞게 두 원소를 교환해주는 것으로 j-1, j 번째 원소의 값을 교환해준다.

그림으로 보는 버블 정렬

1번 순환 동안 값이 정렬되는 과정

위의 그림은 한번의 순환 동안 원소가 이동하는 과정을 그린 것입니다. 주어진 배열에서 5는 가장 큰 값이므로 4번의 원소 교환 끝에 원소의 자리를 찾았습니다.

전체 정렬 과정

위 그림은 전체 배열에서 한번의 순환에 하나의 원소가 정렬되는 과정을 그린 것입니다. 그림에서 볼 수 있듯이 한 번의 순환에 하나의 원소가 정렬되는 것을 보았을 때 버블 정렬은 정렬을 위해서는 배열의 길이만큼 순환을 해야 한다는 것을 알 수 있습니다.

시간 복잡도

버블 정렬의 시간 복잡도는 평균, 최선, 최악의 경우 모두 O(n^2)입니다. 원소의 개수가 n개인 배열이 있다고 가정하였을 때 1️⃣의 경우 n-1번의 순환을 진행합니다. 2️⃣는 부분 배열의 최대값을 맨 끝으로 옮기는 연산으로 배열의 크기에 비례하여 연산 횟수가 늘어난다. (k개의 원소의 최대값을 맨 끝으로 옮기기 위해서는 k-1번의 비교와 최대 k-1번의 교환 연산이 발생한다)

 

따라서 주어진 배열을 i번 순환할 때마다 n-i번의 비교 연산을 하게 됩니다. 그러므로 비교 연산의 총합은 (n-1) + (n-2) + (n-3) + (n-4) + ... + 2 + 1 = n(n-1)/2, 즉 시간 복잡도가 O(n^2)가 되게 됩니다.

결론

정렬 알고리즘의 기초가 되는 버블 정렬에 대해서 알아보았습니다. 버블 정렬의 경우 구현과 코드 이해가 어렵지 않습니다. 기초가 되는 만큼 알고리즘의 효율성으로 보았을 때는 좋지 않습니다. 하지만 시간 복잡도를 이해하는 것과 추후 다른 효율적인 알고리즘을 이해하기 위해서는 충분한 이해가 필요하다고 생각합니다.

 

[참고 자료 및 깃허브 코드]

쉽게 배우는 알고리즘, 문병로, 한빛아카데미, 2018-01-20

깃허브(Github) - 버블 정렬 알고리즘 구현