[정렬] 버블 정렬 [Bubble Sort]

버블 정렬에 대해 알아보자.

 

 

사진 출처

 

 

개념

 

오름차순으로 정렬할 경우, 서로 이웃한 데이터들을 비교하여 더 큰 데이터를 뒤로 보낸다. 

1회 정렬 후에는 가장 큰 데이터가 가장 뒤에 위치하게 된다.

이것을 반복해서 오름차순으로 정렬시킨다.

 

 

---

복잡도

 

별로의 추가 공간을 사용하지 않는다.

주어진 배열 내에서 값들이 위치를 변경하기 때문에 공간 복잡도는 O(1)이다.

 

가장 큰 데이터를 계속해서 가장 뒤에 위치시켜야 하므로 O(N),

서로 이웃한 데이터들의 비교를 위해서 O(N)이 필요하다.

따라서 시간복잡도는 O(N^2)이다.

 

 

---

구현

 

# 기본
def bubble_sort(li):
    for i in range(len(li) - 1, 0, -1):
        for j in range(i):
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]

 

 

---

최적화 1

 

교대[swap]가 아예 없는 경우 종료한다. 

 

# 최적화 1
def bubble_sort(li):
    for i in range(len(li) - 1, 0, -1):
        swapped = False
        for j in range(i):
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
            	swapped = True
                
        if not swapped:
            break

 

예를 들어, [1, 2, 3, 5, 4]가 있다.

 

# 1바퀴째

0. [1, 2, 3, 5, 4] : 초기값

1. [1, 2, 3, 4, 5] : 4와 5 교대

2. [1, 2, 3, 4, 5] : 교대 없음 

 

2번에서 정렬을 종료한다. 덕분에 불 필요한 수행을 하지 않는다.

 

 

---

최적화 2

 

swap이 일어나지 않아도 되는 부분을 제외하고 범위를 재설정한다.

 

# 최적화 2 
def bubble_sort(li):
    end = len(li) - 1

    while end > 0:
        last_swap = 0
        for i in range(end):
            if li[i] > li[i + 1]:
                li[i], li[i + 1] = li[i + 1], li[i]
                last_swap = i
        end = last_swap

 

예를 들어, [3, 2, 1, 4, 5, 6]가 있다.

 

# 1바퀴째

0. [3, 2, 1, 4, 5, 6] : 초기값

1. [2, 3, 1, 4, 5, 6] : 2와 3 교대

2. [2, 1, 3, 4, 5, 6] : 1와 3 교대

 

# 2바퀴째

3. [2, 1, 3, 4, 5, 6] : 1과 2 교대

 

1바퀴에서 알 수 있는 점은 4부터 교대를 안 한다. 

따라서 다음 바퀴에서는 4이전만 교대를 하면 된다.

 

덕분에 범위를 정렬 범위를 한 칸씩 줄이지 않고 여러 칸씩 줄일 수 있다.

 

 

---

코드 참고