버블 정렬

오늘은 대표적인 정렬 알고리즘인 Bubble sort에 대해 알아보려고 한다. 

 

버블정렬은 가장 앞의 값을 뒤의 값과 비교하여 앞의 값이 클 경우 두개의 순서를 바꾸는 과정을

반복하며 진행한다. 

 

글 보다는 예시를 봐야 이해가 잘 가는 것 같다. 

[4, 3, 5, 1, 2]

 

이렇게 5개의 값이 있는 리스트가 있다고 해보자.

 

[4, 3, 5, 1, 2]
 ^  ^
4 > 3 => Swap
[3, 4, 5, 1, 2]

 

우리는 먼저 가장 앞의 값인 4와 3을 비교한다. 

 

4가 3보다 크기 때문에 두 값은 바뀌게 된다. 

 

[3, 4, 5, 1, 2]
    ^  ^
4 < 5 => No Swap

 

이후에 4와 5를 비교하게 되는데 4가 5보다 자리가 작기 때문에 자리를 바꾸지 않는다. 

 

[3, 4, 5, 1, 2]
       ^  ^
5 > 1 => Swap
[3, 4, 1, 5, 2]

 

그 다음엔 5와 그 뒤의 값인 1을 비교하는데 5가 1보다 크기 때문에 자리를 바꾼다. 

 

[3, 4, 1, 5, 2]
          ^  ^
5 > 2 => Swap
[3, 4, 1, 2, 5]
             *

 

마찬가지로 5와 2를 비교하는데 5가 더 크기 때문에 자리를 바꾼다. 

 

5는 리스트에서 가장 큰 수이기 때문에 마지막 자리수는 정렬이 끝난 상태라고 보면 된다. 

 

이 과정을 마지막 자리수를 제외한 나머지 4자리에 대해서도 진행한다. 

Initial: [4, 3, 5, 1, 2]

 Pass 1: [3, 4, 1, 2, 5]
                      *
 Pass 2: [3, 1, 2, 4, 5]
                   *  *
 Pass 3: [1, 2, 3, 4, 5]
                *  *  *
 Pass 4: [1, 2, 3, 4, 5]
             *  *  *  *
 Pass 5: [1, 2, 3, 4, 5]
          *  *  *  *  *

 

이렇게 정렬하는 과정을 한칸씩 줄이며 모든 값이 정렬될 때까지 반복하는 것이다. 

 

 

공간복잡도는 주어진 공간내에서만 정렬을 진행하기 때문에 O(1) 의 공간복잡도를 가진다. 

 

시간복잡도는 모든 인덱스에 접근해야 되기 때문에 N번 + 인접 값들의 대소비교 후 자리 바꾸기에 N번이 걸려

O(N^2) 된다.

 

하지만 부분적으로 정렬이 되어있는 배열이 들어올 경우 속도는 훨씬 빨라진다. (자리바꾸기가 별로 없기 때문)

 

만약 배열이 완전히 정렬되어있는 상태라면 O(N) 까지 시간복잡도가 향상된다고 한다. 

 

---

구현

def bubble_sort(arr):
    for i in range(len(arr)-1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j+1]: # 뒤보다 앞의 크기가 크다면 순서바꾸기
                arr[j], arr[j+1] = arr[j+1], arr[j] 
        print(arr)

arr = [4, 3, 5, 1, 2]
bubble_sort(arr)

 

실행결과

 

위의 과정과 같은 결과가 나온 것을 확인할 수 있다.