Bubble Sort (버블 정렬)

✅ Bubble Sort (버블 정렬)

평균 시간복잡도 : O(n2)

 

버블 정렬(Bubble Sort)은 가장 간단한 정렬 알고리즘 중 하나로, 주어진 리스트에서 인접한 두 원소를 비교하고 교환하면서 정렬하는 방식입니다. 이름 그대로 버블(bubble)처럼, 가장 큰 수가 차례차례 리스트의 끝으로 "떠오르는" 모습을 비유하여 붙여졌습니다.

항목	설명
알고리즘 유형	비교 기반 정렬
시간 복잡도	최악: O(n^2) 최선: O(n) 평균: O(n^2)
공간 복잡도	O(1)
안정성	안정적인 정렬
적용	데이터가 적고, 이미 정렬된 경우 최적화 가능
단점	큰 데이터에서 비효율적, O(n2)O(n^2)O(n2) 시간 복잡도

 

✅버블정렬 특징

버블 정렬의 동작 원리는 크게 반복문을 통한 비교와 교환으로 이루어집니다. 각 단계에서 가장 큰 수가 리스트의 끝으로 "떠오르는" 방식입니다. 이를 아래와 같이 단계별로 정리할 수 있습니다:

1. 첫 번째 반복:
   • 리스트의 첫 번째 원소부터 끝까지 순차적으로 비교합니다.
   • 인접한 두 원소가 잘못된 순서라면 교환합니다.
   • 이 과정이 끝나면 가장 큰 값이 맨 뒤로 이동합니다.
2. 두 번째 반복:
   • 마지막 원소는 이미 정렬되었으므로, 그 전까지의 원소들을 비교합니다.
   • 다시 인접한 두 원소를 비교하고 교환합니다.
   • 이번 반복 후 두 번째로 큰 값이 마지막에서 두 번째 위치로 이동합니다.
3. 반복을 계속 진행:
   • 매번 비교할 범위가 줄어들면서, 남은 원소들을 정렬합니다.
   • 이 과정을 반복하면서 나머지 원소들이 정렬됩니다.
4. 정렬 완료:
   • 리스트가 완전히 정렬되면 반복문이 끝납니다.

 

✅버블 정렬의 동작 원리

버블 정렬은 인접한 두 원소를 비교하여 큰 값을 뒤로 보내는 방식으로 정렬하는 알고리즘입니다. 이를 "버블"처럼, 큰 값이 점차적으로 뒤로 떠오른다고 비유할 수 있습니다. ( 단 조건문에 따라 다르다. by. 규리 )

1. 배열의 첫 번째 원소부터 차례대로 비교합니다.
   • 두 원소가 순서대로 정렬되지 않으면 그 두 값을 교환합니다.
   • 교환된 값은 배열의 끝으로 밀려가면서 계속 "버블처럼 떠오릅니다."
2. 배열의 마지막까지 진행되면 가장 큰 값이 뒤로 이동하여 올바른 위치를 차지합니다.
3. 반복을 통해 두 번째 큰 값은 그 전까지 정렬된 부분을 제외한 배열에서 버블처럼 떠오르며 자리를 잡습니다. 이 과정을 계속 반복하여 전체 배열이 정렬됩니다.

---

✅ 이해를 돕기 위한 코드

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        print(f"반복 {i+1}: {arr}")  # 각 반복 후 배열 출력
        for j in range(0, n-i-1):  # 뒤에서부터 비교해서 큰 값을 끝으로 보냄
            if arr[j] > arr[j+1]:
                # 교환
                arr[j], arr[j+1] = arr[j+1], arr[j]
            print(f"  비교 {j+1}: {arr}")  # 각 비교 후 배열 상태 출력
    return arr

# 예시 배열
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("\n최종 정렬된 배열:", sorted_arr)

 

반복 1: [64, 34, 25, 12, 22, 11, 90]
  비교 1: [34, 64, 25, 12, 22, 11, 90]
  비교 2: [34, 25, 64, 12, 22, 11, 90]
  비교 3: [34, 25, 12, 64, 22, 11, 90]
  비교 4: [34, 25, 12, 22, 64, 11, 90]
  비교 5: [34, 25, 12, 22, 11, 64, 90]
  비교 6: [34, 25, 12, 22, 11, 64, 90]
반복 2: [34, 25, 12, 22, 11, 64, 90]
  비교 1: [25, 34, 12, 22, 11, 64, 90]
  비교 2: [25, 12, 34, 22, 11, 64, 90]
  비교 3: [25, 12, 22, 34, 11, 64, 90]
  비교 4: [25, 12, 22, 11, 34, 64, 90]
  비교 5: [25, 12, 22, 11, 34, 64, 90]
반복 3: [25, 12, 22, 11, 34, 64, 90]
  비교 1: [12, 25, 22, 11, 34, 64, 90]
  비교 2: [12, 22, 25, 11, 34, 64, 90]
  비교 3: [12, 22, 11, 25, 34, 64, 90]
  비교 4: [12, 22, 11, 25, 34, 64, 90]
반복 4: [12, 22, 11, 25, 34, 64, 90]
  비교 1: [12, 22, 11, 25, 34, 64, 90]
  비교 2: [12, 11, 22, 25, 34, 64, 90]
  비교 3: [12, 11, 22, 25, 34, 64, 90]
반복 5: [12, 11, 22, 25, 34, 64, 90]
  비교 1: [11, 12, 22, 25, 34, 64, 90]
  비교 2: [11, 12, 22, 25, 34, 64, 90]
최종 정렬된 배열: [11, 12, 22, 25, 34, 64, 90]