버블 정렬(bubble sort)

참고: 누구나 자료 구조와 알고리즘(개정2판) 4장,

모두를 위한 컴퓨터 과학(데이비드말란 교수님) 강의

 

정렬 알고리즘 시각화 사이트
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

4.1. 버블 정렬

이번 4장에서는 현실적인 문제를 푸는 코드를 작성해보고, 빅 오를 사용해 작성한 알고리즘을 평가해보겠다.
정렬 알고리즘은 컴퓨터 과학 분야에서 폭넓게 연구된 주제이며, 이러한 알고리즘은 모두 다음 문제를 해결한다.

정렬되지 않은 배열이 주어졌을 때, 어떻게 오름차순으로 정렬할 수 있을까?

4장과 5장에서는 이런 정렬 알고리즘을 많이 다룰 것이다. 매우 기본적인 정렬 알고리즘인 버블 정렬부터 알아본다.
버블 정렬은 두 인접한 원소의 대소를 비교하여 일정 기준(오름차순, 내림차순)을 만족하면 두 값의 위치를 교환하는 방법이다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

버블 정렬은 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중하기 때문에 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다.

4.2.1. 버블 정렬 구현 (오름차순 기준)

1부터 N개의 원소가 있다고 하자. (인덱스 번호로는 0번째부터 N-1번째에 원소가 있는 것)

1-1) [i=0], [i=1]번째 원소 ~ [i=N-2], [i=N-1]번째까지 인접한 두 원소를 비교한다. -> N-1번 비교
1-2) 위 과정에서 인접한 두 원소를 교환한다. -> N-1번 교환
1-3) 가장 큰 원소는 [i=N-1]번째로 정렬된다.

* 배열의 처음부터 끝까지 두 값을 비교해 교환해나가는 한번의 사이클을 PASS라 한다.

2-1) [i=0], [i=1]번째 원소 ~ 마지막 원소 제외한 [i=N-3], [i=N-2]번째까지 인접한 두 원소를 비교한다. -> N-2번 비교
2-2) 위 과정에서 인접한 두 원소를 교환한다. -> N-2번 교환
2-3) 가장 큰 원소는 [i=N-2]번째로 정렬된다.

---

* 버블 정렬 알고리즘 파이선 구현 예제

def bubbleSort(box): 
    bubble_index = len(box)-1 # 리스트의 인덱스는 0부터 n-1까지 이므로 len(리스트)-1 

    for i in range(bubble_index): 
        print(f'\n * {i+1}번째 비교:') 
        print('--------------------') 
        for j in range(0, bubble_index - i): # 한 번의 pass가 끝나면 맨 뒤로 이동한 인덱스는 정렬에서 제외 
            print(f'인덱스 ({j},{j+1})') 
            if box[j] > box[j+1]: 
                box[j], box[j+1] = box[j+1], box[j] 
        
    return box

버블 정렬 알고리즘대로 (N-1) + (N-2) + ... + 1 = N(N-1)/2번의 비교를 진행하게 된다.
이미 정렬되어 있는 [1,2,3,4,5] 리스트를 예시로 포스팅한 이유는 아래의 알고리즘 실행시간 줄이기와 비교하기 위해 정렬된 리스트로 예시를 들었다.

추가. 버블 정렬 실행 시간 줄이기, 알고리즘 최적화

이미 정렬이 되어있는 숫자 리스트가 있다면, O(N²) 만큼의 비교를 할 필요가 없다.
즉, '교환이 일어나지 않을 때' 까지만 비교를 수행하도록 알고리즘을 수정하면 시간 복잡도를 O(N)으로 줄일 수 있다.
버블 정렬의 기본 알고리즘 코드에 swapped = True/False(교환 여부) 코드만 추가해 구현한다.

def bubbleSort(box): 
    bubble_index = len(box)-1 # 리스트의 인덱스는 0부터 n-1까지 이므로 len(리스트)-1 
    
    for i in range(bubble_index): 
        print(f'\n * {i+1}번째 비교:') 
        print('--------------------') 
        swapped = False # 교환이 일어나지 않는 경우를 기본값으로 설정 
        
        for j in range(0, bubble_index - i): # 한 번의 pass가 끝나면 맨 뒤로 이동한 인덱스는 정렬에서 제외 
            print(f'인덱스 ({j},{j+1})') 
            if box[j] > box[j+1]: 
                box[j], box[j+1] = box[j+1], box[j] 
                swapped = True # 교환이 일어나면 True로 바꿔, break하지 않고 계속 비교 
            
        if not swapped: # 교환이 이루어지지 않으면 비교를 멈추고 빠져나온다. 
                break
    
    return box

이미 정렬이 잘 되어 있는 배열이 있다면,
위의 수정된 알고리즘을 통해 N(N-1)/2번의 비교하지 않고 N-1번의 O(N)의 시간복잡도로 실행 시간을 줄일 수 있다.

 

4.3. 버블 정렬의 효율성

버블 정렬 알고리즘은 두 가지 중요한 단계를 포함한다.

최악의 시나리오: O(N²)

• 비교: (N-1) + (N-2) + ... + 1 = N(N-1)/2번
• 교환(swap): (N-1) + (N-2) + ... + 1 = N(N-1)/2번

최선의 시나리오: Ω(N²)

• 비교: (N-1) + (N-2) + ... + 1 = N(N-1)/2번
• 교환(swap): 0번

'교환이 일어나지 않을 때' 까지만 비교를 수행할 때 최선의 시나리오: Ω(N)

 

따라서 버블 정렬의 시간 복잡도를 빅 오 표기법으로 나타내면 O(N²), 이차 시간(quadratic time)이라고 부른다.
데이터가 증가할수록 단계 수가 급격히 늘어나므로 비효율적인 알고리즘으로 볼 수 있다.