버블 정렬(bubble sort)개념 및 구현 방법(python)

정렬 : 대소관계에 따라 데이터를 일정하게 나열하는 것

정렬은 교환 / 선택 / 삽입 3가지 과정을 통해서 이루어진다

교환 및 삽입 과정에서 순서가 보장되면 stable, 안되면 unstable이라고 지칭

---

1. 버블 정렬(Bubble Sort)

이웃한 두 원소의 대소관계 비교 후, 교환 반복하는 알고리즘

2. 동작 원리

i = 인덱스 , n = 전체 배열의 개수

a. i = 0에서 반복을 실행한다. 오른쪽 원소가 왼쪽 원소보다 작으면 교환을 진행한다

b. i = 1에서 반복을 실행한다. 오른쪽 원소가 왼쪽 원소봐 작으면 교환을 진행한다

c i = n-1까지 반복한다

3. 장단점

• 장점
  • 구현하기 쉽다
• 단점
  • 정렬이 된 요소 또한, 교환이 일어난다 (비효율 발생)
  • 교환 후, 순서가 일치하지 않음에도, 교환이 일어난다

4. 시간 복잡도

원소의 정렬 상태에 관계 없이 n -1 번, n-2 번, ... , 2, 1번 일어난다

• Worst : n2
• Average : n2
• Best : n2

5. 구현하기

기본적인 bubble sort 구조는 다음과 같습니다

a = [1,4,5,3,2]

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

 

그러나, 앞서 우리는 bubble sort의 시간 복잡도가 n² 인 알고리즘이라는 사실을 알고 있기 때문에,

이를 최적화하는 로직이 필요할 것 같습니다.

 

bubble sort를 진행하다가 '두 원소가 이미 정렬'되어 있다면 교환을 진행하지 않고 넘어가면 되지 않을까요?

설명이 모호할 수 있으니 아래 코드와 함께 살펴보겠습니다

 

a = [1,4,5,3,2]

def bubble_sort(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 swapped == False:
            break
                
    return arr

 

 

반복문의 시작점에서 swapped = False를 명시합니다.

swapped = False로 시작하는 이유는, 현재 반복에서 아직 교환(swap)이 발생하지 않았음을 나타내기 위해서입니다.

 

반복 중 arr[j] > arr[j+1]인 경우, 두 요소를 교환하고 swapped = True로 설정합니다.

 

만약 단 한 번도 교환이 발생하지 않았다면 (swapped가 여전히 False라면), 배열은 이미 정렬된 상태이므로 남은 반복을 건너뛰고 루프를 종료합니다.

 

즉, a = [ 1, 4, 5, 3, 2] 정렬을 할 때, 이미 정렬이 완료된 상태에서 또 다시 정렬을 진행할 수 있는데, 그것을 막는 구문입니다