주변인의 주저리 주저리 Tstory점

1. 힙 정렬(Heap Sort)?

힙 정렬은 우선 순위 큐인 힙을 이용하여, 모든 원소를 힙에 집어넣었다가 빼는 방식으로 정렬을 하는 알고리즘 입니다.

1.1 힙이란?

이진 트리 형태로 윗쪽의 원소들이 아래쪽의 원소보다 작은 형태(Min Heap의 경우)로 저장하는 자료구조이다.

(Min Heap의 예 : 뿌리 1을 중심으로 아래쪽의 원소들은 위쪽의 원소보다 작다)

※ 이 포스트에서는 Min Heap을 기준으로 설명합니다.

1.2 힙에 원소를 추가하기

힙에 원소를 추가할 때는 가장 말단에 원소를 추가한 뒤 위쪽의 원소와 비교하면서 그보다 작을 경우 교환을 위쪽의 원소가 작은 경우나 뿌리에 도달할 때까지 반복하는 과정을 통해 원소를 추가하게 된다.

1.3 힙에서 원소를 꺼내기

힙에 원소를 꺼낼 때에는 뿌리의 원소를 꺼낸 후 힙의 구조를 유지하기 위해 가장 말단의 원소를 뿌리로 옮긴 후 아래노드와 비교하여 자신이 작을 경우 교환하게 됩니다.

2. C를 이용한 구현

1. 기수 정렬(Radix Sort)?

기수 정렬은 정수의 자리수의 숫자를 기준으로 큐에 넣어서 순서대로 꺼내는 방식으로 정렬을 기준이 되는 자리수를 바꿔가면서 정렬을 하는 알고리즘입니다.

2. 기수 정렬의 실제

데이터를 가지고 직접 기수 정렬을 해봅시다.

1. 일의 자리수를 기준으로 각 자리수 큐에 넣는다.

큐

큐

큐

큐

큐

큐

2. 각 큐에 들어간 원소들을 순서대로 꺼낸다.

큐

큐

큐

큐

큐

큐

3. 기준이 되는 자리수를 바꿔서 반복한다.

큐

큐

큐

큐

큐

큐

큐

큐

큐

큐

큐

큐

3. C를 이용한 구현

 다음은 큐를 사용하지 않고, 자릿수 숫자를 세는 방식으로 기수 정렬을 행하는 방식이다.

4. 비트를 이용한 기수 정렬

정수의 자릿수가 아닌 비트 몇개를 단위로 하여 기수 정렬을 행하는 방식으로 정수이외의 경우에도 정렬을 행할 수 있다. 단, 이 경우 HEX코드값에 따라 대소가 구분이 가능한 경우만 가능하다.

1. 셸 정렬(Shell Sort)?

셸 정렬은 삽입 정렬의 단점인 원소를 적합한 위치에 삽입하기 위해 원소들을 뒤로 옮기는 과정을 줄이기 위해, 특정한 거리씩 떨어진 원소들끼리 삽입정렬을 하고, 그 거리을 차츰 줄여나가면서, 최종적으로는 전체 원소들에 대해 삽입정렬을 하는 알고리즘입니다.

※ 삽입 정렬에 대한 내용은 정렬 알고리즘 - 5. 삽입 정렬(Insertion Sort)(http://juff.tistory.com/11)를 참조해주세요.

2. 셸 정렬의 실제

데이터를 가지고 직접 셸 정렬을 해봅시다. (여기서는 원소간 거리가 3, 1로 줄어드는 경우로 합니다.)

1. 거리가 3만큼 떨어진 원소끼리 삽입 정렬을 한다.

삽입할 원소 : 3

삽입할 원소 : 3

삽입할 원소 :

삽입할 원소 : 7

삽입할 원소 :

삽입할 원소 : 8

삽입할 원소 : 8

삽입할 원소 :

2. 거리가 1만큼 떨어진 원소끼리 삽입 정렬을 한다.

삽입할 원소 : 1

삽입할 원소 : 1

삽입할 원소 :

삽입할 원소 : 8

삽입할 원소 : 

삽입할 원소 : 5

삽입할 원소 : 5

삽입할 원소 : 

삽입할 원소 : 7

삽입할 원소 : 7

삽입할 원소 : 

삽입할 원소 : 9

삽입할 원소 : 

3. C를 이용한 구현

다음 코드는 원소간 거리를 데이터의 절반에서 부터 시작하여, 정렬이 완료될 때까지 반으로 나눠가는 방법을 사용하였다.

4. 원소간 거리를 어떻게 정해야 하는가?

셸 정렬의 기본전략은 삽입정렬 과정에서 원소를 뒤로 옮기는 횟수를 줄이는 것으로 속도를 향상시키는데 있다. 하지만, 삽입정렬 횟수가 너무 많거나, 적게 된다면, 이러한 효과가 떨어진다. 때문에 원소간 거리에 대한 최적화된 수열을 사용한다면 속도를 더욱 향상시킬 수 있게된다.