[자료구조] 버블 정렬 concept, 분석

내부 정렬 중 버블정렬은, 인접한 두개의 원소를 비교하여 자리를 교환하는 방식이다. 첫번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬되게 된다. (마지막으로 배열되는 원소는 비교를 끝까지 진행하므로!) 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물 속에서 물 위로 올라오는 물방울 모양과 같다고 하여 bubble 정렬이라 지어졌다고 한다.

 

버블 정렬의 경우, 선택 정렬과 달리 best case와 worst case로 나누어 보아야 한다. best case는 이미 정렬이 완료된 상태로, 비교만 진행하고 자리 교환은 이루어지지 않아도 된다. worst case는 자리 교환이 이루어져야 하기 때문에 시간이 더 필요하다.

 

그러나 두 경우 모두 big-oh notation으로 표현하였을 때의 시간복잡도는 같다(O(N^2)로)

 

[python 코드] 

 

def bubble_sort(arr):
    n = len(arr)

    # 모든 원소에 대해 반복
    for i in range(n):
        # 각 패스에서 가장 큰 원소를 배열의 끝으로 보내기
        for j in range(0, n - i - 1):
            # 현재 원소가 다음 원소보다 크면 교환
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

# 예시
my_array = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(my_array)

print("정렬된 배열:", my_array)