[알고리즘 이론] 거품 정렬, 거품 정렬 개선하기

구현

def bubbleSortAsc(arr, n):
    for idx in range(n-1, -1, -1):
        for jdx in range(idx):
            if arr[jdx] > arr[jdx+1]:
                arr[jdx], arr[jdx+1] = arr[jdx+1], arr[jdx]
    return arr

def bubbleSortDesc(arr, n):
    for idx in range(n-1, -1, -1):
        for jdx in range(idx):
            if arr[jdx] < arr[jdx+1]:
                arr[jdx], arr[jdx+1] = arr[jdx+1], arr[jdx]
    return arr

arr = [2, 7, 5, 1, 4, 6, 3]
sortedArrAsc = bubbleSortAsc(arr, len(arr))
print(sortedArrAsc)
sortedArrDesc = bubbleSortDesc(arr, len(arr))
print(sortedArrDesc)

시간복잡도

• 시간 복잡도는 O(n2)

특징

• 전통적인 거품 정렬이 뒤에서부터 시작하는 이유는, 각 반복마다 가장 큰(또는 가장 작은) 요소가 "거품처럼" 배열의 끝으로 이동하게 되기 때문이다. 이 방식은 단순하며, 각 반복 후에 마지막 요소(들)이 이미 정렬된 상태라는 점을 활용하여 다음 반복에서 그 부분을 제외할 수 있다. 이는 알고리즘의 효율성을 조금이나마 개선할 수 있는 방법이다.

거품 정렬 개선하기

def bubbleSortUpgrade(arr, n):
    end = n - 1
    while end > 0:
        last_swap = 0
        for i in range(end):
            if arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                last_swap = i
            end = last_swap
    return arr

특징

• 배열의 뒷부분이 이미 정렬되어 있다면, 이 알고리즘은 그 부분을 다시 검사하지 않는다. 따라서, 전체적인 비교 횟수와 교환 횟수가 줄어들어, 실행 시간이 단축된다. 하지만 여전히 시간복잡도는 O(n2)이다.