버블 정렬

버블 정렬 알고리즘은 입력된 배열에서 인접한 두 원소를 계속해서 비교하면서 큰 원소를 뒤로 이동시켜가며 정렬하는 알고리즘입니다.

 

이 알고리즘을 파이썬 코드로 구현하면, 우선 입력으로 받은 배열을 순회하면서 인접한 두 원소를 비교합니다. 만약 뒤의 원소가 더 작다면 두 원소의 위치를 서로 교환합니다. 이 과정을 배열의 모든 원소가 정렬될 때까지 반복합니다.

예를 들어, [3, 1, 5, 2, 4]라는 배열이 있다면, 우선 3과 1을 비교합니다. 1이 더 작으므로 두 원소를 교환하여 [1, 3, 5, 2, 4]가 됩니다. 이후 3과 5를 비교하면서 뒤의 원소가 더 크기 때문에 교환이 일어나지 않습니다. 이와 같은 방식으로 모든 원소를 비교하면서 정렬을 완료합니다. 이렇게 구현된 버블 정렬 알고리즘은 입력 배열의 크기가 작을 경우에는 적절한 성능을 보이지만, 배열의 크기가 커지면 시간 복잡도가 증가하여 느려질 수 있습니다.

 

파이썬 소스 코드는 다음과 같습니다.

def bubble_sort(bubbleArr):
    n = len(bubbleArr)
    
    # 모든 원소를 순회하며 비교
    for i in range(n):
        for j in range(0, n-i-1):
            # 인접한 두 원소를 비교하고 필요하면 교환
            if bubbleArr[j] > bubbleArr[j+1]:
                bubbleArr[j], bubbleArr[j+1] = bubbleArr[j+1], bubbleArr[j]
    
    return bubbleArr

 

If 문을 자세히 보면,

# 인접한 두 원소를 비교하고 필요하면 교환
if bubbleArr[j] > bubbleArr[j+1]: 
    # 현재 원소가 다음 원소보다 큰 경우
    # 두 원소의 위치를 서로 교환한다.
    bubbleArr[j], bubbleArr[j+1] = bubbleArr[j+1], bubbleArr[j]

 

시간 복잡도

버블 정렬의 최선, 평균, 최악의 시간 복잡도는 모두 O(n^2)입니다. 이는 배열의 크기가 n일 때, 인접한 모든 쌍을 비교하므로 n * (n-1) / 2 번의 비교를 수행하기 때문입니다.

공간 복잡도
버블 정렬의 공간 복잡도는 O(1)입니다