파이썬 정렬 알고리즘

정렬 알고리즘의 정의

정렬(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배가량 감소했다.

---

단순 선택 정렬의  정의

단순 선택 정렬(straight selection sort)은 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘이다. 다음은 단순 선택 정렬의 과정이다.

아직 정렬하지 않은 범위에서 값이 가장 작은 원소를 선택하고, 아직 정렬하지 않은 부분의 맨 앞 원소와 교환하는 작업을 반복한다.

이 과정을 n - 1번 반복하면 정렬하지 않은 부분이 없어지면서 전체 정렬을 완료한다. 알고리즘의 개요는 다음과 같다.

for i in range(n - 1):
    min    # a[i], ... a[n-1]에서 키 값이 가장 작은 원소의 인덱스
    a[i]와 a[min]의 값을 교환

 

<code>

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        min = i    # 정렬할 부분에서 가장 작은 원소의 인덱스
        for j in range(i + 1, n):
            if a[j] < a[min]:
                min = j
        a[i], a[min] = a[min], a[i]    # 정렬할 부분에서 맨 앞의 원소와 가장 작은 원소를 교환

 

단순 선택 정렬 알고리즘의 원솟값을 비교하는 횟수는 (n^2 - n) / 2번이다.

하지만 이 알고리즘은 서로 이웃하지 않는 떨어져 있는 원소를 교환하므로 안정적이지 않다.

 

단순 삽입 정렬의 정의

단순 삽입 정렬(straight insertion sort)은 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘이다. 단순 선택 정렬과 비슷해 보이지만 가장 값이 작은 원소를 선택하지 않는다는 점이 다르다.

 

이때 i를 1, 2, ... n - 1까지 1씩 증가시키면서 인덱스 i의 원소를 꺼내 알맞은 위치에 삽입한다. 알고리즘의 개요는 다음과 같다.

for i in range(1, n):
    tmp <- a[i]를 넣는다.
    tmp를 a[0], ... a[i - 1]의 알맞은 위치에 삽입한다.

 

<code>

def insertion_sort(a):
    n = len(a)
    for i in range(1, n):
        j = i
        tmp = a[i]
        while j > 0 and a[j - 1] > tmp:
            a[j] = a[j - 1]
            j -= 1
            
        a[j] = tmp
        
if __name__ == '__main__':
    print('단순 삽입 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요 : '))
    x = [None] * num 
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))
        
    insertion_sort(x)
    
    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')

 

이 알고리즘은 서로 떨어져 있는 원소를 교환하지 않으므로 안정적이라고 할 수 있다. 원소의 비교 횟수와 교환 횟수는 모두 n^2 / 2번이다.

이전까지 다룬 버블, 선택, 삽입 알고리즘의 시간 복잡도는 모두 O(n^2)으로 효율이 좋지 않다.

---

이진 삽입 정렬

단순 삽입 정렬은 배열 원소 수가 많아지면 원소 삽입에 필요한 비교-교환 비용이 커진다. 그러나 이진 검색법을 사용하여 삽입 정렬을 하면 이미 정렬을 마친 배열을 제외하고 원소를 삽입해야 할 위치를 검사하므로 비용을 줄일 수 있다.

<code>

def binary_insertion_sort(a):
    n = len(a)
    for i in range(1, n):
        key = a[i]
        pl = 0
        pr = i - 1
        
        while True:
            pc = (pl + pr) // 2
            if a[pc] == key:
                break
            elif a[pc] < key:
                pl = pc + 1
            else:
                pr = pc - 1
                
            if pl > pr:
                break
        
        pd = pc + 1 if pl < pr else pr + 1    # 삽입해야 할 위치의 인덱스
        
        for j in range(i, pd, -1):
            a[j] = a[j - 1]
        a[pd] = key
        
if __name__ == '__main__':
    print('이진 삽입 정렬을 수행한다.')
    num = int(input('원소 수를 입력하세요 : '))
    x = [None] * num
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))
        
    binary_insertion_sort(x)
    
    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')

 

** 단순 삽입 정렬 알고리즘은 파이썬 표준라이브러리 bisect 모듈의 insort() 함수로 제공한다.

 

<code>

import bisect

def binary_insertion_sort(a):
    for i in range(1, len(a)):
        bisect.insort(a, a.pop(i), 0, i)

---

셸 정렬 정의

셸 정렬(shell sort)은 단순 삽입 정렬의 장점을 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘이다.

 

단순 삽입의 특징

- 장점 : 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서는 속도가 아주 빠르다.

- 단점 : 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아진다.

셀 정렬은 먼저 정렬할 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행한다. 그 후 정렬된 그룹을 합치는 작업을 반복하여 원소의 이동 횟수를 줄인다.

위의 배열은 먼저 서로 4칸씩 떨어진 원소를 꺼내어 4개의 그룹으로 나누고 그룹별로 정렬한다. 이런 방법을 '4 - 정렬'이라고 한다. 아직 정렬을 마치지 않았지만 정렬의 상태와 가까워졌다.

이어서 2칸 떨어진 원소를 모두 꺼내 '2 - 정렬'을 진행한다.

이후 '1 - 정렬'을 적용하면 오른차순 정렬이 완료된다. 

삽입 정렬에 비해 정렬 횟수는 늘어나지만 전체적으로 원소의 이동 횟수가 줄어들어 효율적이다.

 

<code>

def shell_sort(a):
    n = len(a)
    h = n // 2 # h의 초깃값은 배열의 절반값이다 while문을 반복할 때마다 2배씩 줄어든다.
    while h > 0:
        for i in range(h, n):   # 5~12행은 단순 삽입 정렬을 수행하는 과정이다. 다른점은 주목 원소와 비교 원소가 h개만큼 떨어져 있다는 것.
            j = i - h
            tmp = a[i]
            while j >= 0 and a[j] > tmp:
                a[j + h] = a[j]  # 한 칸 뒤로 
                j -= h
            a[j + h] = tmp
        h //= 2
        
if __name__ == '__main__':
    print('셸 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요 : '))
    x = [None] * num
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))
        
    shell_sort(x)
    
    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')

 

부분 집합으로 나누는 h의 초깃값은 전체 배열의 절반값이다. while 문을 반복할 때마다 다시 2로 나눈 값으로 업데이트한다. 즉, 원소 수가 8이면 4, 2, 1순으로 변화하고, 7이면 3, 1순으로 변한다.

 

셸 정렬의 시간 복잡도는 O(n^1.25)이고 단순 정렬의 시간 복잡도인 O(n^2)보다 매우 빠르다. 그러나 셸 정렬 알고리즘은 이웃하지 않고 떨어져 있는 원소를 서로 교환하므로 안정적이지 않다.

---

퀵 정렬 정의

퀵 정렬(suick sort)은 가장 빠른 정렬 알고리즘으로 알려져 있으며 널리 사용된다. 

배열 안의 한 원소(요소)를 선택하는 데, 이 원소를 pivot이라고 한다. pivot을 기준으로 pivot보다 작은 원소들은 왼쪽  그룹으로 큰 원소들은 오른쪽 그룹으로 옮긴다. 다시 각 그룹에서 pivot을 선택하여 나누기를 반복하고 모든 그룹이 1명씩 남으면 정렬이 완료된다

1. 배열을 두 그룹으로 나누기

5

7

1

4

6

2

3

9

8

위의 배열에서 6을 pivot으로 선택하여 그룹을 나눈다. pivot을 x, 왼쪽 끝 원소의 인덱스를 pl, 오른쪽을 pr이라고 하겠다.

그룹을 나누려면 pivot 이하인 원소를 배열 왼쪽(맨 앞쪽)으로, 피벗 이상인 원소를 배열 오른쪽(맨 뒤쪽)으로 이동시켜야 한다. 

 

- a[pl] >= x 가 성립하는 원소를 찾을 때까지 pl을 오른쪽 방향으로 스캔한다.

- a[pr] <= x 가 성립하는 원소를 찾을 때까지 pr을 왼쪽 방향으로 스캔한다.

 

이 과정을 거치면 pl은 x보다 큰 a[1], pr은 x보다 작은 a[6]에서 멈추고, pl과 pr 서로의 값을 교환한다. 다시 스캔을 진행한다.

pl과 pr이 교차하면 이로써 그룹을 나누는 과정이 끝나고, 배열은 다음과 같은 두 그룹으로 나뉜다.

 

- pivot 이하의 그룹 :  a[0], ... a[pl - 1]

- pivot 이상의 그룹 :  a[pr + 1], ... a[n - 1]

 

 

배열을 두 그룹으로 나누는 소스코드.

<code>

def partition(a):
    n = len(a)
    pl = 0
    pr = n - 1
    x = a[n // 2]
    
    while pl <= pr:
        while a[pl] < x: pl += 1
        while a[pr] > x: pr -= 1
        
        if pl <= pr:
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1
            
    
    print(f'피벗은 {x}입니다.')
    
    print('피벗 이하인 그룹입니다.')
    print(*a[0 : pl])
    
    if pl > pr + 1:
        print('피벗과 일치하는 그룹입니다.')
        print(*a[pr+1 : pl])
        
    print('피벗 이상인 그룹입니다.')
    print(*a[pr + 1 : n])
    

if __name__ == '__main__':
    print('배열을 나눕니다.')
    num = int(input('원소 수를 입력하세요 : '))
    x = [None] * num
    
    for i in range(num):
        x[i] = int(input(f'x[{i}] : '))
        
    partition(x)

• 이 프로그램에선 배열 가운데에 있는 원소를 pivot으로 정했다. 어떤 값을 pivot으로 정하느냐에 따라 배열을 나누는 것과 정렬하는 성능에 영향을 미친다.

 

2. 퀵 정렬 만들기

배열을 두 그룹으로 나누는 과정을 조금 더 발전시키면 퀵 정렬 알고리즘이 된다.

위의 그림을 보면 원소가 9개인 배열 a를 나누면 그림 a처럼 a[0]~a[4]인 그룹과 a[5]~a[8]인 그룹으로 나뉜다.  그리고 그림 b, c처럼 나누어진 두 그룹에 같은 과정을 적용하여 다시 나눈다. 

 

원소 수가 1개인 그룹은 더 이상 나눌 필요가 없으므로 원소 수가 2개 이상인 그룹만 다음과 같이 반복해서 나눈다.

 

• pr가 a[0]보다 오른쪽에 위치하면 (left < pr) 왼쪽 그룹을 나눈다.
• pl이 a[8]보다 왼쪽에 위치하면 (pl < right) 오른쪽 그룹을 나눈다.

 

퀵 정렬은 퀸 문제와 같은 분할 정복 알고리즘이므로 재귀 호출을 사용하여 구현할 수 있다.

 

<code>

def qsort(a, left, right):
    '''a[left] ~ a[right]를 정렬'''
    pl = left
    pr = right
    x = a[(left + right) // 2]    # pivot
    
    while pl <= pr:
        while a[pl] < x: pl += 1
        while a[pr] > x: pr -= 1
        if pl <= pr:
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1
    
    #재귀 호출 추가
    if left < pr: qsort(a, left, pr)
    if pl < right: qsort(a, pl, right)
    
def quick_sort(a):
    '''퀵 정렬'''
    qsort(a, 0, len(a) - 1)
    
if __name__ == '__main__':
    print('퀵 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요 : '))
    x = [None] * num
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))
        
    quick_sort(x)
    
    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')

 

 

비재귀적인 퀵 정렬은 재귀 함수 recur()를 비재귀적으로 구현하는 방법과 같이 만들 수 있다.

<code>

from stack import Stack

def qsort(a, left, right):
    '''a[left] ~ a[right]를 정렬'''
    range = Stack(right - left + 1)    # 스택 생성
    
    range.push((left, right))
    
    while not range.is_empty():
        pl, pr = left, right = range.pop()    # 왼쪽, 오른쪽 커서를 꺼냄
        x = a[(left + right) // 2]
    
    while pl <= pr:
        while a[pl] < x: pl += 1
        while a[pr] > x: pr -= 1
        if pl <= pr:
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1
    
    if left < pr: range.push((left, pr))
    if pl < right: range.push((pl, right))
    
def quick_sort(a):
    '''퀵 정렬'''
    qsort(a, 0, len(a) - 1)
    
if __name__ == '__main__':
    print('퀵 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요 : '))
    x = [None] * num
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))
        
    quick_sort(x)
    
    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')

 

---

pivot 선택하기

pivot 선택 방법은 퀵 정렬의 실행 효율에 큰 영향을 미친다.  예를 들어 아래 배열의 맨 앞 원소(8)를 pivot으로 선택한다.

8

7

6

5

4

3

2

1

0

 

이 배열은 pivot(8)만 있는 그룹과 나머지 원소 그룹으로 나누어야 한다. 하나의 원소와 그 외 나머지 원소로 나누는 것은 한쪽으로 완전히 치우친 분할을 반복하므로 빠른 정렬 속도를 기대할 수 없다.

 

빠른 정렬을 원한다면 배열을 정렬한 뒤 가운데에 위치하는 값, 즉 전체에서 중앙값을 pivot으로 하는 것이 이상적이다. 그러면 배열이 한쪽으로 치우치지 않고 절반 크기로 나누어진다.  하지만 정렬된 배열의 중앙값을 구하려면 그에 대한 처리가 필요하고, 처리를 위해 많은 계산 시간이 걸린다. 결국 pivot을 선택하는 의미가 없어진다.

 

최악의 경우를 피하는 방법 : 나누어야 할 배열의 맨 앞 원소, 가운데 원소, 맨 끝 원소를 정렬한 뒤 가운데 원소와 맨 끝에서 두 번째 원소를 교환한다. 맨 끝에서 두 번째 원솟값 a[right - 1]이 피벗으로 선택되었고, 그 동시에 나눌 대상을 a[left + 1] ~ a[right - 2]로 좁힌다.

퀵 정렬의 시간 복잡도

퀵 정렬은 배열은 조금씩 나누어 보다 작은 문제를 푸는 과정을 반복하므로 시간 복잡도는 O(n log n)이다. 그런데 정렬하는 배열의 초깃값이나 피벗을 선택하는 방법에 따라 실행시간 복잡도가 증가하는 경우도 있다. 예를 들어 매번 1개의 원소와 나머지 원소로 나누어진다면 n번의 분할이 필요하다. 이러한 최악의 경우 O(n^2)이 된다. 그래서 원소 수가 9개 미만인 경우 단순 삽입 정렬로 전환한다.

---

병합정렬의 정의

병합정렬(merge sort)은 배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘이다. 

 

정렬을 마친 배열의 병합

쪼개진 두 배열이 정렬을 마친 후 병합하는 과정을 살펴본다. 각 배열에서 주목하는 원소의 값을 비교하여 작은 쪽의 원소를 꺼내 새로운 배열에 저장한다. 이 작업을 반복하며 정렬을 마친 배열을 만든다. 

<예제 code>

위의 코드는 3개의 반복문을 늘어놓는 단순한 병합 알고리즘이다. 병합하는 데 필요한 시간 복잡도는 O(n)이다.

def merge_sorted_list(a, b, c):
    pa, pb, pc = 0, 0, 0     # 각 배열의 커서(인덱스)
    na, nb, nc = len(a), len(b), len(c)    # 각 배열의 원소 수
    
    while pa < na and pb < nb:    # pa와 pb를 비교하여 더 작은 값을 pc에 저장
        if a[pa] <= b[pb]:
            c[pc] = a[pa]
            pa += 1
        else:
            c[pc] = b[pb]
            pb += 1
        pc += 1
        
    while pa < na:    # a에 남은 원소를 c에 복사 (남은 찌꺼기 c에 넣기)
        c[pc] = a[pa]
        pa += 1
        pc += 1
        
    while pb < nb:
        c[pc] = b[pb]
        pb += 1
        pc += 1
        
if __name__ == '__main__':
    a = [2, 4, 6, 8, 11, 13]
    b = [1, 2, 3, 4, 9, 16, 21]
    c = [None] * (len(a) + len(b))
    
    merge_sorted_list(a, b, c)
    
    print('배열 a와 b를 병합하여 배열 c에 저장했습니다.')
    print(f'배열 a : {a}')
    print(f'배열 b : {b}')
    print(f'배열 c : {c}')

 

 

c = list(sorted(a + b))

 

import heapq
c = list(heapq.merge(a, b))

 

파이썬의 내장함수인 sorted()를 통해 쉽게 적용할 수 있지만 속도가 상대적으로 느리다. 빠르게 병합하려면 heapq 모듈의 merge() 함수를 사용하면 된다.

 

 

 

병합 정렬 만들기

정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬이라고 한다. 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 뒤 병합하여 배열 정렬을 완료한다.

병합 정렬 알고리즘의 순서는 다음과 같이 정리할 수 있다.

배열의 원소 수가 2개 이상인 경우 1. 배열의 앞부분을 병합 정렬로 정렬한다. 2. 배열의 뒷부분을 병합 정렬로 정렬한다. 3. 배열의 앞부분과 뒷부분을 병합한다.

 

<code>

from typing import MutableSequence

def merge_sort(a: MutableSequence) -> None:
    """병합 정렬"""

    def _merge_sort(a: MutableSequence, left: int, right: int) -> None:
        """a[left] ~ a[right]를 재귀적으로 병합 정렬"""
        if left < right:
            center = (left + right) // 2

            _merge_sort(a, left, center)            # 배열 앞부분을 병합 정렬
            _merge_sort(a, center + 1, right)       # 배열 뒷부분을 병합 정렬

            p = j = 0
            i = k = left

            while i <= center:
                 buff[p] = a[i]
                 p += 1
                 i += 1

            while i <= right and j < p:
                 if buff[j] <= a[i]:
                     a[k] = buff[j]
                     j += 1
                 else:
                     a[k] = a[i]
                     i += 1
                 k += 1

            while j < p:
                a[k] = buff[j]
                k += 1
                j += 1

    n = len(a)
    buff = [None] * n           # 작업용 배열을 생성
    _merge_sort(a, 0, n - 1)    # 배열 전체를 병합 정렬
    del buff                    # 작업용 배열을 소멸

if __name__ == '__main__':
    print('병합 정렬을 수행합니다')
    num = int(input('원소 수를 입력하세요.: '))
    x = [None] * num    # 원소 수가 num인 배열을 생성

    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))

    merge_sort(x)       # 배열 x를 병합 정렬

    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')

배열 병합의 시간 복잡도는 O(n)이다. 데이터 원소 수가 n일 때 병합 정렬의 단계는 log n만큼 필요하므로 전체 시간 복잡도는 O(n log n)이다. 병합 정렬 알고리즘은 서로 떨어져 있는 원소를 교환하는 것이 아니므로 안정적이다.

---

힙 정렬의 개념

힙 정렬(heap sort)은 힙의 특성을 이용하여 정렬하는 알고리즘이다. 힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진 트리이다. 이때 부모의 값이 자식의 값보다 항상 작아도 힙이라고 한다. 즉, 두 값의 대소 관계가 일정하면 된다.

힙에서 부모와 자식 관계는 일정하지만 형제(sibling)사이의 대소 관계는 일정하지 않다. 

위의 사진은 힙의 원소를 배열에 어떻게 저장할 것인지를 나타낸다. 먼저 가장 위쪽에 있는 루트(10)를 저장하고, 한 단계 아래에서 왼쪽부터 배열의 인덱스 값을 1씩 증가시키면서 각 원소를 저장한다. 가장 마지막에 있는 원소 1까지 반복하여 힙을 배열에 저장하면 완료된다.

 

이러한 순서로 힙을 배열에 저장하면 다음과 같은 부모 인덱스와 왼쪽, 오른쪽 자식간에 다음과 같은 관계가 성립한다.

원소 a[i]에서 -  부모 : a[(i - 1) // 2] -  왼쪽 자식 : a[i * 2 + 1] -  오른쪽 자식 : a[i * 2 + 2]

 

힙 정렬 특징

힙 정렬은 '힙에서 최댓값은 루트에 위치한다'는 특징을 이용하여 정렬하는 알고리즘이다. 다음과 같은 작업을 반복한다.

-  힙에서 최댓값인 루트를 꺼낸다.

-  루트 이외의 부분을 힙으로 만든다.

이 과정에서 꺼낸 값을 나열하면 정렬이 끝난 배열이 완성된다. 즉, 힙 정렬은 선택 정렬을 응용한 알고리즘이다.

또한 힙 정렬에서 최댓값인 루트를 꺼낸 뒤 다시 남은 원소 중에서 최댓값을 구해야 한다. (남은 원소로 구성한 트리도 힙이 되도록 재구성)

 

 

루트를 삭제한 힙의 재구성

루트를 삭제하고 다시 힙으로 만들기 위해 원소를 알맞은 위치로 이동하는 순서는 다음과 같다.

 

1. 루트를 꺼낸다.

2. 마지막 원소(가장 하단의 오른쪽에 위치한)를 루트로 이동한다.

3. 루트에서 시작하여 자신보다 값이 큰 자식과 자리를 바꾸고 아래쪽으로 내려가는 작업을 반복한다. 자식의 값이 작거나 리프의 위치에 도달하면 종료한다.

 

힙 정렬 알고리즘의 흐름을 이해해본다면 (n값은 배열의 원소 수, i값은 배열의 마지막 인덱스)

1. i값을 n - 1로 초기화

2. a[0]과 a[i]를 교환

3. a[0], a[1] ,,,, a[i - 1]을 힙으로 만든다.4. i값을 1씩 감소시켜 0이 되면 종료한다. 그렇지 않으면 2로 돌아간다.

 

 

배열을 힙으로 만들기

위 그림과 같은 이진 트리가 있다고 가정하자. 루트가 4인 서브트리 A는 힙이 아니다. 그러나 4의 왼쪽 자식과 오른쪽 자식을 루트로 하는 서브트리 B와 C는 모두 힙 상태이다. 루트를 삭제한 힙을 재구성하려면 마지막 원소를 루트로 이동시켜 알맞은 위치까지 아래로 옮겨야 한다. 즉, 루트 4를 알맞은 위치까지 아래로 옮기면 서브트리 A를 힙으로 만들 수 있다.

 

이 방법을 사용하면 가장 아랫부분의 작은 서브트리부터 상향식(bottom up)으로 진행하여 전체 배열을 힙으로 만들 수 있다. 가장 아랫부분의 오른쪽 서브트리의 힙을 만들고, 왼쪽 서브트리로 진행한다. 그 단계를 완료하면 한 단계 위로 이동하면서 각각의 서브트리를 힙으로 만든다.

<code>

# [Do it! 실습 6-16] 힙 정렬 알고리즘 구현하기

from typing import MutableSequence

def heap_sort(a: MutableSequence) -> None:
    """힙 정렬"""

    def down_heap(a: MutableSequence, left: int, right: int) -> None:
        """a[left] ~ a[right]를 힙으로 만들기"""
        temp = a[left]      # 루트

        parent = left
        while parent < (right + 1) // 2:
            cl = parent * 2 + 1     # 왼쪽 자식
            cr = cl + 1             # 오른쪽 자식
            child = cr if cr <= right and a[cr] > a[cl] else cl  # 큰 값을 선택합니다.
            if temp >= a[child]:
                break
            a[parent] = a[child]
            parent = child
        a[parent] = temp

    n = len(a)

    for i in range((n - 1) // 2, -1, -1):   # a[i] ~ a[n-1]을 힙으로 만들기
        down_heap(a, i, n - 1)

    for i in range(n - 1, 0, -1):
        a[0], a[i] = a[i], a[0]     # 최댓값인 a[0]과 마지막 원소 a[i]를 교환
        down_heap(a, 0, i - 1)      # a[0] ~ a[i-1]을 힙으로 만들기

if __name__ == '__main__':
    print('힙 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요. : '))
    x = [None] * num    # 원소 수가 num인 배열을 생성

    for i in range(num):
        x[i] = int(input(f'x[{i}] : '))

    heap_sort(x)        # 배열 x를 힙 정렬

    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')

 

 

힙 정렬 시간 복잡도

단순 선택 정렬은 아직 정렬하지 않은 모든 원소 중에서 최댓값을 선택한다. 힙 정렬은 맨 앞 원소를 꺼내는 것만으로 최댓값을 구할 수 있지만 남은 원소를 힙으로 재구성해야 한다.

단순 선택 정렬에서 최갯값인 원소를 선택하는 시간 복잡도는 O(n)이지만, 힙 정렬에서 다시 힙으로 만드는 작업의 시간 복잡도는 O(log n)이다.

 

따라서 단순 선택 정렬의 시간 복잡도는 O(n^2)이지만, 힙 정렬은 원소의 개수만큼 작업을 반복하므로 전체 정렬하는 데 걸리는 시간 복잡도는 O(n log n)으로 크게 줄어든다.