힙정렬

소개

자료구조 힙정렬
코드, 설명, 캡쳐 포함

목차

Ⅰ. 문 제 분 석
Ⅱ. 입/출력의 예
Ⅲ. 문제 풀이 방법(알고리즘 )
Ⅳ. 소스 프로그램
Ⅴ. 수행 결과
Ⅵ. 결과 분석 및 토의

본문내용

Ⅰ. 문 제 분 석
1. 힙정렬(heap Sort)이란?
힙정렬을 하기 위해서는 먼저 힙을 정의해야 하는데, 힙은 자식노드의 값보다 부모노드의 값이 같거나 큰, 완전 이진트리이다. 어떤 리스트가 힙으로 구성될 수 있다면 배열 상에서 인덱스 1에 해당하는 값인 뿌리노드의 값이 전체 노드의 값들보다 큰 특징을 갖는 것이다.
힙정렬은 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 오름차순 정렬을 위해서는 최대 힙을 구성해야 하고 내림차순 정렬을 위해서는 최소 힙을 구성하면 된다.

2. 중순위(inorder)란?
이진트리의 운행법으로, 특정 노드에서 왼쪽 노드, 뿌리 노드, 오른쪽 노드의 순으로 왼쪽 서브 트리를 모두 방문하고, 자기 노드를 방문한 후에 오른쪽 서브 트리를 방문한다. 이 원리를 모든 노드에 재귀적으로 적용하면 모든 노드들을 한 번씩 방문할 수 있다.

3. 힙 정렬의 정렬 방법
1. n개의 노드에 대한 완전이진 트리를 구성. 이때 루트 노드부터 부노드, 왼쪽 자노드, 오른쪽 자노드 순으로 구성한다.
2. 정렬한 원소들을 입력하여 최대 힙을 구성. 최대 힙이란 부노드가 자노드보다 큰 트리를 말하는데, 단말 노드를 자노드로 가진 부노드부터 구성하며 아래부터 루트까지 순차적으로 만들어 갈 수 있다. 단, 트리의 특성상 인덱스는 1부터 사용한다(0에 2를 곱해도 계속 0이 되는 현상을 방지)
3. 루트에 위치한 가장 큰 수와 가장 작은 수를 교환.
4. 2-3단계를 반복한다.
ex) [1, 9, 2, 4, 3, 7, 5, 6, 8]을 힙정렬 해보자.
원소 9개를 완전 이진트리로 만들고 최대 힙으로 구성한다. 힙의 루트노드의 원소를 9로 하고 배열의 마지막 자리에 저장한다. 나머지 원소들을 최대 힙으로 다시 구성하고 연산을 수행해서 8, 7, 6 ...의 순서로 배열의 오른쪽에서 왼쪽으로 저장한다.

참고자료

· 없음