알고리즘 힙 정렬(Heap Sort)

소개글

알고리즘 힙 정렬(Heap Sort)

목차

1. 힙 정렬의 개요
2. 힙 정렬의 수행과정
3. 힙 정렬 알고리즘

본문내용

1. 힙 정렬의 개요
힙이라고 하는 특별한 자료 구조를 사용하여 정렬을 한다. 그것은 전이진 트리를 이용하게 되는 것인데 이를 이용함으로 임의의 노드는 언제나 자식 노드들보다 큰 값을 가지게 된다. 즉, 트리 전체에서 루트가 언제가 가장 큰 값이 되는 것이다.
힙 정렬은 이러한 힙을 사용하여 정렬을 한다. 가장 큰 값을 갖게 되는 루트 값을 출력(삭제)시킨 후에 다시 나머지 노드들로 힙을 구성하게 되고, 이러한 과정을 계속하여 반복해 나간다면 가장 큰 값으로부터 내림차순으로 정렬이 된다.
다시 말해서 자료를 정렬할 대 모든 자료들을 동시에 처리하지 않고 모든 자료 중에서 가장 큰 자료를 찾아 출력(삭제)시키고, 나머지 자료 중에서 앞의 과정을 반복하여 가장 큰 자료(실제 두 번째 큰 자료)를 찾아 출력시키면서 정렬하는 것을 힙 정렬이라 한다. 여기서 가장 중요한 서브 알고리즘은 모든 자료 중에서 가장 큰 값을 빠르게 찾는 과정이다.

2.힙 정렬의 수행과정
0단계 : 다음과 같은 데이터가 입력되는 순서대로 들어와서 루트에서부터 레벨순서에 따라 이진트리를 만들었다. 그리고 이 이진트리를 힙으로 재구성해보도록 하자.

3. 힙 정렬 알고리즘
앞 절에서는 루트에 있는 값을 출력(삭제)하고 트리를 힙으로 재구성하는 것을 반복함으로 결과적으로 내림차순으로 정렬된 출력 값을 얻었다. 이번에는 루트를 삭제하지 않고 트리의 맨 마지막 값과 교환하고 맨 마지막 노드를 제외한 노드들에 대하여 트리를 재구성하는 것을 반복하여 배열의 값을 오름차순으로 정렬해 보자.

참고 자료

없음