버블 정렬 (Bubble Sort)

버블 정렬(bubble sort)이란 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘이다.

 

직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting

 

https://en.wikipedia.org/wiki/Bubble_sort

 

데이터가 네 개일 때를 예시로 이해해보겠다. 데이터 갯수에 따라 복잡도가 바뀌는 것은 아니므로, 네 개로 로직을 이해할 수 있다.

 

ex) data_list = [1, 9, 3, 2]

• 1차 로직 적용
  • 1과 9 비교, 자리 바꿈 없음 [1, 9, 3, 2]
  • 9와 3 비교, 자리 바꿈 [1, 3, 9, 2]
  • 9와 2 비교, 자리 바꿈 [1, 3, 2, 9]
• 2차 로직 적용
  • 1과 3 비교, 자리 바꿈 없음 [1, 3, 2, 9]
  • 3과 2 비교, 자리 바꿈 [1, 2, 3, 9]
  • 3과 9 비교, 자리 바꿈 없음 [1, 2, 3, 9]
• 3차 로직 적용
  • 1과 2 비교, 자리 바꿈 없음 [1, 2, 3, 9]
  • 2와 3 비교, 자리 바꿈 없음 [1, 2, 3, 9]
  • 3과 9 비교, 자리 바꿈 없음 [1, 2, 3, 9]

 

위 예시를 보면, 데이터 개수가 4개일 때 로직이 3번 적용된 것을 알 수 있다. 그리고 1차 로직을 적용했을 때, 맨 뒤에는 제일 큰 숫자가 확정되었다. 한편, 2차 로직까지 갔을 때 이미 데이터가 정렬된 것을 알 수 있다.

 

버블 정렬의 특징(패턴)을 정리하자면,

• n개의 리스트가 있는 경우 최대 n-1 번의 로직을 적용한다.
• 로직을 1번 적용할 때마다 가장 큰 숫자가 뒤에서부터 1개씩 결정된다.
• 로직이 경우에 따라 일찍 끝날 수도 있다. 따라서 로직을 적용할 때 한 번도 데이터가 교환된 적이 없다면 이미 정렬된 상태이므로 더 이상 로직을 반복 적용할 필요가 없다.

 

https://www.fun-coding.org/00_Images/bubblealgo.png

 

버블 정렬을 코드로 구현하기 위한 plan을 짜보면,

 

1. for num in range(len(data_list)) 반복
2. swap = False (교환이 되었는지를 확인하는 변수를 두는 것)
3. 반복문 안에서, for index in range(len(data_list) - num - 1) 을 한다. n - 1 번 반복해야 하므로.
4. 반복문 안의 반복문 안에서, if data_list[index] > data_list[index + 1] 이면
5. data_list[index], data_list[index + 1] = data_list[index + 1], data_list[index]
6. swap = True
7. 반복문 안에서, if swap == False 이면, break 끝

 

def bubblesort(data):
    for index in range(len(data) - 1):
        swap = False
        for index2 in range(len(data) - index - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True

        if swap == False:
            break
    return data

 

코드는 이렇게 된다. 테스트를 해보면,

 

import random

data_list = random.sample(range(30), 10)

print(data_list)
print(bubblesort(data_list))

 

 

이렇게 잘 정렬되어 출력되는 것을 볼 수 있다.

 

버블 정렬의 경우, 시간 복잡도는 O(n^2) 이다. 반복문이 두 개이기 때문이다. 최악의 경우, n * (n - 1) / 2 이다.

 

완전 정렬이 되어 있는 상태라면 최선은 O(n) 이다.

 

 

 

 

 

[참고자료]

패스트캠퍼스 개발자 취업 합격 패스 With 코딩테스트, 기술면접 초격차 패키지 Online 강의자료