TIL - 버블 정렬 Bubble Sort

문제

인접한 두 원소를 비교하여 정렬하는 방식이다.

가장 큰 원소가 배열 끝으로 버블 처럼 이동한다.

 

버블 정렬을 쉽게 이해하기 위한 아티팩트를 생성했다.

bubble_sort_visualizer.html

0.01MB

 

 

문제풀이

def bubble_sort(arr):
    for i in range(n-1): # 외부 반복문은 n-1 까지 돈다.
        for j in range(0, n-i-1): # 외부 반복문 이후의 항목만 진행
            if arr[j] > arr[j+1]:
                arr[j+1], arr[j] = arr[j], arr[j+1]
                
        
    return arr

 

외부 반복문은 n-1 까지만 돌고, 가장 마지막은 범위에서 제외한다. (어차피 j+1 값이랑 바뀌기 때문)

내부 반복문은 0 부터 정렬된 부분을 제외하고 n - i - 1 까지 돈다. 

 

앞 인덱스의 값이 뒷 값보다 크면 서로 위치를 교체한다. 파이썬에서는 아래와 같은 방식으로 교체가 가능하다.

arr[j+1], arr[j] = arr[j], arr[j+1]

 

 

 

최적화된 버블 정렬

def bubble_sort_optimized(arr):
    n = len(arr)
    
    for i in range(n):
        swapped = False  # 교환 발생 여부
               
        for j in range(0, n - i - 1):
            if arr[j] > arr[j+1]:
                arr[j+1], arr[j] = arr[j], arr[j+1]
                swapped = True

        if not swapped :
            break
    return arr

 

swapped 변수를 추가하여 교환이 더이상 발생하지 않는다면 바로 반복문을 종료하도록 코드가 추가되었다. 

 

 

 

어려웠던 점

1. 버블 정렬은 많이 해봤던 것 같은데 다시 보니 헷갈려서 개념부터 다시 정리했다. 클로드 아티팩트로 시각화한게 도움이 되었다.
2. swapped 변수를 클로드에서 먼저 스포당해버려서 구현 후에 이해했다.