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

정리해놓자...

TL;DR

- 비효율적 (단위가 클수록, 랜덤한 데이터를 대상으로 하기에는)

- 구현은 쉬운편

 

버블 정렬이란

버블 정렬은 최초로 정립된 알고리즘 종류로 알려져 있습니다.

다른 정렬 알고리즘에 비해 구현이 간편합니다.

그래서 정렬 알고리즘을 처음 접할때 가장 첫 챕터에 등장하기도 합니다.

하지만 효율이 극악이라 쓰이는 경우는 많지는 않다고 합니다.

보통의 경우, 최악의 경우 모두 O(n^2) 효율성을 가집니다.

 

구현 설명

총 n개의 원소(e)가 있는 데이터가 있습니다.

e0와 e1를 비교해 더 큰 값을 뒤로 두고

e1와 e2를 비교해 더 큰 값을 뒤로 두는 작업을 반복해

e(n-1)과 e(n) 비교까지 마칩니다.

 

그런 다음 또다시 e0과 e1 비교로 돌아갑니다.

처음과 같은 비교작업을 e(n-2)와 e(n-1)까지 합니다.

 

여기 e(n-2),e(n-1) 같은 이 비교의 끝지점을 쉽게 e(l-1), e(l) 라고 해보겠습니다.

이렇게 한번 돌고 두번 돌다가  e(l-1), e(l)이 e0, e1가 되었을때 알고리즘은 종료됩니다.

 

결국 n 만큼 순회를 하고, (e(l)이 e(n)부터 e1이 될때까지니까)

그 한 순회당 두 원소끼리의 비교는 n-(현 순회 횟수)-1번 이루어집니다. (한쌍씩 짝 지어지니까 -1)

그래서 두 번의 반복문이 있기에 O(n^2) 시간복잡도를 지닌겁니다.

 

https://visualgo.net/en/sorting

 

구현 (Python)

1차 구현

import random


def bubble_sort(arr):
    n = len(arr)

    # n만큼 loop
    for i in range(n):

        # n-i-1만큼 loop
        for j in range(0, n-i-1):
            print(f'비교: {arr[j]} <-> {arr[j+1]}')
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
            print(f'정렬됨 : {arr}')


numbers = [random.randint(0, 100) for _ in range(4)]

print(f'시작 : {numbers}')
bubble_sort(numbers)

명성에 맞게 코드가 매우 간결합니다.

 

결과

시작 : [88, 46, 64, 30]

비교: 88 <-> 46
정렬됨 : [46, 88, 64, 30]

비교: 88 <-> 64
정렬됨 : [46, 64, 88, 30]

비교: 88 <-> 30
정렬됨 : [46, 64, 30, 88]

비교: 46 <-> 64
정렬됨 : [46, 64, 30, 88]

비교: 64 <-> 30
정렬됨 : [46, 30, 64, 88]

비교: 46 <-> 30
정렬됨 : [30, 46, 64, 88]

 

특이점

그런데 분명 설명에 적었듯이, 보통의 경우, 최악의 경우 모두 O(n^2)라고 했는데

최선의 경우에는 O(n) 정도의 효율성을 보여줍니다.

이 경우는 이미 정렬할 데이터가 어느정도 정렬되어 있다는 가정이 있어야 합니다.

두 원소를 비교하며 순서를 뒤집는게 버블 정렬의 관건인데

만약 한 번 훑는 과정에서 보니 한 번도 순서가 바뀐게 없다면?

이미 정렬된 데이터로 판단하고 로직을 종료시키면 됩니다.

 

2차 구현

def bubble_sort(arr):
    n = len(arr)
    element_reversed = False

    # n만큼 loop
    for i in range(n):

        # n-i-1만큼 loop
        for j in range(0, n-i-1):
            print(f'비교: {arr[j]} <-> {arr[j+1]}')
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                element_reversed = True
            print(f'정렬됨 : {arr}')

        if element_reversed is False:
            return


numbers = [1, 2, 3, 4, 5]

print(f'시작 : {numbers}')
bubble_sort(numbers)

 

결과

시작 : [1, 2, 3, 4, 5]

비교: 1 <-> 2
정렬됨 : [1, 2, 3, 4, 5]

비교: 2 <-> 3
정렬됨 : [1, 2, 3, 4, 5]

비교: 3 <-> 4
정렬됨 : [1, 2, 3, 4, 5]

비교: 4 <-> 5
정렬됨 : [1, 2, 3, 4, 5]