버블 정렬

버블 정렬

 

이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘입니다.

아래 예시처럼 n개 원소의 배열에서 처음 교환 과정(패스)에서는 비교 횟수가 n - 1회, 다음 패스에서는 비교 횟수가 n - 2회로 최종적으로 시간 복잡도는 O(n^2)입니다.

 

from typing import MutableSequence

def bubble_sort(a: MutableSequence) -> None:
    n = len(a)
    for i in range(n - 1):
        for j in range(n-1, i, -1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]

 

처음에는 이 코드가 이해가 되지 않았는데, 우측의 a[j-1], a[j]를 (a[j-1], a[j]) 튜플로 인식하여, 좌측으로 언패킹하는 것이라고 합니다.

a[j-1], a[j] = a[j], a[j-1]

 

알고리즘 개선 1

 

어떤 패스에서 교환 횟수가 0이라면, 이미 정렬을 마친 배열이므로 그 이후 패스에서도 더이상 교환이 일어나지 않을 것입니다. 그러므로 실행 시간을 단축하기 위해 그 이후 패스에 대해서는 정렬 중단을 실행합니다. 

 

해당 패스의 교환 여부를 추적하는 변수 change를 초기값으로 False로 선언하여, 만약 교환이 일어났을 시 True로 변환하도록 합니다. 만약 해당 패스에서 change가 그대로 False인 경우 다음 패스를 실행하지 않고 정렬을 종료합니다.

def bubble_sort(a: MutableSequence) -> None:
    n = len(a)
    for i in range(n - 1):
    	change = False
        for j in range(n-1, i, -1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]
                change = True
        if change == False:
            break

 

최선의 경우 그저 n-1번만 비교하고 종료하므로 O(n)이지만, 최악의 경우인 배열이 내림차순이었다면 O(n^2)입니다. 

 

알고리즘 개선 2

 

각 패스에서 비교/교환을 하다가 어떤 특정한 원소 이후에 원소 교환이 이루어지지 않을 수 있습니다. 즉, 특정 원소 이후의 원소들은 이미 정렬이 되어 있는 경우입니다. 이때도 불필요하게 정렬 과정을 수행하지 않고, 스캔 범위를 제한하여 실행 시간을 단축할 수 있습니다.

 

변수 last에는 교환이 일어났을 때 오른쪽 원소의 인덱스를 대입하고, 하나의 패스를 마친 시점에 변수 k에 last 값을 대입하여 다음에 수행할 패스의 스캔 범위를 제한하는 방식입니다.

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

 

셰이커 정렬

 

홀수 번째의 패스는 가장 작은 요소를 맨 앞으로, 짝수 번째의 패스는 가장 큰 요소를 맨 뒤로 정렬하는 방식입니다. (혹은 그 반대)

 

응?

 

수행 과정

① 먼저 우측에서 좌측으로 비교 작업을 진행합니다. 교환할 자료가 있으면 교환하면서 좌측 지점까지 진행합니다.

② 마지막에 교환이 이루어진 곳을 좌측 지점으로 설정합니다.

③ 이번에는 반대로 좌측 지점부터 우측 지점으로 비교 작업을 진행하면서 교환할 요소는 교환합니다.

④ 마지막에 교환이 이루어진 곳을 우측 지점으로 지정합니다.

⑤ 좌측 지점과 우측 지점이 교차하지 않았다면 아직 정렬할 자료가 남아있으니 앞의 작업을 계속 반복합니다.

 

​비교/교환 작업이 진행되면서 정렬 범위가 조금씩 좁아지게 되며 결국은 더이상 비교할 것이 없는 정렬 완료 상태가 됩니다.

def shaker_sort(a: MutableSequence) -> None:
    left = 0
    right = len(a) - 1
    last = right
    while left < right:
        for j in range(right, left, -1):
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]
                last = j
            left = last

        for j in range(left, right):
            if a[j] > a[j + 1]:
                a[j + 1], a[j] = a[j], a[j + 1]
                last = j
            right = last