버블정렬(Bubble Sort)알고리즘 정리

버블 정렬은 이웃한 두 원소의 관계를 비교해, 필요에 따라 교환을 반복하는 알고리즘입니다.버블정렬은 '단순 교환 정렬' 이라고 부르기도 합니다. 우선 버블 정렬의 교환 방식을 그림으로 살펴보겠습니다

 

버블정렬은 기본적으로 이웃된 원소들간의 비교, 교환이 일어나기 때문에, 안정적인 정렬이라고 할 수 있습니다. 이제 한번 그림을 같이 보겠습니다.총 길이 6인 리스트가 있습니다. 이 리스트에서 한번의 정렬을 위해서 (총 길이)  - 1번만큼의 비교, 교환이 이루어 지는것을 볼 수 있습니다. 그리고 참고로 버블 정렬에서 일어나는 비교,교환 과정을 '패스'라고 부릅니다. 자 그럼 일단 코드를 작성해 봅시다. 우선 총 길이에 대해 -1 번만큼 교환이 일어난다고 했죠? 아래와 같이 작성해 줍니다.

 

from typing import Any, MutableSequence

def bubblesort(a : MutableSequence):
    n = len(a)
    for i in range(n - 1):
        pass

자 그러면 비교에 대해서 생각해볼 차례입니다. 우선적으로 비교를 맨 앞에서 하는게 아닌 맨 뒷부분에서 교환이 일어나는것을 볼 수 있습니다. 그렇기 때문에 리스트를 역순으로 비교해야겠죠? 값의 비교는 집중하고 있는 값이 n이라고 하면 n - 1번째 index에 있는 값과 비교하며 필요에 따라 교환해 나갑니다. 그리고 i의 값은 매번 반복문을 돌때마다, 정렬되지 않은 부분의 첫번째 index가 되게 됩니다. 그렇다면 아래와 같이 코드를 작성해 줄 수 있겠죠? 

from typing import Any, MutableSequence

def bubblesort(a : MutableSequence):
    n = len(a)
    for i in range(n - 1):
        for j in range(n-1,i,-1): # 이 for문이 패스가 되는겁니다
            if a[j] < a[j - 1]:
                a[j],a[j-1] = a[j-1],a[j]

a = [3,1,5,4,2]
bubblesort(a)
print(a)

자 버블정렬은 시간복잡도가 총 O(n^2)에 달하는 매우 비효율적인 알고리즘입니다. 이 비효율적인 알고리즘을 조금이나마 개선시키는 방법에 대해 2가지를 정리해 보겠습니다.

 

1. 만약 특정 패스 과정에서 교환이 일체 일어나지 않았다면 그건 모두 정렬이 완료되었다는것을 의미합니다. 그럼 아래와 같이 패스내에서 비교교환이 일어났는지에 대해 조건을 추가해서 검사해 줄 수 있겠죠?

from typing import Any, MutableSequence

def bubblesort(a : MutableSequence):
    n = len(a)
    for i in range(n - 1):
        exchange = False
        for j in range(n-1,i,-1):
            if a[j] < a[j - 1]:
                exchange = True
                a[j],a[j-1] = a[j-1],a[j]
        if not exchange:
            break
        else:
            continue


a = [3,1,5,4,2]
bubblesort(a)
print(a)

2. 특정 index미만 부터 교환이 일어나지 않는다면,다음 패스부터는 해당 index까지만 검사를 진행해 주면 됩니다.

from typing import Any, MutableSequence

def bubblesort(a : MutableSequence):
    n = len(a)
    k = 0
    while k < n - 1:
        last = n-1
        for j in range(n-1,k,-1):
            if a[j] < a[j - 1]:
                a[j],a[j-1] = a[j-1],a[j]
                last = j
        k = last
                

a = [3,1,5,4,2]
bubblesort(a)
print(a)