알고리즘 이론 - 거품 정렬

거품 정렬(Bubble Sort)

• 거품 정렬은 현재 인덱스와 다음 인덱스의 크기를 비교해 다음 수가 크다면, 그대로 두고 다음 수가 현재 인덱스보다 작으면, 값의 위치를 바꾸는 정렬 방법이다.

위에 그림에서 알 수 있듯이 자리를 바꿔나가는 작업을 1회 수행하면 가장 큰 값이 배열의 끝에 위치한다. 이를 반복 작업해서 차례로 다음으로 큰 수를 정렬해나가는 방법이다. 최대값을 구하는 방식하고 유사해보인다.

버블 정렬의 기본 틀

# 버블 정렬
def bubbleSort(arr):
    # 배열의 크기만큼 반복
    for i in range(len(arr)):        
        # 배열의 총 크기에서 i와 1을 뺀 만큼 반복. 그 이유는 j의 현재 인덱스가 arr의 마지막 인덱스가 되면 j와 j+1을 비교할 때, indexOutofRange 이기 때문이다.
        for j in range(0, len(arr) - i - 1):
            # 만약 현재 인덱스의 값이 다음 인덱스보다 크면, 서로의 위치를 바꿈.
            if arr[j] > arr[j + 1]: 
                arr[j], arr[j + 1] = arr[j + 1], arr[j]




arr_bubble = [4, 7, 80, 50, 30, 40, 20, 10]

bubbleSort(arr_bubble)
print(arr_bubble)

*참고로 내림차순으로 정렬하려면 다음 인덱스가 작도록 부등호만 바꿔주면 된다.

*버블 정렬은 사용하기 편하지만 이중 반복문으로 리스트의 모든 값을 순회하므로 시간복잡도가 O(N^2)이다. 효율이 좋은 정렬 방법은 아니다.