[Algorithm] 버블 정렬

※버블 정렬이란?

 

인접한 데이터 간에 비교를 통해 교환하는 방식의 정렬

 

아래의 데이터 셋을 버블 정렬로 정렬해보자.

 

 

[ 5, 10, 1, 8, 7, 6, 4, 3, 2, 9 ] 

 

 

첫 번째 정렬 후 : [ 5 , 1 , 8 , 7 , 6 , 4 , 3 , 2 , 9 ,10 ]

두 번째 정렬 후 : [ 1 , 5 , 7 , 6 , 4 , 3 , 2 , 8 , 9 , 10 ]

세 번째 정렬 후 : [ 1 , 5 , 6 , 4 , 3 , 2 , 7 , 8 , 9 , 10 ]

---

 

버블 정렬 또한 총 10번의 정렬 과정을 거쳐 오름차순으로 정렬된다.

 

 

파이썬 코드로 구현한 버블 정렬은 다음과 같다.

 

👩🏻‍💻Python Code👩🏻‍💻

 

data_set = [5,10,1,8,7,6,4,3,2,9]

for i in range(len(data_set)):
    for j in range(9-i):
        if(data_set[j]>data_set[j+1]):
            temp = data_set[j]
            data_set[j] = data_set[j+1]
            data_set[j+1] = temp

data_set

그렇다면 버블 정렬의 시간복잡도는 얼마일까?

 

데이터 셋 내 데이터의 개수가 10개라고 가정하자. 각 케이스별로 수행하는 비교 연산은

 

첫 번째 케이스 : 10번

두 번째 케이스 : 9번

세 번째 케이스 : 8번

---

이므로 10+9+8+7+6+5+4+3+2+1번의 비교 연산을 수행한다. 이는 등차수열로 N개의 데이터가 있을 때, 총 수행하는 비교 연산은 N(N+1)/2번이다.

이는 빅오표기법으로 O(N*2)이다. 

 

버블 정렬과 선택 정렬의 시간 복잡도는 동일하지만 실제 수행 시간은 버블 정렬이 더 오래 걸려 비효율적이다. 그 이유는 버블 정렬은 비교 연산 후 매번 교체를 해줘야하기 때문이다. 선택 정렬의 경우 비교 연산 후 가장 작은 값을 찾아 마지막에만 교체를 진행하지만 버블 정렬은 인접한 값들을 비교 후 조건이 맞으면 교체를 진행하기 때문에 실제 수행 시간이 더 길다.