[python] 알고리즘 - 거품 정렬(Bubble Sort)

버블 소트(Bubble Sort)

출처: https://visualgo.net/en

버블 소트는 배열에서 차례대로 두 데이터들을 비교한다. 이때 앞에 있는 숫자가 뒤에 있는 숫자보다 크다면 자리를 교체한다. 큰 숫자가 차례차례 뒤로 넘어가는 구조다.

 

한번의 순회가 끝나면 다시 처음부터 값들을 비교한다. 이를 반복하는 것이다. 특징으로는 한번 루틴을 돌 때 마다 가장 큰 값이 뒤로 가므로 비교해야 할 횟수가 줄어든다.

 

위 이미지에서는 최대 순회 횟수를 채우기 전에 데이터가 모두 정렬됐다. 즉 중간에 더 이상 비교할 필요가 없어졌다. 따라서 소스 코드 내에서 swap이라는 불리언 값을 주었다. 만약 한번의 순회를 거치는 동안 데이터간의 교체가 있는지 없는지를 체크하는 것이다. 교체가 없다면 정렬이 끝났다는 것이므로 반복문을 종료한다.

 

아래 코드에서 첫번째 루프의 a는 최대 루틴 횟수이다.

#Bubble Sort
def bubbleSort(array):
    for a in range(len(array) - 1):
        swap = False
        for b in range(len(array) - a - 1):
            if array[b+1] < array[b]:
                array[b+1], array[b] = array[b], array[b+1]
                swap = True
        if swap == False:
            break
    return array
    
#Test Code
import random
data = random.sample(range(100), 10)
print(data)
print(bubbleSort(data))