버블 정렬

정렬 알고리즘의 정의

 

정렬(sorting)이란 텍스트나 숫자 등의 key를 항목 값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말한다. 데이터를 정렬하면 쉽게 검색할 수 있다. 

값이 작은 데이터를 앞쪽에 늘어놓는 것을 오름차순(ascending order)정렬이라 하고, 반대를 내림차순(descending order) 정렬이라 한다.

 

정렬 알고리즘은 데이터를 교환-선택-삽입하면서 정렬을 완료한다. 대부분의 정렬 알고리즘은 이 세가지를 응용한다.

---

 

안정성

 

여러 정렬 알고리즘 가운데 안정적인(stable) 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있다.

안정적인 정렬 알고리즘

위의 그림처럼 안정적인 정렬 알고리즘은 값이 같은 원소의 순서가 정렬한 후에도 유지되는 것을 말한다. 안정적이지 않은 알고리즘은 정렬 후에도 원래의 순서가 유지된다는 보장을 할 수 없다.

 

 

 

내부 정렬과 외부 정렬

 

만약 카드 10장을 정렬 한다면, 책상 위에 늘어놓고 작업을 수행할 수 있다. 그러나 카드가 500장이라면 더 큰 책상을 마련해야 한다. 이처럼 정렬 알고리즘도 하나의 배열에서 작업할 수 있는 경우 내부 정렬(internal sorting)을 사용하고, 그렇지 않은 경우 외부 정렬(external sorting)을 사용한다.

외부 정렬은 내부 정렬을 응용한 것으로, 외부 정렬을 구현하려면 별도로 작업용 파일이 필요하고 알고리즘도 복잡하다.

---

버블 정렬

 

버블 정렬(bubble sort)은 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘으로, 단순 교환 정렬이라고도 한다.

 

원소 수가 n인 배열에서 n - 1번 비교-교환을 하면 가장 작은 원소인 1이 맨 앞으로 이동한다. 이러한 일련의 비교, 교환하는 과정을 패스(pass)라고 한다.

패스를 한 번 수행할 때마다 정렬할 대상은 1개씩 줄어든다. 두 번째 패스의 비교 횟수는 n - 2번이다. 패스를 k번 수행하면 맨 앞부터 k개 원소가 정렬된다. 모든 정렬이 끝나려면 패스를 n - 1번 수행해야 한다.

 

<code>

from typing import MutableSequence

def bubble_sort(a: MutableSequence):
    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]
    
if __name__ == '__main__':
    print('버블 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요 : '))
    x = [None] * num    # 원소 수가 num인 배열을 생성
    
    for i in range(num):
        x[i] = int(input(f'x[{i}] : '))
        
    bubble_sort(x)
    
    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')

 

 

버블 정렬은 1칸 이상 떨어져 있는 원소를 교환하는 것이 아니라 서로 이웃한 원소만 교환하기 때문에 안정적이다.

원소를 비교하는 횟수는 다음과 같다.

(n - 1) + (n + 2) + ... + 1 = n(n - 1) / 2

그러나 실제 원소를 교환하는 횟수는 배열의 원 솟값에 영향을 받으므로 평균값은 비교 횟수 전체의 절반인 n(n - 1) / 4번이다.

 

 

알고리즘의 개선 1

 

만약 이전의 패스 과정에서 원소 정렬이 모두 끝났다면, 다음 패스에선 원소 교환이 발생하지 않는다. 즉 어떤 패스의 원소 교환 횟수가 0이면 모든 원소가 정렬을 완료한 경우이므로 그 이후의 패스는 불필요하다고 판단하여 정렬을 중단하면 된다.

예를 들어 아래의 배열은 첫 번째 패스부터 한 번도 교환하지 않으므로 첫 번째 패스를 마친 시점에 정렬을 종료할 수 있다.

1

3

4

6

7

9

 

<code>

from typing import MutableSequence

def bubble_sort(a: MutableSequence):
    n = len(a)
    for i in range(n - 1):
        exchng = 0
        for j in range(n - 1, i, - 1):
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]
                exchng += 1
        if exchng == 0:
            break
            
            
...생략...

 

 

알고리즘의 개선 2

 

배열 1, 3, 9, 4, 7, 8, 6을 버블 정렬한다면, 첫 번째 패스의 비교, 교환 과정은 아래와 같다.

 

마지막으로 교환한 위치에서 원소 1, 3, 4는 이미 정렬된 상태이다. 각각의 패스에서 비교-교환을 하다가 어떤 특정한 원소 이후에 교환하지 않는다면, 그 원소보다 앞쪽에 있는 원소는 이미 정렬을 마친 것이다. 따라서 정렬을 마친 원소는 제외하고 좁혀서 비교하면 된다.

<code>

from typing import MutableSequence

def bubble_sort(a: MutableSequence):
    n = len(a)
    k = 0
    
    while k < n - 1:
        last = n - 1
        exchng = 0
        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
                exchng += 1
        k = last
        if exchng == 0:
            break
            
...생략...

 

새로운 변수 last는 각 패스에서 마지막으로 교환한 두 원소 가운데 오른쪽 원소인 a[j] 인덱스를 저장한다. 교환할 때마다 오른쪽 원소의 인덱스값을 last에 대입한다. 하나의 패스를 마친 시점에 last의 값을 k에 대입하여 다음에 수행할 패스의 스캔 범위를 a[k]로 제한한다.

---

 셰이커 정렬

 

9

1

3

4

6

7

8

위의 배열은 거의 정렬이 완료된 배열이다. 그러나 정렬 작업을 빠르게 마칠 수 없다. 가장 큰 원소인 9가 한 패스에 하나씩 뒤로 이동하기 때문이다. 만약 9를 빠르게 맨 뒤로 이동시킨다면 작업 속도는 훨씬 빨라질 것이다.

 

홀수 패스에서는 가장 작은 원소를 맨 앞으로 이동시키고, 짝수 패스에서는 가장 큰 원소를 맨 뒤로 이동시켜 패스의 스캔 방향을 번갈아 바꾼다면, 이전의 실행 결과보다 적은 비교 횟수로 정렬할 수 있다.

이렇게 버블 정렬을 개선한 알고리즘을 셰이커 정렬(saker sort), 양방향 버블 정렬(bidirectional bubble sort), 칵테일 정렬(cocktail sort) 이라고도 한다. 

 

<code>

from typing import MutableSequence

def shaker_sort(a: MutableSequence):
    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], a[j + 1] = a[j + 1], a[j]
                last = j
        right = last

...생략...

 

코드에서 선언한 left는 스캔 범위의 첫 원소 인덱스이며, right는 스캔 범위의 마지막 원소 인덱스이다. 비교 횟수가 이전의 버블 정렬보다 2배가량 감소했다.