파이썬 버블정렬

버블정렬이란?

버블 정렬은 인접한 두 원소를 비교하고, 정렬 기준에 따라 그 위치를 바꾸는 방식으로 작동하는 정렬 알고리즘입니다. 리스트의 맨 끝에서부터 가장 큰(또는 가장 작은) 원소가 거품처럼 '떠오르는' 것처럼 보여서 '버블(거품) 정렬'이라는 이름이 붙었습니다.

작동 원리

버블 정렬은 다음 단계를 반복합니다.

1. 첫 번째 원소와 두 번째 원소를 비교합니다.
   • 첫 번째 원소가 더 크면(오름차순 기준), 두 원소의 위치를 바꿉니다.
   • 그렇지 않으면 그대로 둡니다.
2. 두 번째 원소와 세 번째 원소를 비교합니다. 위와 같은 방식으로 비교 및 교환을 반복하며 리스트의 끝까지 진행합니다.
3. 한 번의 순회가 끝나면 가장 큰 원소가 리스트의 맨 끝에 위치하게 됩니다.
4. 이 과정을 정렬되지 않은 나머지 원소들에 대해 반복합니다. 매 순회가 끝날 때마다 정렬된 부분은 하나씩 늘어납니다.

---

장단점

• 장점: 알고리즘이 매우 간단하여 이해하고 구현하기 쉽습니다.
• 단점: 시간 복잡도가 매우 비효율적입니다. 데이터의 양이 많아질수록 정렬 속도가 급격히 느려지기 때문에, 실제 프로그래밍에서는 거의 사용되지 않습니다. 하지만 알고리즘 학습을 위한 예시로는 자주 활용됩니다.

버블 정렬을 파이썬으로 구현하는 방법은 다음과 같습니다. 버블 정렬은 인접한 두 원소를 비교하며 정렬하는 알고리즘으로, 비효율적이지만 구현이 간단하다는 특징이 있습니다.

#1. 기본 버블 정렬

가장 기본적인 버블 정렬 구현입니다. 리스트의 모든 원소를 순회하며 인접한 원소와 비교하고, 필요에 따라 위치를 바꿉니다.

arr = [100, 90, 120, 80, 140, 200, 70]

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

print(bubble_sort_basic(arr))

#결과물 [70, 80, 90, 100, 120, 140, 200]

코드 분석

• arr = [100, 90, 120, 80, 140, 200, 70]: 정렬할 숫자들이 담긴 리스트를 정의합니다.
• def bubble_sort_basic(arr):: arr라는 리스트를 인자로 받아 정렬하는 함수를 정의합니다.
• n = len(arr): 리스트의 길이를 n 변수에 저장합니다. 이 예시에서는 n이 7이 됩니다.
• for i in range(n):: 이 외부 루프는 전체 리스트를 n번 순회합니다. 이 루프가 한 번 끝날 때마다 가장 큰 원소가 리스트의 맨 뒤로 이동하게 됩니다.
  • i는 0부터 n-1까지 변합니다. i가 증가할수록 이미 정렬된 원소의 개수가 늘어나므로, 안쪽 루프의 반복 횟수는 줄어들게 됩니다.
• for j in range(0, n - i - 1):: 이 내부 루프는 인접한 두 원소를 비교하고 필요에 따라 위치를 바꿉니다.
  • j는 0부터 (n-i-1)까지 변합니다. (n-i-1)은 매 순회마다 이미 정렬된 부분(뒤에서부터 i개)을 제외하고 비교를 수행하기 위함입니다.
• if arr[j] > arr[j + 1]:: 현재 원소(arr[j])가 다음 원소(arr[j+1])보다 크다면(오름차순 기준), 두 원소의 위치를 바꿉니다.
• arr[j], arr[j + 1] = arr[j + 1], arr[j]: 파이썬의 튜플 언패킹을 이용해 두 원소의 값을 서로 교환합니다.
• return arr: 정렬이 완료된 리스트 arr를 반환합니다.

최종적으로 print(bubble_sort_basic(arr)) 명령어를 통해 정렬된 리스트인 [70, 80, 90, 100, 120, 140, 200]가 출력됩니다.

---

실행 과정 예시 (첫 번째 순회)

arr = [100, 90, 120, 80, 140, 200, 70]

• j = 0: 100과 90을 비교 → 90, 100으로 교환 -> [90, 100, 120, 80, 140, 200, 70]
• j = 1: 100과 120을 비교 → 그대로 -> [90, 100, 120, 80, 140, 200, 70]
• j = 2: 120과 80을 비교 → 80, 120으로 교환 -> [90, 100, 80, 120, 140, 200, 70]
• j = 3: 120과 140을 비교 → 그대로 -> [90, 100, 80, 120, 140, 200, 70]
• j = 4: 140과 200을 비교 → 그대로 -> [90, 100, 80, 120, 140, 200, 70]
• j = 5: 200과 70을 비교 → 70, 200으로 교환 -> [90, 100, 80, 120, 140, 70, 200]

첫 번째 순회가 끝난 후, 가장 큰 원소인 200이 리스트의 맨 끝으로 이동합니다. 이 과정을 반복하여 최종적으로 모든 원소가 정렬됩니다.

---

#2. 최적화된 버블 정렬

정렬 과정에서 교환이 한 번도 일어나지 않으면 이미 정렬이 완료된 상태이므로, 불필요한 반복을 멈추고 효율을 높일 수 있습니다. swapped 변수를 사용하여 교환 여부를 확인하고, 교환이 없으면 반복문을 탈출합니다.

arr = [70, 80, 100, 120, 90, 140, 200]

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], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr
    
print(bubble_sort_optimized(arr))

#결과물 [70, 80, 90, 100, 120, 140, 200]

코드 분석

• arr = [70, 80, 100, 120, 90, 140, 200]: 정렬할 숫자들이 담긴 리스트입니다.
• def bubble_sort_optimized(arr):: arr 리스트를 정렬하는 함수를 정의합니다.
• n = len(arr): 리스트의 길이를 n 변수에 저장합니다. 이 예시에서는 n이 7입니다.
• for i in range(n):: 이 외부 루프는 전체 리스트를 순회합니다. 한 번의 순회가 끝날 때마다 가장 큰 원소가 리스트의 맨 뒤로 이동합니다.
• swapped = False: 내부 루프가 시작하기 전에 swapped 변수를 False로 초기화합니다. 이 변수는 이번 순회에서 원소 교환이 일어났는지 추적하는 데 사용됩니다.
• for j in range(0, n - i - 1):: 이 내부 루프는 인접한 두 원소를 비교하고, 필요에 따라 위치를 바꿉니다.
  • if arr[j] > arr[j + 1]: : 현재 원소(arr[j])가 다음 원소(arr[j+1])보다 크다면(오름차순), 두 원소의 위치를 교환합니다.
  • arr[j], arr[j + 1] = arr[j + 1], arr[j] : 원소의 위치를 교환하는 코드입니다.
  • swapped = True : 교환이 발생했으므로 swapped 변수를 True로 변경합니다.
• if not swapped: break: 내부 루프가 끝난 후, swapped 변수가 여전히 False라면 이는 이번 순회 동안 단 한 번의 교환도 일어나지 않았음을 의미합니다. 즉, 리스트가 이미 완전히 정렬된 상태이므로, 불필요한 나머지 순회를 중단하고 break 문을 통해 외부 루프를 탈출합니다.
• return arr: 정렬이 완료된 리스트를 반환합니다.

실행 과정 분석

기본 버블 정렬과 달리, 이 코드는 리스트가 이미 정렬된 상태에 가까울 때 더 효율적입니다.

arr = [70, 80, 100, 120, 90, 140, 200]

• 첫 번째 순회 (i=0):
  • 70과 80 비교 → 그대로
  • 80과 100 비교 → 그대로
  • 100과 120 비교 → 그대로
  • 120과 90 비교 → 90, 120으로 교환. swapped가 True가 됩니다. ([70, 80, 100, 90, 120, 140, 200])
  • 120과 140 비교 → 그대로
  • 140과 200 비교 → 그대로
  • swapped가 True이므로 루프를 계속 진행합니다.
• 두 번째 순회 (i=1):
  • swapped는 다시 False로 초기화됩니다.
  • 70부터 140까지 비교를 진행합니다. 이 순회에서는 어떤 교환도 일어나지 않습니다. ([70, 80, 90, 100, 120, 140, 200])
  • 내부 루프가 끝난 후, swapped는 여전히 False이므로 if not swapped: break 조건이 참이 되어 알고리즘이 여기서 종료됩니다.

이처럼 최적화된 버블 정렬은 정렬이 불필요한 시점을 빠르게 파악하여 실행 시간을 단축합니다.

---

#3. 재귀를 이용한 버블 정렬

버블 정렬을 재귀 함수로 구현할 수도 있습니다. 재귀 호출을 통해 가장 큰 원소를 리스트의 끝으로 이동시키는 과정을 반복합니다.

arr = [70, 80, 100, 120, 90, 140, 200]

def bubble_sort_recursive(arr, n=None):
    if n is None:
        n = len(arr)
    if n == 1:
        return
    for i in range(n - 1):
        if arr[i] > arr[i + 1]:
            arr[i], arr[i + 1] = arr[i + 1], arr[i]
    bubble_sort_recursive(arr, n - 1)
    return arr
    
print(bubble_sort_optimized(arr))

#결과물 [70, 80, 90, 100, 120, 140, 200]

코드 분석

• arr = [70, 80, 100, 120, 90, 140, 200]: 정렬할 리스트입니다.
• def bubble_sort_recursive(arr, n=None):: arr 리스트와 현재 정렬할 범위를 나타내는 n을 인자로 받는 재귀 함수를 정의합니다. n이 제공되지 않으면 리스트의 전체 길이로 초기화됩니다.
• if n is None: n = len(arr): 함수가 처음 호출될 때 n이 None이면, 리스트의 전체 길이로 n을 설정합니다.
• if n == 1: return: 이 부분은 종료 조건입니다. 리스트의 길이가 1이 되면 더 이상 비교할 원소가 없으므로 재귀 호출을 멈춥니다. 이 조건이 없으면 무한 루프에 빠질 수 있습니다.
• for i in range(n - 1):: 이 반복문은 한 번의 순회를 수행합니다. 인접한 두 원소를 비교하여 가장 큰 원소를 현재 정렬 범위의 끝으로 보냅니다.
  • if arr[i] > arr[i + 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i] : 현재 원소가 다음 원소보다 크면 위치를 교환합니다.
• bubble_sort_recursive(arr, n - 1): 한 번의 순회가 끝난 후, 가장 큰 원소는 이미 제 위치를 찾았으므로 **남은 원소들(n-1개)**에 대해 다시 함수를 호출합니다.
• return arr: 모든 재귀 호출이 완료되면, 최종적으로 정렬된 리스트를 반환합니다.

제공된 코드의 print(bubble_sort_optimized(arr)) 부분은 실제로 위에 정의된 재귀 함수(bubble_sort_recursive)를 호출하지 않고, 이전 질문에서 사용된 최적화 함수를 호출하고 있습니다. 하지만 재귀 함수 코드 자체는 위의 설명대로 작동하여 동일한 정렬 결과를 만들어 냅니다.