일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
- 알고리즘
- redux
- 항해플러스
- axios
- 프로그래머스
- programmers
- react-router
- sw expert academy
- maeil-mail
- 테코테코
- 항해99
- C++
- redux-saga
- Algorithm
- java
- SW
- react
- createSlice
- JavaScript
- Get
- 리액트
- 매일메일
- useDispatch
- 이코테
- json-server
- 자바
- 코딩테스트합격자되기
- Python
- react-redux
- redux-toolkit
- Today
- Total
Binary Journey
[Algorithm] Heap Sort(힙 정렬) 본문
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
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
다음 데이터를 오름차순 정렬하세요.
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
퀵 정렬의 경우 worst case로는 시간복잡도가 O(N^2) 도 나올 수 있는데도 바꾼 것은 힙 정렬에서 swap 연산횟수 때문이라고 위 블로그에서 추측하고 있다.
'Algorithm > 알고리즘 스터디(2021.07)' 카테고리의 다른 글
[Algorithm] 심화 정렬 알고리즘 문제 풀이 (백준 1181, 1431, 10989) (0) | 2021.08.10 |
---|---|
[Algorithm] Counting Sort(계수 정렬) (0) | 2021.08.10 |
[Algorithm] Merge Sort(병합 정렬) (0) | 2021.08.04 |
[Algorithm] 백준 sort 문제풀이 (0) | 2021.07.29 |
[Algorithm] Quick Sort(퀵 정렬) (0) | 2021.07.29 |