파이썬 자료구조 6-3장. 정렬 알고리즘 3

in Python on Data Structure

1. 병합 정렬

병합 정렬은 배열을 앞부분과 뒷부분의 두 그룹으로 나누너 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘이다. 배열 병합의 시간 복잡도는 O(n)이고 데이터 원소 수가 n 일 때 병합 정렬의 단계는 log n만큼 필요하므로 전체 시간 복잡도는 O(n log n)이다. 서로 떨어져있는 원소를 교환하는 것이 아니므로 안정적이다.
알고리즘 순서(배열의 원소가 2개 이상인 경우)

  1. 배열의 앞부분을 병합 정렬로 정렬한다.
  2. 배열의 뒷부분을 병합 정렬로 정렬한다.
  3. 배열의 앞부분과 뒷부분을 병합한다.
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)       # 배열 뒷부분을 병합 정렬
            
            # 재귀적 구현에서는 재귀 대상의 list 인덱스를 0,1,2 로 보면 안된다.
            # 재귀 될 때마다 원래 list의 부분으로 나뉘어지기 때문에
            # 원래 list의 인덱스와 다른 인덱스이다.
            # 예를 들어 a[0~4] a[5~8] 로 나뉘었는데 a[5~8]에서 
            # 인덱스를 left가 아니라 0으로 사용한다면 전혀 다른 곳을 참조하게 된다.            
            # 따라서 재귀적 구현에서 재귀 대상 list의 인덱스는 인자로 받은 것을 사용해야 한다.
            
            p = j = 0
            i = k = left

            # 배열 앞부분 buff로 옮기기
            while i <= center:
                 buff[p] = a[i]
                 p += 1
                 i += 1

            # 다시 a 배열로 가져오면서 비교하기
            while i <= right and j < p: # j가 p를 넘을경우 none으로 비교 불가
                 if buff[j] <= a[i]:
                     a[k] = buff[j]
                     j += 1
                 else:
                     a[k] = a[i]
                     i += 1
                 k += 1
            # 남은 것 옮기기
            # buff가 먼저 다 옮겼으면 뒤에는 자동으로 뒤에는 a에 있던 그대로 
            # buff가 남으면 buff는 a로 옮겨줘야함
            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                    # 작업용 배열을 소멸

a = [5,8,4,2,6,1,3,9,7]
merge_sort(a)
print(a)


2. 힙 정렬

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

원소 a[i]에서 부모 노드와 자식 노드의 관계

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

특징

힙 정렬은 ‘힙에서 최댓값은 루트에 위치한다’는 특징을 이용하여 정렬한다. 구체적으로 아래 작업을 반복한다.

  1. 힙에서 최댓값인 루트를 꺼낸다.
  2. 루트 이외의 부분을 힙으로 만든다.

이 과정에서 꺼낸 값을 나열하면 정렬이 끝난 배열이 완성된다. 즉, 힙 정렬은 선택 정렬을 응용한 알고리즘이다.
또한 힙 정렬에서 최댓값인 루트를 꺼낸 뒤 다시 남은 원소 중에서 최댓값을 구해야한다. 만약 원소 10개에서 최댓값을 꺼내면 남은 9개의 원소에서 다시 최댓값을 구해야한다. 따라서 남은 9개의 원소로 구성한 트리도 힙이 되도록 재구성해야한다.

루트를 삭제한 힙의 재구성

  1. 루트를 꺼낸다.
  2. 마지막 원소(가장 하단의 오른쪽에 위치한 원소)를 루트로 이동한다.
  3. 루트에서 시작하여 자신보다 값이 큰 자식과 자리를 바꾸고 아래쪽으로 내려가는 작업을 반복한다. 자식의 값이 작거나 리프(단말 노드)에 도달하면 종료한다.

힙 정렬 알고리즘

  1. i값을 n-1로 초기화한다.
  2. a[0]과 a[i]를 교환한다.
  3. a[0], a[1] ~ a[i-1]을 힙으로 만든다.
  4. i값을 1씩 감소시켜 0이되면 종료한다.

구현

def heap_sort(a):
    # a[left~right]를 힙으로 만들기
    # left이외에는 모두 힙 상태라고 가정하고 left을 알맞은 위치로 옮기는 함수
    def down_heap(a,left,right): 
        tmp = a[left] # 부모 노드
        
        while left <= (right-1)//2: # 제시된 범위내에서 (right-1)//2 는 마지막 부모 노드
            # while 조건문을 통과한 순간 부모 노드인 것을 확인한 것
            # 부모노드이므로 최소한 왼쪽 자식 노드는 가지고 있음
            cr = left*2+2 # 오른쪽 자식 노드
            cl = left*2+1 # 왼쪽 자식 노드
            # 오른쪽 자식 노드가 없을 수도 있으므로 조건에 넣어줘야함
            big_child = cr if cr<=right and a[cl]<a[cr] else cl
            if a[left] < a[big_child]:
                a[left] = a[big_child]
                left=big_child # big_child가 부모노드일 경우 다시 while문이 성립
            else :
                break
        a[left]=tmp
    
    n = len(a)
    
    # 힙 만들기    
    # 마지막 부모 노드부터 힙으로 만들면서 위로 올라감
    for i in range((n-2)//2,0-1,-1):
        down_heap(a,i,n-1)
    
    # 힙 상태에서 루트노드를 하나씩 배열 맨 마지막으로 옮기며 정렬하기
    for i in range(n-1,0,-1): # 인덱스 1까지 마치면 자동으로 인덱스 0에 최솟값이 있으므로 1까지만
        a[0],a[i] = a[i],a[0]
        # a[i]는 정렬완료
        # 루트노드와 마지막 노드를 스왑했으므로 
        # 마지막 노드를 제외한 부분을 다시 힙 상태로 만들기
        down_heap(a,0,i-1)

a = [6,4,3,7,1,9,8]
heap_sort(a)
print(a)

힙 정렬의 시간 복잡도

힙 정렬에서 다시 힙으로 만드는 작업의 시간 복잡도는 O(log n)이다. 따라서 원소의 개수만큼 작업을 반복하므로 전체 정렬하는데 걸리는 시간 복잡도는 O(n log n)이다.

heapq 모듈을 사용하는 힙 정렬

파이썬의 heapq 모듈은 힙에 원소를 추가하는 heappush() 함수와 힙에서 원소를 제거하는 heappop() 함수를 제공한다. 이때 푸시와 팝은 힙의 조건을 유지하며 수행된다. 따라서 이를 활용하면 쉽게 힙 정렬을 구현할 수 있다.

import heapq

def heap_sort(a):
    heap = []
    for i in a:
        heapq.heappush(heap,i)
    for i in range(len(a)):
        a[i] = heapq.heappop(heap)

a = [1,8,5,3,4,0,9,1]
heap_sort(a)
print(a)


3. 도수 정렬

원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘으로 분포수 세기 정렬이라고도 한다. 단일 for문만 사용하고 재귀 호출이나 이중 if문 없이 사용할 수 있어 매우 빠르지만 도수 분포표가 필요하므로 최댓값과 최솟값을 미리 알고 있는 경우에만 적용할 수 있다.
10점 만점 테스트에서 학생 9명의 도수를 정렬하는 알고리즘을 나타내보자.

  1. a=[5,7,0,2,4,10,3,1,3] 이 9명 각각의 점수라고 하고 도수 분포표(점수표) 즉, 인덱스값이 점수인 f[11] 배열을 만들고 0으로 초기화한다.
  2. f[점수] +=1 을 해주면서 도수 분포표(점수표)를 만든다.
  3. f[i]+=f[i-1]을 통해 f배열을 누적 분포표로 만든다.
  4. 정렬하기 위해 a와 크기가 같은 새로운 배열 b를 만들고 a의 마지막부터 f와 대조한다.
  5. a[8]=3 이므로 f[3]를 주목하면 f[3]=5이다. 즉, 0~3점은 5명이란 뜻이다.
  6. f[3]-=1 을 한 뒤 b[f[3]]에 대입하면 된다.(인덱스0부터 시작이므로 -1해야 자신위치를 찾을 뿐만 아니라 중복처리)
  7. 이후는 똑같이 인덱스 0까지 반복하면 된다.

a의 맨 마지막부터 f와 대조하는 이유
맨 마지막부터 f와 대조를 해야 안정적이기 때문이다. a의 맨 처음 인덱스부터 비교하게 되면 a[6]=3과 a[8]=3의 위치가 역전되게 된다.

구현

def fsort(a,max):
    f = [0]*(max+1) # 0점도 포함을 위해 +1
    n = len(a)
    b = [0]*n
    for i in range(n): # 도수 분포표
        f[a[i]]+=1
    for i in range(1,max+1): # 누적 분포표
        f[i]+=f[i-1]
    for i in range(n-1,0-1,-1):
        f[a[i]]-=1
        b[f[a[i]]]=a[i]
    for i in range(n):
        a[i]=b[i]
    
def counting_sort(a):
    fsort(a,max(a))

a = [22,5,11,32,99,68,70]
counting_sort(a)
print(a)


전역변수 지역변수 참고사항

위에 함수에서 
for i in range(n):
        a[i]=b[i]
대신 a=b를 사용하면 같은 결과를 내지 못한다.
여기서 a=b를 해버리면 인자로 받은 리스트 a에 리스트b를 대입하는 것이 아니라
새로운 변수(지역변수) a를 선언하고 리스트를 참조하는 꼴이 된다.
즉, 밖에 있는 a와는 전혀 다른 a가 만들어지는 것이다.
따라서 인자로 받은 리스트 a를 수정하고 싶다면 인덱스 값을 이용해 수정해야한다.


© 2021. By Backtony