정렬 알고리즘 - 2

오늘은 남은 셸 정렬, 퀵 정렬, 병합 정렬, 힙 정렬, 도수 정렬을 정리합니다. :)

 

1. 셸 정렬

단순 삽입 정렬의 업그레이드 판입니다. (아쉽게도 백준에서 쉬운 예제를 찾지 못했습니다. 😩)

아주 쉬운 예를 들면,

단순 삽입 정렬의 겨우, [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 배열을  정렬할 때, 바로 옆의 값을 확인하고 교환하다보니 54번의 저장이 이루어집니다. 

#예시 코드 및 결과

import sys
n, k = 10, 54
a = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
n = len(a)
count = 0
flag1 = False
for i in range(1, n):
    if k == 0:
        break
    j = i
    tmp = a[i]
    flag2 = False #대소관계가 정렬되어 있는지 확인
    while j > 0 and a[j - 1] > tmp:
        print(a, count)
        count += 1
        flag2 = True  #대소관계가 정렬되어 있는지 확인 했을 때 정렬 되어있지 않은 경우
        k -= 1  #대소관계가 정렬되어 있는지 확인 했을 때 정렬 되어있지 않은 경우 변화했기 때문에 k - 1
        a[j] = a[j - 1]
        if k == 0:
            flag1 = False
            break
        j -= 1
    if k == 0:
        break
    if flag2: #대소관계가 정렬되어 있는지 확인 했을 때 정렬 되어있지 않은 경우 재정렬한 k - 1
        print(a, count)
        count += 1
        k -= 1
    a[j] = tmp

print(a, count)
if k == 0:
    print(a[j])
else:
    print(-1)

[10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 0
[10, 10, 8, 7, 6, 5, 4, 3, 2, 1] 1
[9, 10, 8, 7, 6, 5, 4, 3, 2, 1] 2
[9, 10, 10, 7, 6, 5, 4, 3, 2, 1] 3
[9, 9, 10, 7, 6, 5, 4, 3, 2, 1] 4
[8, 9, 10, 7, 6, 5, 4, 3, 2, 1] 5
[8, 9, 10, 10, 6, 5, 4, 3, 2, 1] 6
[8, 9, 9, 10, 6, 5, 4, 3, 2, 1] 7
[8, 8, 9, 10, 6, 5, 4, 3, 2, 1] 8
[7, 8, 9, 10, 6, 5, 4, 3, 2, 1] 9
[7, 8, 9, 10, 10, 5, 4, 3, 2, 1] 10
[7, 8, 9, 9, 10, 5, 4, 3, 2, 1] 11
[7, 8, 8, 9, 10, 5, 4, 3, 2, 1] 12
[7, 7, 8, 9, 10, 5, 4, 3, 2, 1] 13
[6, 7, 8, 9, 10, 5, 4, 3, 2, 1] 14
[6, 7, 8, 9, 10, 10, 4, 3, 2, 1] 15
[6, 7, 8, 9, 9, 10, 4, 3, 2, 1] 16
[6, 7, 8, 8, 9, 10, 4, 3, 2, 1] 17
[6, 7, 7, 8, 9, 10, 4, 3, 2, 1] 18
[6, 6, 7, 8, 9, 10, 4, 3, 2, 1] 19
[5, 6, 7, 8, 9, 10, 4, 3, 2, 1] 20
[5, 6, 7, 8, 9, 10, 10, 3, 2, 1] 21
[5, 6, 7, 8, 9, 9, 10, 3, 2, 1] 22
[5, 6, 7, 8, 8, 9, 10, 3, 2, 1] 23
[5, 6, 7, 7, 8, 9, 10, 3, 2, 1] 24
[5, 6, 6, 7, 8, 9, 10, 3, 2, 1] 25
[5, 5, 6, 7, 8, 9, 10, 3, 2, 1] 26
[4, 5, 6, 7, 8, 9, 10, 3, 2, 1] 27
[4, 5, 6, 7, 8, 9, 10, 10, 2, 1] 28
[4, 5, 6, 7, 8, 9, 9, 10, 2, 1] 29
[4, 5, 6, 7, 8, 8, 9, 10, 2, 1] 30
[4, 5, 6, 7, 7, 8, 9, 10, 2, 1] 31
[4, 5, 6, 6, 7, 8, 9, 10, 2, 1] 32
[4, 5, 5, 6, 7, 8, 9, 10, 2, 1] 33
[4, 4, 5, 6, 7, 8, 9, 10, 2, 1] 34
[3, 4, 5, 6, 7, 8, 9, 10, 2, 1] 35
[3, 4, 5, 6, 7, 8, 9, 10, 10, 1] 36
[3, 4, 5, 6, 7, 8, 9, 9, 10, 1] 37
[3, 4, 5, 6, 7, 8, 8, 9, 10, 1] 38
[3, 4, 5, 6, 7, 7, 8, 9, 10, 1] 39
[3, 4, 5, 6, 6, 7, 8, 9, 10, 1] 40
[3, 4, 5, 5, 6, 7, 8, 9, 10, 1] 41
[3, 4, 4, 5, 6, 7, 8, 9, 10, 1] 42
[3, 3, 4, 5, 6, 7, 8, 9, 10, 1] 43
[2, 3, 4, 5, 6, 7, 8, 9, 10, 1] 44
[2, 3, 4, 5, 6, 7, 8, 9, 10, 10] 45
[2, 3, 4, 5, 6, 7, 8, 9, 9, 10] 46
[2, 3, 4, 5, 6, 7, 8, 8, 9, 10] 47
[2, 3, 4, 5, 6, 7, 7, 8, 9, 10] 48
[2, 3, 4, 5, 6, 6, 7, 8, 9, 10] 49
[2, 3, 4, 5, 5, 6, 7, 8, 9, 10] 50
[2, 3, 4, 4, 5, 6, 7, 8, 9, 10] 51
[2, 3, 3, 4, 5, 6, 7, 8, 9, 10] 52
[2, 2, 3, 4, 5, 6, 7, 8, 9, 10] 53
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 54

하지만 셸 정렬의 경우  바로 옆이 아닌 먼거리에 있는 수와 교환하기 때문에 훨씬 적은 23번의 저장만이 이루어졌습니다.

 

#예시 코드 및 결과

import sys
n = 10
a = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
count = 0

h = n // 2
while h > 0:
    for i in range(h,n):
        j = i - h
        tmp = a[i]
        flag = False
        while j >= 0 and a[j] > tmp:
            flag = True
            a[j + h] = a[j]
            print(a, count)
            count += 1
            j -= h
        a[j + h] = tmp
        if flag:
            print(a, count)
            count += 1
    h //= 2

[10, 9, 8, 7, 6, 10, 4, 3, 2, 1] 0
[5, 9, 8, 7, 6, 10, 4, 3, 2, 1] 1
[5, 9, 8, 7, 6, 10, 9, 3, 2, 1] 2
[5, 4, 8, 7, 6, 10, 9, 3, 2, 1] 3
[5, 4, 8, 7, 6, 10, 9, 8, 2, 1] 4
[5, 4, 3, 7, 6, 10, 9, 8, 2, 1] 5
[5, 4, 3, 7, 6, 10, 9, 8, 7, 1] 6
[5, 4, 3, 2, 6, 10, 9, 8, 7, 1] 7
[5, 4, 3, 2, 6, 10, 9, 8, 7, 6] 8
[5, 4, 3, 2, 1, 10, 9, 8, 7, 6] 9
[5, 4, 5, 2, 1, 10, 9, 8, 7, 6] 10
[3, 4, 5, 2, 1, 10, 9, 8, 7, 6] 11
[3, 4, 5, 4, 1, 10, 9, 8, 7, 6] 12
[3, 2, 5, 4, 1, 10, 9, 8, 7, 6] 13
[3, 2, 5, 4, 5, 10, 9, 8, 7, 6] 14
[3, 2, 3, 4, 5, 10, 9, 8, 7, 6] 15
[1, 2, 3, 4, 5, 10, 9, 8, 7, 6] 16
[1, 2, 3, 4, 5, 10, 9, 10, 7, 6] 17
[1, 2, 3, 4, 5, 8, 9, 10, 7, 6] 18
[1, 2, 3, 4, 5, 8, 9, 10, 9, 6] 19
[1, 2, 3, 4, 5, 8, 7, 10, 9, 6] 20
[1, 2, 3, 4, 5, 8, 7, 10, 9, 10] 21
[1, 2, 3, 4, 5, 8, 7, 8, 9, 10] 22
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 23

(예시 코드에선 쉬운 이해를 위해 h의 값을 h // 2 로 사용했지만 보통의 경우 효율을 위해 배수가 되지 않는 h * 3 + 1 의 수열을 사용합니다.)

이렇게 단순 삽입 정렬에 비해 셸 정렬은 훨씬 빠른 성능을 보여주지만 ( 시간 복잡도: 단순 삽입 정렬 O(n**2), 셸  O(n**1.25) ) 떨어져 있는 원소와 교환한다는 점에서 안정적이지 않다는 단점이 있습니다.

 

 

2. 퀵 정렬

퀵 정렬은 가장 빠른 알고리즘으로 알려져 있습니다.

그룹을 나누는 기준, 피봇(pivot)을 선택해 나누기를 반복하며 모든 그룹이 한 개의 원소만 남았을 때 정렬이 완료됩니다.

분할 정복 알고리즘의 응용으로 재귀를 사용해 구현할 수도 스택 자료구조를 이용해 비재귀적으로 구현할 수도 있습니다.

이 때 배열을 스택에 푸쉬 할 경우 다음의 두 가지 규칙을 갖습니다.

• 규칙 1: 원소 수가 많은 쪽의 그룹을 먼저 푸시한다.
• 규칙 2: 원소 수가 적은 쪽의 그룹을 먼저 푸시한다.

따라서 스택에 쌓이는 데이터의 최대 개수가 log n보다 적습니다. 배열을 나누어 계산하기 때문에 O(n log n)을 시간 복잡도를 가지지만, 배열의 초깃값, 피벗 선택 방법에 따라 시간복잡도가 증가하고 최악의 경우 O(n**2) 시간 복잡도를 가집니다.

https://www.acmicpc.net/problem/24090

24090번: 알고리즘 수업 - 퀵 정렬 1

import sys

sys.setrecursionlimit(10 ** 4)
n, k = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))
flag = True
def swap(array, a, b):
    global k, flag
    if k == 0:
        return
    k -= 1
    array[a], array[b] = array[b], array[a]
    if k == 0:
        flag = False
        print(array[a], array[b])
        return

def partition(Arr, p, r):
    x = Arr[r]
    i = p - 1
    if k != 0:
        for j in range(p, r):
            if Arr[j] <= x:
                i += 1
                if k != 0:
                    swap(Arr, i, j)
                else:
                    break
        if i + 1 != r:
            swap(Arr, i+1, r)
    return i+1

def quick_sort(Arr, p, r):
    if p < r and k != 0:
        q = partition(Arr, p, r)
        quick_sort(Arr, p, q-1)
        quick_sort(Arr, q+1, r)
quick_sort(a,0,n - 1)

if flag:
    print(-1)

**추가적으로 배운 것.

해당 문제를 풀 때 메모리 초과로 계속해서 풀이에 실패 했습니다. 이유는 지난 번 포스팅 했던 setrecursionlimit 의 경우.  깊이 만큼 미리 스택 메모리 영역을 차지하기 때문이었고, 다음과 같이 실험해봤습니다.

 

깊이를 8000, 16000, 32000, 64000, 128000, 256000 순으로 늘렸더니 10232, 20488, 40952, 81924, 163836 KB 만큼 메모리가 증가했습니다. 이를 통해 대략 1의 스택 메모리가 1.28KB 임을 확인 할 수 있었습니다. 그럼 100만의 깊이는 대략 1280MB 를 잡아 먹기 때문에 메모리 제한이 512MB 인 이 문제는 당연히 메모리 초과가 납니다 :) 

추가적으로 확인하니 실제로 1024MB가 넘어도 문제가 통과되었습니다. :0...

결론

• 적힌 메모리 제한 보다 넉넉하게 주는 케이스도 있음.
• PyPy에서 대략 1의 스택 메모리가 1.28KB를 차지하기 때문에 재귀 깊이 제한을 잘 고려해서 설정해야함. 

 

3. 병합 정렬

병합 정렬은 배열을 앞부분과 뒷부분의 두 그룹으로 나눠 각각 정렬해 병합하는 작업을 반복하는 정렬 알고리즘입니다.

https://www.acmicpc.net/problem/24060

24060번: 알고리즘 수업 - 병합 정렬 1

import sys

n, k = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))
flag = True
def merge(a, p, q, r):
    global k, flag
    i = p
    j = q + 1
    t = 1
    while i <= q and j <= r:
        if a[i] <= a[j]:
            buff[t] = a[i]
            t += 1
            i += 1
        else:
            buff[t] = a[j]
            t += 1
            j += 1
    while i <= q:
        buff[t] = a[i]
        t += 1
        i += 1
    while j <= r:
        buff[t] = a[j]
        t += 1
        j += 1
    i = p
    t = 1
    while i <= r: #결과를 배열에 저장
        a[i] = buff[t]
        i += 1
        t += 1
        k -= 1
        if k == 0:
            print(buff[t - 1])
            flag = False
            break

def merge_sort(a, p, r) -> None:
    if p < r:
        q = (p + r) // 2
        merge_sort(a, p, q)
        merge_sort(a, q + 1, r)
        merge(a, p, q, r)

buff = [None] * (n + 1)
merge_sort(a, 0, n - 1)
if flag:
    print(-1)

4. 힙 정렬

힙의 특성을 이용한 정렬 알고리즘 입니다. 우선 힙은  우선순위에 따라 최대힙, 최소힙이 있고, 대소관계가 일정합니다.

따라서 최대힙의 경우는 트리구조에서 부모노드가 항상 자식노드 보다 크고, 반대로 채소힙의 경우 부모노드가 항상 자식노드 보다 작은 완전 이진트리의 구조를 띕니다. :) 또 원소의 개수 만큼만 작업을 반복하기 때문에 O(n long n)의 적은 시간복잡도를 가집니다.

 

https://www.acmicpc.net/problem/24173

24173번: 알고리즘 수업 - 힙 정렬 1

배열의 index 접근이기 때문에 0부터 시작하며 각 좌우의 자식 노드의 index는 (부모노드 index * 2) + 1,  (부모노드 index * 2) + 2 가 됩니다. 이해하기 편하게 사진을 준비 했습니다. :)

build min heap 

import sys

sys.setrecursionlimit(10 ** 4)
n, k = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))
flag = True


def heapify(array, parent, size):
    global k, flag
    if k == 0:
        flag = False
        return
    smallest = parent
    left = (2 * parent) + 1
    right = (2 * parent) + 2

    if (left < size) and (array[left] < array[smallest]): smallest = left
    if (right < size) and (array[right] < array[smallest]): smallest = right
    if smallest != parent:
        k -= 1

        if k == 0:
            flag = False
            print(array[smallest], array[parent])
            return
        array[parent], array[smallest] = array[smallest], array[parent]
        heapify(array, smallest, size)


def build_min_heap(a, n):
    for i in range((n // 2) - 1, -1, -1):
        heapify(a, i, n)


def heap_sort(a):
    global n, k, flag
    if k == 0:  # k 가 0이면 정렬 종료.
        flag = False
        return
    build_min_heap(a,n)

    for j in range(n - 1, 0, -1):
        if k == 0:
            flag = False
            break
        k -= 1
        if k == 0:
            print(a[0], a[j])
            flag = False
            break
        a[0], a[j] = a[j], a[0]
        heapify(a, 0, j)


heap_sort(a)  # 배열삽입

if flag:
    print(-1)

 

n = 10 배열 예를 준비했습니다. :)

5 1 2 3 4 9 8 7 10 6 배열 교환 예제

build_min_heap 시작
heapify 부모노드 index = 4 부모노드의 값 = 4
heapify 부모노드 index = 3 부모노드의 값 = 3
heapify 부모노드 index = 2 부모노드의 값 = 2
heapify 부모노드 index = 1 부모노드의 값 = 1
heapify 부모노드 index = 0 부모노드의 값 = 5
[5, 1, 2, 3, 4, 9, 8, 7, 10, 6] 부모 자식 노드 비교 후 교환되는 원소값 1 5
heapify 부모노드 index = 1 부모노드의 값 = 5
[1, 5, 2, 3, 4, 9, 8, 7, 10, 6] 부모 자식 노드 비교 후 교환되는 원소값 3 5
heapify 부모노드 index = 3 부모노드의 값 = 5
build_min_heap 종료

[1, 3, 2, 5, 4, 9, 8, 7, 10, 6] for문에서 교환되는 원소값 1 6
heapify 부모노드 index = 0 부모노드의 값 = 6
[6, 3, 2, 5, 4, 9, 8, 7, 10, 1] 부모 자식 노드 비교 후 교환되는 원소값 2 6
heapify 부모노드 index = 2 부모노드의 값 = 6
[2, 3, 6, 5, 4, 9, 8, 7, 10, 1] for문에서 교환되는 원소값 2 10
heapify 부모노드 index = 0 부모노드의 값 = 10
[10, 3, 6, 5, 4, 9, 8, 7, 2, 1] 부모 자식 노드 비교 후 교환되는 원소값 3 10
heapify 부모노드 index = 1 부모노드의 값 = 10
[3, 10, 6, 5, 4, 9, 8, 7, 2, 1] 부모 자식 노드 비교 후 교환되는 원소값 4 10
heapify 부모노드 index = 4 부모노드의 값 = 10
[3, 4, 6, 5, 10, 9, 8, 7, 2, 1] for문에서 교환되는 원소값 3 7
heapify 부모노드 index = 0 부모노드의 값 = 7
[7, 4, 6, 5, 10, 9, 8, 3, 2, 1] 부모 자식 노드 비교 후 교환되는 원소값 4 7
heapify 부모노드 index = 1 부모노드의 값 = 7
[4, 7, 6, 5, 10, 9, 8, 3, 2, 1] 부모 자식 노드 비교 후 교환되는 원소값 5 7
heapify 부모노드 index = 3 부모노드의 값 = 7
[4, 5, 6, 7, 10, 9, 8, 3, 2, 1] for문에서 교환되는 원소값 4 8
heapify 부모노드 index = 0 부모노드의 값 = 8
[8, 5, 6, 7, 10, 9, 4, 3, 2, 1] 부모 자식 노드 비교 후 교환되는 원소값 5 8
heapify 부모노드 index = 1 부모노드의 값 = 8
[5, 8, 6, 7, 10, 9, 4, 3, 2, 1] 부모 자식 노드 비교 후 교환되는 원소값 7 8
heapify 부모노드 index = 3 부모노드의 값 = 8
[5, 7, 6, 8, 10, 9, 4, 3, 2, 1] for문에서 교환되는 원소값 5 9
heapify 부모노드 index = 0 부모노드의 값 = 9
[9, 7, 6, 8, 10, 5, 4, 3, 2, 1] 부모 자식 노드 비교 후 교환되는 원소값 6 9
heapify 부모노드 index = 2 부모노드의 값 = 9
[6, 7, 9, 8, 10, 5, 4, 3, 2, 1] for문에서 교환되는 원소값 6 10
heapify 부모노드 index = 0 부모노드의 값 = 10
[10, 7, 9, 8, 6, 5, 4, 3, 2, 1] 부모 자식 노드 비교 후 교환되는 원소값 7 10
heapify 부모노드 index = 1 부모노드의 값 = 10
[7, 10, 9, 8, 6, 5, 4, 3, 2, 1] 부모 자식 노드 비교 후 교환되는 원소값 8 10
heapify 부모노드 index = 3 부모노드의 값 = 10
[7, 8, 9, 10, 6, 5, 4, 3, 2, 1] for문에서 교환되는 원소값 7 10
heapify 부모노드 index = 0 부모노드의 값 = 10
[10, 8, 9, 7, 6, 5, 4, 3, 2, 1] 부모 자식 노드 비교 후 교환되는 원소값 8 10
heapify 부모노드 index = 1 부모노드의 값 = 10
[8, 10, 9, 7, 6, 5, 4, 3, 2, 1] for문에서 교환되는 원소값 8 9
heapify 부모노드 index = 0 부모노드의 값 = 9
[9, 10, 8, 7, 6, 5, 4, 3, 2, 1] for문에서 교환되는 원소값 9 10
heapify 부모노드 index = 0 부모노드의 값 = 10
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

 

5. 도수 정렬

도수 정렬은 원소의 대소 관계를 판단하지 않고 도수분포표를 이용해 빠르게 정렬하는 알고리즘으로, 분포수 세기 정렬이라고도 합니다.