버블 정렬 (Bubble Sort)

버블 정렬(Bubble Sort)은 가장 간단한 정렬 알고리즘 중 하나로, 인접한 두 요소를 비교하여 필요에 따라 자리를 바꾸는 작업을 반복하는 방식으로 리스트를 정렬한다. 이 과정은 리스트가 정렬될 때까지 계속되며, 가장 큰 요소가 "거품"처럼 리스트의 끝으로 이동하는 모습을 보인다.

동작 원리

1. 초기 상태: 리스트의 처음부터 끝까지 반복한다.
2. 인접한 두 요소 비교: 각 반복에서 인접한 두 요소를 비교한다.
3. 교환: 두 요소가 잘못된 순서(오름차순 정렬에서는 앞의 요소가 뒤의 요소보다 클 때)에 있으면 자리를 바꾼다.
4. 반복: 이 과정을 리스트가 완전히 정렬될 때까지 반복한다.

알고리즘 단계

1. 첫 번째 요소와 두 번째 요소를 비교하여 잘못된 순서이면 교환한다.
2. 두 번째 요소와 세 번째 요소를 비교하여 잘못된 순서이면 교환한다.
3. 이 과정을 리스트의 마지막 요소까지 반복한다.
4. 한 번의 전체 순회를 마치면 가장 큰 요소가 리스트의 마지막에 위치하게 된다.
5. 리스트가 정렬될 때까지 이 과정을 반복한다.

예제

다음은 버블 정렬의 동작을 보여주는 예제이다:

정렬할 리스트: [5, 1, 4, 2, 8]

1. 첫 번째 순회:
   • [5, 1, 4, 2, 8] (5와 1 비교, 교환) -> [1, 5, 4, 2, 8]
   • [1, 5, 4, 2, 8] (5와 4 비교, 교환) -> [1, 4, 5, 2, 8]
   • [1, 4, 5, 2, 8] (5와 2 비교, 교환) -> [1, 4, 2, 5, 8]
   • [1, 4, 2, 5, 8] (5와 8 비교, 교환 없음) -> [1, 4, 2, 5, 8]
2. 두 번째 순회:
   • [1, 4, 2, 5, 8] (1과 4 비교, 교환 없음) -> [1, 4, 2, 5, 8]
   • [1, 4, 2, 5, 8] (4와 2 비교, 교환) -> [1, 2, 4, 5, 8]
   • [1, 2, 4, 5, 8] (4와 5 비교, 교환 없음) -> [1, 2, 4, 5, 8]
3. 세 번째 순회:
   • [1, 2, 4, 5, 8] (1과 2 비교, 교환 없음) -> [1, 2, 4, 5, 8]
   • [1, 2, 4, 5, 8] (2와 4 비교, 교환 없음) -> [1, 2, 4, 5, 8]
4. 네 번째 순회:
   • [1, 2, 4, 5, 8] (1과 2 비교, 교환 없음) -> [1, 2, 4, 5, 8]

리스트가 완전히 정렬되었다.

시간 복잡도

버블 정렬의 시간 복잡도는 최선, 평균, 최악의 경우 모두 O(n^2)이다. 최선의 경우에도 모든 요소를 비교해야 하기 때문이다. 이는 비교 기반 정렬 알고리즘 중에서는 효율적이지 않은 편에 속한다.

공간 복잡도

버블 정렬은 제자리 정렬(in-place sorting) 알고리즘으로, 추가적인 메모리를 거의 사용하지 않기 때문에 공간 복잡도는 O(1)이다.

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

arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array is:", arr)

버블 정렬은 간단하고 이해하기 쉬운 정렬 알고리즘이지만, 효율성 면에서는 다른 정렬 알고리즘에 비해 낮은 편이다. 작은 데이터 세트나 학습 목적에는 유용하지만, 큰 데이터 세트에는 퀵 정렬(Quick Sort)이나 병합 정렬(Merge Sort) 같은 더 효율적인 알고리즘을 사용하는 것이 좋다.

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms