27. 파이썬 - 거품 정렬(버블 소팅 bubble sorting)

다양한 소팅을 애니메이션으로 보여줍니다. 볼만합니다. 

 

https://www.toptal.com/developers/sorting-algorithms

Sorting Algorithm Animations

미리 알아야할 지식

파이썬에서는 2개의 변수의 값을 교환할 때 

a, b = b, a를 쓸 수 있습니다. 

 

다른 프로그래밍 언어에서는 temp를 동원해서

temp = a

a = b

b = temp 

를 사용하는 것에 비해 상당히 간편합니다. 

 

무식한 정렬법

다들 처음 정렬을 배울 때 이런 식의 무식한 정렬 알고리듬 하나씩 만들어보죠?

효율은 '전혀' 신경 쓰지 않고 하나하나 모두 비교하는 방식입니다. 

 

def fool_sort(array):
    """무식 정렬"""

    for outer in range(len(array)):
        for inner in range(len(array)):
            if array[outer] < array[inner]:
                array[inner], array[outer] = array[outer], array[inner]
            print(outer, inner, array)


fool_sort([8, 5, 2, 4, 6])

 

0 0 [8, 5, 2, 4, 6]
0 1 [8, 5, 2, 4, 6]
0 2 [8, 5, 2, 4, 6]
0 3 [8, 5, 2, 4, 6]
0 4 [8, 5, 2, 4, 6]
1 0 [5, 8, 2, 4, 6]
1 1 [5, 8, 2, 4, 6]
1 2 [5, 8, 2, 4, 6]
1 3 [5, 8, 2, 4, 6]
1 4 [5, 8, 2, 4, 6]
2 0 [2, 8, 5, 4, 6]
2 1 [2, 5, 8, 4, 6]
2 2 [2, 5, 8, 4, 6]
2 3 [2, 5, 8, 4, 6]
2 4 [2, 5, 8, 4, 6]
3 0 [2, 5, 8, 4, 6]
3 1 [2, 4, 8, 5, 6]
3 2 [2, 4, 5, 8, 6]
3 3 [2, 4, 5, 8, 6]
3 4 [2, 4, 5, 8, 6]
4 0 [2, 4, 5, 8, 6]
4 1 [2, 4, 5, 8, 6]
4 2 [2, 4, 5, 8, 6]
4 3 [2, 4, 5, 6, 8]
4 4 [2, 4, 5, 6, 8]

정렬은 잘 됩니다만, 불필요한 비교가 많이 일어나죠?

버블 소팅

 

버블 소팅은 이러한 반복을 줄이기 위해서 
배열 내에서 앞 뒤 요소를 비교하고
만약 교환이 필요하다면 교환해줍니다. 

 

이때 작은(가벼운) 숫자가 한쪽으로 움직이는 것이
마치 거품이 위로 올라오는 것 처럼 보인다
해서 버블 정렬입니다. 

def bubble_sort(array):
    """버블 정렬"""

    for outer in range(len(array) - 1):
        for inner in range(len(array) - outer - 1):
            if array[inner] > array[inner + 1]:
                array[inner], array[inner + 1] = array[inner + 1], array[inner]
            print(outer, inner, inner + 1, array)


bubble_sort([8, 5, 4, 6, 2])

0 0 1 [5, 8, 4, 6, 2]
0 1 2 [5, 4, 8, 6, 2]
0 2 3 [5, 4, 6, 8, 2]
0 3 4 [5, 4, 6, 2, 8]
1 0 1 [4, 5, 6, 2, 8]
1 1 2 [4, 5, 6, 2, 8]
1 2 3 [4, 5, 2, 6, 8]
2 0 1 [4, 5, 2, 6, 8]
2 1 2 [4, 2, 5, 6, 8]
3 0 1 [2, 4, 5, 6, 8]

2의 움직임을 보면 버블을 느낄 수 있습니다.