버블 정렬(Bubble Sort)

버블 정렬은 단순 정렬(simple sort)중 하나로 알려져있으며 매우 기본적인 정렬 알고리즘이지만 더욱 빠르다고 알려진 정렬 알고리즘보다 비효율적이다. 버블 정렬 예제를 살펴보자.

 

먼저 [ 6, 3, 1, 2, 4, 5 ] 이라는 배열을 정렬하고 싶다고 가정하자.

 

1loop [ 6, 3, 1, 2, 4, 5 ] 먼저 6과 3을 비교하여 순서가 맞지 않음을 확인하고 6과 3을 교환한다. [3, 6, 1, 2, 4, 5 ] 그다음으로 6과 1을 비교하여 순서가 맞지 않음을 확인하고 6과 1을 교환한다. [3, 1, 6, 2, 4, 5 ] [3, 1, 2, 6, 4, 5 ] [3, 1, 2, 4, 6, 5 ] 1loop result = [3, 1, 2, 4, 5, 6 ]

 

이렇게하여 1loop가 끝난다.

 

2loop [3, 1, 2, 4, 5, 6 ] [1, 3, 2, 4, 5, 6 ] [1, 2, 3, 4, 5, 6 ] [1, 2, 3, 4, 5, 6 ] 2loop result = [1, 2, 3, 4, 5, 6]

 

완전히 정렬이 되었지만 실제로는 정렬 되지 않았다고 가정하고 끝까지 비교 해보자.

 

3loop [1, 2, 3, 4, 5, 6] [1, 2, 3, 4, 5, 6] [1, 2, 3, 4, 5, 6] 3loop result = [1, 2, 3, 4, 5, 6] 4loop result = [1, 2, 3, 4, 5, 6] 5loop result = [1, 2, 3, 4, 5, 6] 6loop result = [1, 2, 3, 4, 5, 6]

 

아마도 끝까지 비교해보면 감이 올것이다.

 

버블 정렬 알고리즘은 두 가지 중요한 단계가 있다.

• 비교(comparison): 어느 쪽이 더 큰지 두 수를 비교한다.
• 교환(swap): 정렬하기 위해 두 수를 교환한다.

 

만약 위 예제와 같이 배열의 원소가 6개이며 전부 교환을 한다고 가정한다면

• 비교는 5 + 4 + 3 + 2 + 1 = 15번의 비교가 필요하다.
• 교환 또한 5 + 4 + 3 + 2 + 1 = 15번의 교환이 빌교하다.
• 15번의 비교와 15번의 교환이 필요하니 총 30단계가 필요한 셈이다.

 

따라서 6^2 = 36 이므로 시간복잡도는 O(N2)라고 볼 수 있다.

 

버블 정렬을 파이썬 코드로 구현을 해보았다.

 

def BubbleSort(array):
    
    unsorted_index = len(array)-1
    sorted = False
    
    while not sorted:
        sorted = True
        
        for i in range(unsorted_index):
      
            if(array[i] > array[i+1]):
                array[i], array[i+1] = array[i+1], array[i]
                sorted = False
        
        unsorted_index -= 1

    return array

 

코드를 하나씩 살펴보자.

 

unsorted_index = len(array)-1
sorted = False

 

가장먼저 정렬되지 않은 배열의 가장 오른쪽 인덱스를 기록하는 변수 unsorted_index를 생성한 후

배열의 정렬 여부를 기록하는 sorted 변수도 생성한다.

 

while not sorted:
	sorted = True

 

배열이 정렬될 때까지 계속 실행될 while 루프를 시작한다. while루프 한 번의 실행이 배열의 한 loop에 해당한다.

이어서 sorted에 True를 할당해준다.

 

각 패스스루 안에서는 교환이 일어나기 전까지 배열이 정렬되어 있다고 가정하고 값을 교환하면 변수를 다시 False로 바꾸는 방식으로 취한다. 이렇게 해야 어떤 교환도 하지 않고 전체 loop를 통과할 때 sorted가 True로 남아서 배열이 완전히 정렬된 상태를 반환할 수 있다.

 

for i in range(unsorted_index):

 

for 루프를 시작한다. 루프안에서 배열 내 모든 내 모든 값 쌍을 가리킨다. 변수i를 첫포인터로 사용해 배열의 첫인덱스부터 unsorted_index까지 비교한다.

 

if list[i] > list[i+1]:
	list[i], list[i+1] = list[i+1], list[i]
    sorted = False

 

for 루프 내에서 i와 i+1 값을 비교해 순서가 올바르지 않으면 교환한다. 교환하게 되면 sorted를  False로 바꾼다.

각 패스스루가 끝나면 오른쪽으로 올려준 버블이 이제 올바른 위치에 있음을 알 수 있다.

 

unsorted_index -= 1

 

기존에 가리키던 인덱스가 (1loop에서는 마지막 인덱스) 정렬된 상태이니 unsorted_index 값을 1 감소시킨다.

 

return list

 

sorted가 True가 되면 정렬된 배열을 반환한다.

 

---

공부하면서 더욱 자세히 보았던 부분이 있다. 처음에 sorted 변수를 True값을 주고 for 안에 if문이 성립되면 False를 주는 부분은 for문안에서 모든 배열을 한번씩 순환하기 때문에 정렬이 이미 되어있다면 if문이 성립 되지 않기 때문에 바로 list를 반환하는 부분에서 효율성이 괜찮다는 것에 감탄하였다. 

버블은 비눗방울이나 거품을 뜻하는데 제일 큰 값을 비눗방울 처럼 둥둥 떠나보낸다는 느낌이랄까 더욱 상상력이 풍부해진 느낌이다.

---