거품 정렬 (Bubble sort)

방학도 했겠다, 정렬 알고리즘을 다뤄보고자 한다.

지난 시간 잠깐씩 다뤘던 것들까지 수정할 수 있으면 다같이 정리해보고 싶다. 기초적인 알고리즘들부터 다루면 어떨까 싶다. 사람들한테 제일 친숙한건 Selection, Insertion 정도일텐데 Bubble부터 다루는게 된 이유는 딱히 없다. 그냥 제일 자주 쓰기도 하고, 편해서...

---

사람 손은 두 개다. 양 손에 집어든 물건의 대소 비교를 진행할 수 있다.이번 정렬도 딱 그 컨셉으로 진행된다. Bubble이라고 만든 것은 서로 이웃한 item 두 개를 비교하면서 큰 것과 작은 것을 분류해가는 정렬이다.

정렬되지 않은 list 가 있을 때, index가 가장 낮은 두 item을 Bubble로 만든다. 더 큰 것을 더 큰 index를 가지도록 서로 순서를 바꾸거나 바꾸지 않는 작업을 반복하면서 list를 순회한다. 반복이 한 번 종료되면 가장 큰 item은 가장 큰 index를 가지게 될 것이다. 이제 list 길이 상한을 하나씩 줄여가면서 여러 번 반복하면 전체 list는 정렬된다.

전체 list 길이가 n이라고 하면 n-1 번 순회, n-2 번 순회, ... , 1번 순회 하는 과정을 반복하게 된다.

따라서 시간 복잡도를 가진다.

def bsort(arr):
    length = len(arr)
    flag = False                # initialize
    # flag is not necessary but it's useful when the list is almost sorted.
    while length > 0 and not flag:
        flag = True             # Is the array sorted?
        length -= 1
        for j in range(length):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                flag = False    # the array is not sorted
    return arr

flag는 Bubble Sort의 단점을 조금 보강하기 위해 넣은 것이다.

Bubble Sort는 이미 정렬된 list에 적용시켜도, 반복 연산을 진행하게 된다. 이러한 의미없는 반복을 줄이기 위해서 이미 정렬됐는지를 확인하는 용도로 flag를 만든 것이다. 어떤 상황이든 list 순회를 진행했는데 단 한 번도 swap이 일어나지 않았다면 이미 그 list는 정렬된 것이다. 따라서 알고리즘을 종료하면 된다.