정렬 알고리즘 : 버블 정렬 (Python)

버블 정렬

---

 

 

버블 정렬 gif

개념

 선택 정렬과 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다.

 배열 끝에서부터 반대 끝까지 두 요소를 선택하여 비교한다. 만약 더 작은 요소가 뒤에 있다면 자리를 바꾼다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동한다. 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외한다. 

 장점은 구현이 간단하고 소스 코드가 직관적이다. 또한 정렬하고자 하는 배열 안에서 교환하는 방식이므로 다른 메모리 공간을 필요로 하지 않는다. 

 단점은 시간 복잡도가 최악, 최선, 평균 모두 비효율적이며, 정렬되어있지 않은 원소가 정렬될 자리로 가기 위해 SWAP 연산이 많이 일어나게 된다.

 

 

소스 코드

def bubble_sort_1(array):
    for index in reversed(range(len(array))):
        for i in range(index):
            if array[i] > array[i+1]:
                x[i],x[i+1] = x[i+1],x[i]
                

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

arr = [64, 34, 25, 12, 57, 93, 1, 123]
bubble_sort2(arr)

 

 

시간 복잡도

O(N^2)

 (n-1) + (n-2) + (n-3) + ... + 2 + 1 = n * (n - 1) / 2 이므로, O(N^2) 이다. 또한 버블 정렬은 기존에 정렬 여부에 상관없이 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가 동일하다.

 

 

공간 복잡도

주어진 배열 안에서 swap을 통해 정렬이 수행되므로 O(N)이다.