[Algorithm] Heap Sort(힙 정렬)
[무료] 알고리즘의 개요와 실습 환경 구축 - 인프런 | 강의
알고리즘을 배우며, 실무에서는 알고리즘이 어떻게 활용되는지 알아봅니다., [임베딩 영상] 알고리즘의 개요와 실습 환경 구축 알고리즘은 문제를 해결하는 절차입니다.입력, 출력, 유한성, 명
www.inflearn.com
11강 힙 정렬에 대한 리뷰이다. 9, 10강은 C++ 라이브러리에 관한 내용이라 리뷰를 따로 다루지 않겠다.
1. 소스코드
** C++
아래는 강의에서 작성해본 C++ 소스이다.
#include <stdio.h>
int number = 9;
int heap[9] = {7, 6, 5, 8, 3, 5, 9, 1, 6};
int main(void) {
// 전체 트리 구조를 최대 힙 구조로 바꿈
for (int i = 1; i < number; i++) {
int child = i;
do {
int parent = (child - 1) / 2;
if (heap[parent] < heap[child]) {
int temp = heap[parent];
heap[parent] = heap[child];
heap[child] = temp;
}
child = parent;
} while (child != 0);
}
// 크기를 줄이며 반복적으로 힙 구성
for (int i = number - 1; i >= 0; i--) {
// 가장 큰 값을 오른쪽으로 보냄
int temp = heap[0];
heap[0] = heap[i];
heap[i] = temp;
int parent = 0;
int child = 1;
do {
child = 2 * parent + 1;
// 자식 중 더 큰 값 찾기
if (heap[child] < heap[child + 1] && child < i - 1) {
child++;
}
// 부모보다 자식이 더 크다면 swap
if (heap[parent] < heap[child] && child < i) {
int temp = heap[parent];
heap[parent] = heap[child];
heap[child] = temp;
}
parent = child;
} while (child < i);
}
for (int i = 0; i < number; i++) {
printf("%d ", heap[i]);
}
}
** Javascript
javascript 로 변환하는 것은 어렵지 않았다.
가장 어려운 것은 이진 트리, 힙, 힙 정렬에 대한 이해일 듯하다.
let number = 9;
let heap = [7, 6, 5, 8, 3, 5, 9, 1, 6];
function main() {
for (let i = 1; i < number; i++) {
let child = i;
do {
let parent = Math.floor((child - 1) / 2);
if (heap[parent] < heap[child]) {
let temp = heap[parent];
heap[parent] = heap[child];
heap[child] = temp;
}
child = parent;
} while (child != 0);
}
// 크기를 줄여가며 반복적으로 힙을 구성
for (let i = number - 1; i >= 0; i--) {
// 최대 힙 제거 - 가장 큰 값을 오른쪽으로 보냄
let temp = heap[0];
heap[0] = heap[i];
heap[i] = temp;
let parent = 0;
let child = 1;
do {
child = 2 * parent + 1;
if (child < i - 1 && heap[child] < heap[child + 1]) { // index 오류나서 순서 바꿈
child++;
}
if (child < i && heap[parent] < heap[child]) { // index 오류나서 순서 바꿈
let temp = heap[parent];
heap[parent] = heap[child];
heap[child] = temp;
}
parent = child;
} while (child < i);
}
console.log(heap.join(", "));
}
** Java
public class Main
{
private static int temp; // 재선언 오류 나서 아예 바깥에 선언하여 재사용함
private static int number = 9;
private static int heap[] = {7, 6, 5, 8, 3, 5, 9, 1, 6};
private static void heapSort() {
// 전체 트리 구조를 최대 힙 구조로 바꿈
for (int i = 1; i < number; i++) {
int child = i;
do {
int parent = (child - 1) / 2;
if (heap[parent] < heap[child]) {
temp = heap[parent];
heap[parent] = heap[child];
heap[child] = temp;
}
child = parent;
} while (child != 0);
}
// 크기를 줄이며 반복적으로 힙 구성
for (int i = number - 1; i >= 0; i--) {
// 최대 힙 제거 - 가장 큰 값을 오른쪽으로 보냄
temp = heap[0];
heap[0] = heap[i];
heap[i] = temp;
int parent = 0;
int child = 1;
do {
child = 2 * parent + 1;
// 자식 중 더 큰 값 찾기
if (child < i - 1 && heap[child] < heap[child + 1]) { // index 오류나서 순서 바꿈
child++;
}
// 부모보다 자식이 더 크다면 swap
if (child < i && heap[parent] < heap[child]) { // index 오류나서 순서 바꿈
temp = heap[parent];
heap[parent] = heap[child];
heap[child] = temp;
}
parent = child;
} while (child < i);
}
}
public static void main(String[] args) {
heapSort();
for (int i = 0; i < number; i++) {
System.out.printf("%d ", heap[i]);
}
}
}
위 java 코드는 C++ 을 변환한 것이다. 변환한 소스코드보다 아래 코드가 힙정렬을 파악하기가 더 쉬울 것 같아서 가져왔다.
static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n/2-1; i >= 0; i--) {
// 최초 heap 구성
heapify(arr, n, i);
}
for (int i = n-1; i > 0; i--) {
// 최대 원소를 맨 끝에 정렬하고 다시 heap구성하는 과정
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
static void heapify(int[] arr, int n, int i) {
int p = i;
int l = i * 2 + 1; // 왼쪽 자식노드
int r = i * 2 + 2; // 오른쪽 자식노드
if(l < n && arr[p] < arr[l]) {
p = l;
}
if(r < n && arr[p] < arr[r]) {
p = r;
}
// 부모노드보다 자식노드가 더 클 경우 swap
if(i != p) {
int temp = arr[p];
arr[p] = arr[i];
arr[i] = temp;
heapify(arr, n, p);
}
}출처 : https://gaemi606.tistory.com/entry/%ED%9E%99-%EC%A0%95%EB%A0%ACHeap-sort
힙 정렬(Heap sort)
1. 힙 정렬(Heap sort) 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기본으로하는 정렬. 불안정 정렬(unstable sort)에 속하며 평균, 최선, 최악 시간 복잡도 모두 O(n log n)임. 가장 크거나 작은 값
gaemi606.tistory.com
2. 정리
힙 정렬은 이진 트리 구조를 이용한다.
이진 트리는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조이다.
(이미지 출처: https://velog.io/@junhok82/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%9E%99heap)
동빈 나님의 블로그에 따르면
https://m.blog.naver.com/ndb796/221228342808
10. 힙 정렬(Heap Sort)
힙 정렬(Heap Sort)은 병합 정렬(Merge Sort)와 퀵 정렬(Quick Sort)만큼 빠른 정렬 알고리즘입니다....
blog.naver.com
다음 데이터를 오름차순 정렬하세요.
7 6 5 8 3 5 9 1 6
기본적으로 완전 이진 트리를 표현하는 가장 쉬운 방법은 배열에 그대로 삽입하는 겁니다, 현재 정렬할 데이터의 개수가 8개이기 때문에 인덱스 0부터 8까지 차례대로 담아주는 것입니다.
완전 이진 트리에 삽입이 되는 순서대로 인덱스를 붙여줍니다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 숫자 | 7 | 6 | 5 | 8 | 3 | 5 | 9 | 1 | 6 |
1. 한 노드의 두 자식 노드 중 큰 값이 있다면 위치를 바꾸는 heapify algorithm를 수행하는데 이 과정에서 가장 큰 값이 root 가 되고 뒤이어 큰 숫자들이 부모노드가 된다.
2. 이 때 가장 큰 값이 인덱스 0에 오게 된다.
* 데이터의 개수가 n개이므로 전체 트리를 힙 구조로 만드는 시간 복잡도는 O(N * logN)이지만 모든 데이터에 적용하지 않아도 되기 때문에 O(N/2 * logN) => O(N) 에 가까운 속도를 낸다.
3. 최대 힙을 제거(마지막 인덱스와 교체)하고 나머지 숫자로 힙을 구성하여 다시 heapify algorithm 을 수행한다.
4. 루트의 인덱스와 마지막 인덱스가 같아질 때 까지 반복한다.
아래 블로그는 참고용으로 달아두었다.
javascript 의 sort() 메소드가 힙 정렬을 이용하다가 퀵 정렬로 바뀐 이유를 설명해준다.
https://brunch.co.kr/@k2u4yt/3#comment
퀵 정렬 vs 힙 정렬
자바스크립트의 sort 함수는 배열 오브젝트의 내장 함수이다. 이 sort 함수의 내부 구조는 우리가 흔히 알고 있는 정렬 알고리즘이 구현되어 있다. 크롬의 v8엔진 코드를 보면 그 내부 구현부를
brunch.co.kr
퀵 정렬의 경우 worst case로는 시간복잡도가 O(N^2) 도 나올 수 있는데도 바꾼 것은 힙 정렬에서 swap 연산횟수 때문이라고 위 블로그에서 추측하고 있다.
