버블 정렬

Bubble Sort

버블 정렬(Bubble Sort)은 정렬 알고리즘 중 하나로, 배열을 정렬할 때 인접한 두 요소를 비교하여 교환하는 방식으로 동작한다. 가장 큰 값이 반복적으로 배열의 끝으로 이동하는 모습이 마치 물속에서 거품이 위로 올라가는 것과 비슷하다고 하여 버블 정렬이라는 이름이 붙었다.

---

특징

1. 시간 복잡도:
   • 평균: (O(n^2))
   • 최악: (O(n^2))
   • 최선(이미 정렬된 경우): (O(n))
2. 공간 복잡도: (O(1)) (제자리 정렬, 추가 메모리 필요 없음)
3. 정렬 방식: 안정 정렬 (동일한 값의 순서가 유지됨)
4. 구현의 단순성: 이해와 구현이 매우 쉬운 정렬 알고리즘.

---

동작 원리

1. 배열의 첫 번째 요소부터 시작하여 인접한 두 요소를 비교한다.
2. 두 요소의 순서가 잘못되었다면(오름차순 기준: 앞의 값 > 뒤의 값), 위치를 교환한다.
3. 이 과정을 배열의 끝까지 반복한다. 이를 1회전이라고 한다.
4. 각 회전이 끝날 때 가장 큰 값이 배열의 끝에 위치하게 된다.
5. 배열이 완전히 정렬될 때까지 위 과정을 반복한다.

---

파이썬 코드 구현 예제

다음은 버블 정렬 알고리즘을 구현한 예제이다.

def bubble_sort(arr):
    """
    버블 정렬 알고리즘을 구현한 함수.
    입력: 정렬되지 않은 배열 arr
    출력: 오름차순으로 정렬된 배열
    """
    n = len(arr)  # 배열의 길이를 저장
    for i in range(n - 1):  # 정렬 회전 횟수
        swapped = False  # 이번 회전에서 교환이 발생했는지 체크
        for j in range(n - i - 1):  # 아직 정렬되지 않은 구간 반복
            # 두 인접 요소 비교
            if arr[j] > arr[j + 1]:  # 오름차순 기준으로 잘못된 순서라면
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # 위치 교환
                swapped = True  # 교환 발생 표시
        if not swapped:  # 교환이 발생하지 않았으면 정렬 완료
            break
    return arr

# 테스트
data = [64, 34, 25, 12, 22, 11, 90]
sorted_data = bubble_sort(data)
print("정렬된 배열:", sorted_data)

---

코드 설명

1. 외부 반복문: for i in range(n - 1)은 배열의 크기에서 1을 뺀 만큼 반복한다. 각 회전마다 가장 큰 값이 배열의 끝으로 이동한다.
2. 내부 반복문: for j in range(n - i - 1)은 각 회전에서 아직 정렬되지 않은 구간만큼 비교를 진행한다.
3. 교환 조건: if arr[j] > arr[j + 1]은 현재 요소가 다음 요소보다 클 경우 교환하도록 한다.
4. 최적화: swapped 변수를 통해 교환이 없을 경우 반복을 조기에 종료한다.

---

장단점

장점

• 구현이 매우 간단하다.
• 코드의 직관성이 높아 학습 목적으로 적합하다.

단점

• 비효율적이며, 대규모 데이터에는 적합하지 않다.
• (O(n^2))의 시간 복잡도로 인해 정렬 속도가 느리다.

---

추가 개념

버블 정렬은 단순하면서도 효율적인 최적화를 도입할 수 있다. 예를 들어, 교환이 없으면 반복을 중단하거나, 정렬된 범위를 줄이는 등의 방법이 있다. 이러한 특징 덕분에 알고리즘의 기본 원리를 이해하는 데 유용하다.

---

Reference 책 - Do it! 알고리즘 코딩테스트 with Python