알고리즘 : 정렬 #3 (Shell Sort, Heap Sort)

지금까지 대표적인 정렬 다섯개에 대해 알아보았습니다.

이번엔 좀 더 응용된 정렬인 Shell Sort(쉘 정렬), Heap Sort(힙 정렬)에 대해 알아보겠습니다.

---

Shell Sort (쉘 정렬)

---

Shell Sort(쉘 정렬)는 Insertion Sort(삽입 정렬)를 변형한 정렬입니다.

먼저 Shell sort에는 "gap" 이 존재합니다.

이 gap을 미리 정해 두고, gap만큼 벌어진 것들 끼리 삽입 정렬을 해주는 겁니다. 그림으로 보겠습니다.

다음 배열 a[]를 정렬하려 하는데, gap을 1 ← 4 ← 13 으로 정했다고 합니다. 무슨 뜻일까요?

일단 첫 시작은 gap=13 이라니까 한번 보도록 합시다.

그러고선 앞서 정한 gap만큼 건너 뛴 원소들끼리 삽입 정렬을 해줍니다.

이 때 3번째 원소인 12의 경우, 13만큼 떨어져 있는 애가 없으므로 정렬을 안해줍니다.

이번엔 gap=4로 정렬해 보겠습니다.

이 또한 4만큼 건너 뛴 애들끼리 정렬을 해줍니다. 같은 색끼리 정렬된다고 보시면 됩니다.

마지막으로 gap=1 까지 수행하면..

gap=1은 사실상 그냥 삽입 정렬을 하는 것과 다름 없습니다.

그렇다면 굳이 왜 이렇게 하는 걸까요? 아까 gap=13 단계에서 보겠습니다.

gap=13 정렬에서 상대적으로 작은 값이 앞에, 큰 값이 뒤에 정렬됩니다.

gap을 줄여 나가면서 진행하면 일반적으로 뒤쪽에 상대적으로 큰 값이 모이게 됩니다.

그러고선 제일 마지막 gap=1의 삽입 정렬에서 더 빠르게 정렬하기 위해서 Shell sort를 개발한 겁니다.

---

Shell sort의 알고리즘을 확인하겠습니다.

ShellSort(S[], n) 
	for (gap ← 1; gap < n; gap ← 3*gap+1) do { }; // 첫 번째 gap 값 계산
	for ( ; gap > 0; gap ← gap/3) do { // gap을 감소시키며 진행
		for (i ← gap + 1; i ≤ n; i ← i+1) do { 
			x ← S[i]; 
			j ← i; 
			while (j > gap and S[j-gap] > x) do { 
				S[j] ← S[j-gap]; 
				j ← j-gap; 
			} // while 
			S[j] ← x;
		} // for 
	} // for 
end ShellSort()

언뜻 보면 복잡해 보이지만, Insertion sort와 비교하면 똑같은 구조입니다.

먼저 Insertion sort에 없는 부분이 하나 있습니다. 바로 gap을 정하는 부분인데요,

for (gap ← 1; gap < n; gap ← 3*gap+1) do { }; 는 첫번째 gap, 즉 위에서 본 배열로 치면 "13"을 도출합니다.

이 루프를 보면 gap=1부터 시작해서 n이 되기 전까지 3*gap+1을 해 주는데요,

이는 Knuth가 1973년 개발한 gap 연산법으로 worst case가 O(n^1.5)일 정도로 성능이 좋고 쓰기도 쉽습니다.

for ( ; gap > 0; gap ← gap/3) do { ... } 는 gap을 줄여가면서 Shellsort를 수행하는 for 문입니다.

위에서 본 배열에선 13 → 4 → 1 로 gap을 줄여가면서 정렬을 했죠.

이 for문을 살펴보면 아까 도출한 gap=13 에서 시작해서 gap=0이 될 때까지 gap을 3으로 나눠줍니다.

gap은 int 값이니 3으로 나눠도 소수점이나 나머지 없이 몫만 저장되므로, gap=4, gap=1 의 값이 나오고,

gap=1일 때는 3으로 나누면 몫이 0이 되므로 for 루프를 끝냅니다.

 

이제 Insertion sort와 비교하면서 확인해 보겠습니다.

void insertsort(int n, int S[]) {
	int i, j, x;
	for (i = 2; i < n; i++) {
		x = S[i];
		j = i - 1;
		while (j > 0 && S[j] > x) {
			S[j + 1] = S[j];
			j--;
		}
		S[j + 1] = x;
	}
}

먼저 왼쪽은 Shell sort, 오른쪽은 Insertion sort 입니다.

두 정렬 다 while문에 들어가기 직전 상태입니다. Shell sort는 i=gap+1=13, x=S[i]=11, j=14가 저장됩니다.

일단 두 정렬 모두 x에 값을 저장해 두네요.

j가 가리키는 게 다르지만.. 이건 단순 첨자 구성의 차이이므로 구조 자체는 동일합니다. 계속 보도록 하겠습니다.

그런데 이번엔 while 조건에 맞지 않아서 while문을 수행하지 않습니다.

Shell sort는 S[j]에, Insertion sort는 S[j+1]에 x값을 저장하는데, 둘 다 뒷 원소에 x 값을 저장하라는 뜻입니다.

하지만 값이 swap된 부분이 없으므로 그대로 유지됩니다.

이렇게 되면 전자는 3과 11, 후자는 3과 14가 정렬 완료되었습니다. 다음 루프로 진행하겠습니다.

i가 1씩 증가하였고, x와 j 값을 도출하였습니다. 이 상태로 while문에 진입하면..

내부 while 문을 수행한 상태입니다.

Shell sort는 2와 15번째 원소, Insertion sort는 2와 3번째 원소를 갖고 정렬한다는 차이를 제외하면 동일합니다.

전자는 S[j]에 S[j-gap] 값인 14를 저장한 뒤 j를 j-gap으로 옮겨버리고,

후자는 S[j+1]에 S[j]의 값인 14를 저장한 뒤 j를 j--로 옮겨버립니다.

둘 다 뒷 원소에 앞 원소의 값을 저장한다는 것이 동일하죠.

그러고서는 둘 다 (Shell sort는 j>gap, Insertion sort는 S[j]>x 조건에 어긋남) while 문을 탈출합니다.

while 문을 탈출하면 Shell sort는 S[j]에, Insertion sort는 S[j+1]에 x의 값을 저장합니다.

둘 다 첨자만 다르지, 앞 원소에 x의 값을 저장해서 최종적으로 swap한다는 것은 동일합니다.

 

이렇게 수행한 Shell sort는 최대 O(n^1.5)의 시간 복잡도를 갖습니다.

---

Heap Sort (힙 정렬)

---

이번엔 Heap sort(힙 정렬)에 대해 소개하겠습니다.

그 전에, Heap이 뭔지 짚고 넘어가야 합니다. 힙은 우선순위 큐(Priority queue)의 일종으로, 보통 Binary search tree와 비교됩니다. heap은 tree에 대해 알고 있어야 이해할 수 있기에 tree에 대해 먼저 보고 오심을 추천드립니다.

먼저 Binary search tree 즉 BST는 L≤P≤R을 만족합니다.

L에 있는 값이 가장 작고, P에 중간값, R에 제일 큰 값이 와야합니다.

 

반면 heap은 부모 노드와 자식 노드의 상관관계에 따라 Maxheap, Minheap으로 나뉩니다.

Maxheap은 부모가 자식 노드보다 큰 값, Minheap은 부모가 자식보다 작은 값을 가지게 됩니다.

또한 heap은 Complete Binary Tree(완전이진트리) 를 만족해야 합니다.

Complete BT란, 값이 들어오면 왼쪽부터 채우고, 값이 빠질 땐 오른쪽 끝부터 빠지는 트리입니다.

---

이제 본격적으로 Heap sort로 들어가보겠습니다.

다음 배열 a를 정렬하려고 합니다.

일단 처음 해야 할 것은 이 배열로 heap을 만듭니다. Maxheap을 만들어보도록 하겠습니다.

먼저 5, 1, 3을 넣는 건 그렇게 어렵지 않습니다.

heap의 조건인 Complete BT를 만족해야 하므로, 5로 시작하여 1, 3을 왼쪽부터 차곡차곡 넣어주면 됩니다.

그럼 7은 그 다음 자리인 1의 왼쪽 자식에 들어가야겠죠?

그런데 7이 1의 자식으로 들어가면 부모가 자식보다 큰 값을 가져야 하는 Maxheap 조건에 어긋납니다.

그래서 자리를 바꿔주는데, 5도 7보다 작으므로 또 다시 swap 해줍니다.

11 또한 1의 다음 자리에 넣고 조건에 맞게 swap 해 주겠습니다.

이런 식으로 8개의 값을 모두 넣어 Maxheap을 완성하면 다음과 같습니다.

Maxheap을 완성한 후엔 root 노드에 있는 값을 heap에서 빼서 출력합니다.

먼저 11을 빼주는데, 그러면 root 노드가 비어버리겠죠? 제일 마지막에 있는 값인 1을 그 자리에 넣어줍니다.

그런데 11을 뺀 root 자리에 1을 넣어버리면 또 다시 Maxheap 조건에 맞지 않습니다.

Maxheap 조건에 맞도록 1을 아래로 swap하여 보내줍니다.

그러면 root에 7이 오므로, 7도 빼주고 이번에는 제일 마지막의 3을 그 자리에 넣어줍니다.

이렇게 Maxheap 조건을 만족시키며 heap에 있는 값을 모두 빼내면

정렬이 완료되는데, 이를 Heap sort라고 합니다.

 

반대로 Minheap을 만든 다음 root에 있는 값을 빼내면 어떻게 될까요?

일단 Minheap을 만들면 다음 모양으로 만들어 질 것이고,

이를 방금처럼 root의 값을 빼면서 출력하되, Minheap 조건을 만족하면서 빼면 다음과 같이 정렬됩니다.

정렬된 결과는 오름차순이든 내림차순이든 상관 없습니다.

다만 Maxheap과 Minheap은 그 정렬 결과가 반대로 나온다는 점만 알아두시면 됩니다.

---

그렇다면 이제 Heap sort의 알고리즘을 알아보겠습니다.

주어진 배열을 Maxheap sort하는 모든 과정을 따라가볼 것이라서 내용이 많이 길어질 것 같습니다..

void maxHeapSort(int a[], int n) {
    for (int i = n / 2; i >= 1; i--) {
        maxHeapify(a, i, n);
    }
    for (int i = n - 1; i >= 1; i--) {
        swap(a, 1, i + 1);
        maxHeapify(a, 1, i);
    }
}

다음 배열 a를 heap sort 하려고 합니다.

저번 배열들과 똑같이 인덱스 0에는 NULL값을 넣고 인덱스 1부터 10까지 정렬하는 알고리즘을 시작하겠습니다.

먼저 maxHeapSort 함수를 보면, 배열 a[]와 배열의 크기 n을 인자로 받습니다.

실제로 배열의 크기는 11이지만, 0 인덱스를 제외하고 정렬할 것이므로 n = 11-1 = 10 을 넣어주겠습니다.

 

for 문으로 진입하면, i는 n/2 즉 배열 크기의 절반인 i=5부터 시작해서 1까지 루프를 돕니다.

루프 안에는 maxHeapify 함수를 호출하므로 maxHeapify 함수로 이동하겠습니다.

void maxHeapify(int a[], int h, int m) {
    int v = a[h];
    int i;

    for (i = 2 * h; i <= m; i = i * 2) {
        if (i < m && a[i] < a[i + 1])
            i = i + 1;
            
        if (v >= a[i])
            break;
        else
            a[i / 2] = a[i];
    }
    a[i / 2] = v;
}

배열 a, i=5, n=10을 인자로 받은 maxHeapify(int a[], int h, int m) 함수입니다.

먼저 a[h] 즉 a[5]의 값을 v에 저장합니다. v=a[5]=3이 됩니다.

 

그 다음 for 루프는 i가 2*h 에서 m이 될 때까지 2배를 해주며 루프를 돕니다.

i=2h=10, m=10인 상태에서 if 절을 보겠습니다.

일단 if (i<m && a[i]<a[i+1]) 이면 i++,

if (v>=a[i]) 이면 for 루프를 탈출,

else문에선 a[i/2]에 a[i]의 값을 집어 넣는다고 하네요.

지금은 앞선 두 조건 모두 맞지 않으니 건너뛰고 else문에서 a[i/2] = a[i] = 7을 넣습니다.

한 바퀴를 돌았으니 i를 2배 해주어 i=20 이 되는데, i>m이 되므로 for 루프를 벗어납니다. 

a[i/2] = a[10] = v = 3을 넣어주면 결국 i[5]=7, i[10]=3이 되어 두 값이 swap 됨이 확인됩니다.

 

어... 글로는 알았는데 무슨 말인지 직관적으로 이해가 가질 않습니다. 따라서 그림을 그려보죠.

주어진 배열을 maxheap, minheap 생각하지 않고 그냥 index값에 맞게 heap에 넣어본 상태입니다.

위에서 for문, 그 안의 if 조건문 등... 이 모든 과정이 바로 Maxheap 조건에 맞게 이 숫자들의 위치를 바꾸는 과정입니다.

a[5]와 a[10]의 값을 Maxheap 조건에 맞도록 바꿔준 것이죠.

따라서 지금의 상태는 이렇습니다.

maxHeapify를 마치고 다시 maxHeapSort로 돌아와 for 루프를 하나 더 돌려봅시다.

i=4 이므로 maxHeapify(a, 4, 10)을 진행합니다.

v에 a[4]=1이 저장되고, for 루프는 i=8에서 시작합니다.

이번엔 i=8, m=10, a[i]=5, a[i+1]=10 이므로, 첫번째 조건문부터 만족합니다. i를 ++하면 i=9가 됩니다.

두번째 조건문은 v>=a[i]인데, 맞지 않으므로 else 문을 진행합니다. a[i/2] = a[4]에 a[i] = 10을 저장합니다.

다음 루프를 돌리려 했더니, i = i*2 = 18 > m이 되므로 for 문을 마칩니다.

그 후 for문 바깥에 있는 a[i/2] = a[9] 에 v=1 을 저장하고 함수를 마칩니다. 지금의 상태는 이렇습니다.

계속해서 Maxheap의 조건에 맞게 값을 바꿔주고 있는 것이 보이시나요?

한번 더 해보겠습니다. maxHeapSort의 for 루프에서 이제 i=3 이므로 maxHeapify(a, 3, 10)을 진행합니다.

v=a[3]=8, for 루프는 i=6에서 시작됩니다.

i=6, m=10, a[i]=9, a[i+1]=4 이므로 첫 조건문엔 맞지 않습니다.

v>=a[i] 조건에도 맞지 않으므로 else 문을 진행합니다. a[i/2] = a[3]에 a[i] = 9를 저장합니다.

i = i*2 = 12 이므로 for 루프를 벗어나고, a[i/2] = a[6]에 v=8을 저장하고 마칩니다. 지금의 상태입니다.

한번 더 진행해 보겠습니다. i=2이므로 maxHeapify(a, 2, 10)을 진행하고..

v=a[2]=2, i=4, m=10, a[i]=10, a[i+1]=7 이므로 두 조건문에 부합하지 않아 else를 진행합니다.

a[i/2] = a[2]에 a[i] = 10을 저장하고, 다음 루프를 위해 i를 두배 해줬더니

i = i*2 = 8 <= m으로 두번째 루프를 진행할 수 있게 됩니다.

이 상태에서 v=2, i=8, m=10, a[i]=5, a[i+1]=1 이므로 두 조건에 부합하지 않아 else를 진행합니다.

a[i/2] = a[4]에 a[i] = 5를 저장하고, i = i*2 = 16 > m 이므로 for 루프를 탈출합니다.

a[i/2] = a[8]에 v=2를 저장합니다. 현재 상태입니다.

이번엔 for 루프를 두 번 돌게 되면서 값도 두 번 바뀌었습니다.

마지막으로 한번 더 진행하겠습니다. i=1이므로 maxHeapify(a, 1, 10)을 진행합니다.

v=a[1]=6, i=2, m=10, a[i]=10, a[i+1]=9 이므로 if절을 진행하지 않고 else를 진행합니다.

a[i/2] = a[1]에 a[i] = 10을 저장하고 i = i*2 = 4를 만들어 두번째 루프로 갑니다.

v=6, i=4, m=10, a[i]=5, a[i+1]=7 이므로 첫 if절의 i++를 해줍니다. i=5 가 됩니다.

a[i]=7은 v보다 크므로 두번째 if절을 건너뛰고 else절에서 a[i/2] = a[2]에 a[i] = 7을 저장하고 세번째 루프로 갑니다.

v=6, i=10, m=10, a[i]=3 이므로 첫 if를 건너뛰고, 두번째 조건문인 v >= a[i]에 부합하므로 for문을 탈출합니다.

그리고 a[i/2] = a[5]에 v=6을 저장합니다.

이렇게 Maxheap 형태가 완성이 되었습니다.

maxHeapSort의 두 번째 for 문을 돌릴 때입니다.

for (int i = n - 1; i >= 1; i--) {
        swap(a, 1, i + 1);
        maxHeapify(a, 1, i);
    }

n=10 이므로 i=9에서 시작해서 1이 될 때까지 i--를 하는 루프입니다.

먼저 swap(a, 1, i+1)로 a[1]과 a[10]을 바꿔줍니다.

이는 아까 Heap sort의 개념에 대해 설명할 때, root를 빼고 마지막에 있는 원소를 root 자리로 올려준다는 것과 같습니다.

이제 maxHeapify(a, 1, 9)를 진행합니다.

10은 저기 10번 자리에 보내버렸으니 빼놓고 생각하고, 1번부터 9번 인덱스까지만 maxHeapify를 진행한다는 겁니다. 

maxHeapify를 다시 들고 오겠습니다.

void maxHeapify(int a[], int h, int m) {
    int v = a[h];
    int i;

    for (i = 2 * h; i <= m; i = i * 2) {
        if (i < m && a[i] < a[i + 1])
            i = i + 1;
        if (v >= a[i])
            break;
        else
            a[i / 2] = a[i];
    }
    a[i / 2] = v;
}

maxHeapify(a, 1, 9)를 시작하면 v=a[1]=3, i=2, m=9, a[i]=7, a[i+1]=9 가 됩니다.

첫번째 if 조건문을 만족하므로 i++ 해줍니다. i=3, a[i]=9가 되죠.

두번째 조건문은 만족하지 못하므로 건너뛰고, else절에서 a[i/2] = a[1]에 a[i] = 9를 넣어줍니다.

i를 두 배 하여 두번째 루프를 돌아줍니다. 이제 v=3, i=6, m=9, a[i]=8, a[i+1]=4가 되네요.

두 조건문 모두 만족하지 않으므로 else절에서 a[i/2] = a[3]에 a[i] = 8을 넣습니다.

i를 두 배 하면 i=12는 9보다 크므로 for 루프를 종료하고 a[i/2] = a[6]에 v=3을 넣고 종료합니다.

이 상태에서 maxHeapSort로 돌아와 두번째 루프를 돌겠습니다.

i=8 이므로 swap(a, 1, i+1) 로 1번 인덱스와 9번 인덱스를 바꿔줍니다.

그리고 마찬가지로 1~8번 인덱스에 대하여 maxHeapify(a, 1, 8)를 진행합니다.

이렇게 계속 진행하다보면 다음과 같이 정렬됩니다.

Minheap sort는 이 반대로 정렬되겠죠? Minheap sort의 코드도 참고사항으로 올려드리겠습니다.

별다른 건 없고 부등호 방향만 바꾸면 끝납니다.

void minHeapify(int a[], int h, int m) {
    int v = a[h];
    int i;

    for (i = 2 * h; i <= m; i = i * 2) {
        if (i < m && a[i] > a[i + 1]) // a[i] < a[i+1]에서 부등호 변경
            i = i + 1;
            
        if (v <= a[i]) // v >= a[i]에서 부등호 변경
            break;
        else
            a[i / 2] = a[i];
    }
    a[i / 2] = v;
}

void minHeapSort(int a[], int n) {
    for (int i = n / 2; i >= 1; i--) {
        minHeapify(a, i, n);
    }
    for (int i = n - 1; i >= 1; i--) {
        swap(a, 1, i + 1);
        minHeapify(a, 1, i);
    }
}

이렇게 정렬된 배열을 출력하면 다음과 같습니다.

이렇게 정말 길었던 Shell sort, Heap sort를 마치겠습니다.

 

 

<틀린 점이 있다면 지적 부탁드립니다. 감사합니다.>