버블 정렬은 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다. 버블 정렬은 인접한 원소들의 비교를 반복하며, 정렬이 완료될 때까지 반복적으로 수행됩니다. 이 알고리즘은 간단하지만 성능이 좋지 않아서 큰 데이터셋에는 적합하지 않습니다.

버블 정렬 알고리즘 구현

def bubble_sort(arr):
    n = len(arr)
    
    for i in range(n-1):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    
    return arr

위 코드는 파이썬으로 버블 정렬 알고리즘을 구현한 예시입니다. 주어진 리스트 arr을 인자로 받아서 정렬된 리스트를 반환합니다.

예시 동작

아래는 주어진 입력 리스트 [5, 2, 9, 1, 3]를 버블 정렬로 정렬하는 예시입니다.

arr = [5, 2, 9, 1, 3]
sorted_arr = bubble_sort(arr)
print(sorted_arr)

출력 결과는 [1, 2, 3, 5, 9]가 됩니다.

시간 복잡도

버블 정렬의 시간 복잡도는 최선, 평균, 최악 모두 O(n^2)입니다. 이는 이중 반복문을 사용하기 때문입니다. 따라서 큰 데이터셋에서는 다른 정렬 알고리즘을 사용하는 것이 더 효율적입니다.

마무리

버블 정렬은 간단한 알고리즘이지만 성능이 좋지 않아서 실제로는 잘 사용되지 않습니다. 성능을 높이기 위해서는 다른 정렬 알고리즘을 선택하는 것이 좋습니다.