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

정렬 알고리즘 중에서 가장 직관적이고 간단한 버블 정렬에 대해 알아보자. 그리고 버블 정렬이 어떻게 동작하는지 배우고 이를 코드로 구현해 보자.

 

📌 정의

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed.
가라앉는 정렬이라고도 불리는 버블(거품) 정렬은, 입력된 리스트의 요소 별로, 현재 요소를 바로 다음의 요소와 비교를 하는데, 필요에 따라 서로의 값을 교환하는 비교하는 과정을 반복하는 간단한 정렬 알고리즘이다.

Bubble Sort - Wikipedia 

 

📌 동작 과정

버블 정렬은, 쉽게 말하면 가장 큰 값이 맨 끝으로 정렬되어 가는 알고리즘이다.

 

버블 정렬 애니메이션, 가장 큰 숫자가 위에서부터 정렬 되기에 거품이 가라앉는 것처럼 보인다.

이름이 버블 정렬인 이유는 크게 2가지인 것으로 보인다.

1. 가장 큰 값부터 정렬 되기에, 정렬된 데이터가 거품처럼 가라앉는 것처럼 보인다. (위의 gif)
2. 반복할 때마다 가장 큰 값이 맨 끝으로(가장 오른쪽으로) 점차 이동하는데, 거품이 위로 올라가는 것처럼 보인다. (아래의 gif)

 

빨간색 박스는 현재 위치와 그 오른쪽의 데이터를 의미하고, 검은색 박스는 정렬이 완료된 데이터를 의미한다.

버블 정렬의 동작 과정, 반복을 할 때마다 크기가 가장 큰 숫자가 순차적으로 맨 오른쪽으로 자리잡는다.

 

📌 코드 in Python

자, 이제 원리를 알았으니 코드로 구현해 보자. 아래의 1~2번에 의해 이중 반복문으로 작성되어야 한다.

1. 인접한 두 요소를 순차적으로 비교해야 하므로 반복문을 한번 돌아야 한다.
2. 1번을 마치면, 다시 처음 비교한 위치로 돌아가서 또다시 1번 과정을 반복하는 과정이 필요한다. 따라서 반복문이 하나 더 필요하다. 단, 비교의 범위는 방금 정렬된 데이터의 직전까지 해야 조금 더 효율적으로 동작할 수 있다.
3. 1번에서 만약 왼쪽의 요소가 오른쪽의 요소보다 클 경우 두 요소를 서로 교환한다.

# 버블 정렬 함수 정의
def bubble_sort(array):
    # 배열의 길이를 변수 n으로 할당
    n = len(array)

    # 배열의 길이만큼 반복
    for i in range(n):

        # 배열의 길이에서 i와 1을 뺀만큼 반복
        for j in range(0, n - i - 1):

            # 만약 현재 위치의 값이 다음 위치의 값보다 클 경우 서로를 교환
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]

# 테스트 코드
if __name__ == "__main__":
    # 예시 리스트를 할당
    array = [6, 5, 3, 1, 8, 7, 2, 4]

    # 예시 리스트를 인수로 하여, 버블 정렬 함수를 실행
    bubble_sort(array)

    # 정렬된 리스트의 요소를 차례대로 출력
    for element in array:
        print(element, end=" ")  # 1 2 3 4 5 6 7 8

# 처음의 리스트
[6, 5, 3, 1, 8, 7, 2, 4]

# 반복문을 지나면서 버블 정렬이 되어 가는 리스트
[5, 6, 3, 1, 8, 7, 2, 4]
[5, 3, 6, 1, 8, 7, 2, 4]
[5, 3, 1, 6, 8, 7, 2, 4]
[5, 3, 1, 6, 8, 7, 2, 4]
[5, 3, 1, 6, 7, 8, 2, 4]
[5, 3, 1, 6, 7, 2, 8, 4]
[5, 3, 1, 6, 7, 2, 4, 8]
[3, 5, 1, 6, 7, 2, 4, 8]
[3, 1, 5, 6, 7, 2, 4, 8]
[3, 1, 5, 6, 7, 2, 4, 8]
[3, 1, 5, 6, 7, 2, 4, 8]
[3, 1, 5, 6, 2, 7, 4, 8]
[3, 1, 5, 6, 2, 4, 7, 8]
[1, 3, 5, 6, 2, 4, 7, 8]
[1, 3, 5, 6, 2, 4, 7, 8]
[1, 3, 5, 6, 2, 4, 7, 8]
[1, 3, 5, 2, 6, 4, 7, 8]
[1, 3, 5, 2, 4, 6, 7, 8]
[1, 3, 5, 2, 4, 6, 7, 8]
[1, 3, 5, 2, 4, 6, 7, 8]
[1, 3, 2, 5, 4, 6, 7, 8]
[1, 3, 2, 4, 5, 6, 7, 8]
[1, 3, 2, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]

반복문을 지나면서 최댓값이 점점 오른쪽으로 정렬되어 가는 걸 볼 수 있다.