이전 글에서 Heap Sort를 위해 필요한 Heap, Heapify 개념을 다루었다. Heap Sort는 배열이 주어졌을 때 다음과 같은 과정을 통해 정렬한다. ① 주어진 배열로 Max Heap을 만든다. ② Max Heapl에서 최대값(루트)를 가장 마지막 값과 바꾼다. (이때 가장 마지막 값은 정렬이 된 것이므로 힙의 일부가 아닌 것으로 간주함) ③ 루트노드에 대해서 Max-Heapify한다 ④ 남은 노드가 1개가 될 때 까지 ②,③을 반복한다 크게 생각한다면 Max Heap을 만들고(초기화), iterative하게 Max-Heapify하는 과정을 통해 배열을 정렬하는 것이다. 1. Heap Sort 과정 (1) Max Heap 만들기 정렬되지 않는 배열을 추상적으로 complete binary t..
1. Heap이란? Heap은 heap property를 만족하는 complete binary tree이다. (1) complete binary tree binary tree는 자식 노드가 2개만 존재하며, 오른쪽 자식과 왼쪽 자식이 구분되는 tree이다. full binary tree: 모든 층(level)의 노드들이 꽉 차있는 형태 complete binary tree: 마지막 층(level)을 제외한 층의 노드들은 꽉 차 있으며, 마지막 층의 오른쪽부터 몇개의 노드가 비어있을 수 있음 (2) heap property 이 글에서는 max-heap property를 기준으로 다루고자 한다. max-heap property: 부모는 자식보다 크거나 같다 min-heap property: 부모는 자식보다 ..
정렬 알고리즘 종류 Bubble Sort, Selection Sort, Insertion Sort(간단하지만 느림) Merge Sort, Quick Sort, Heap Sort(빠름) Radix Sort(매우 빠름) 이 중 Merge Sort, Quick Sort, Heap Sort는 분할정복법을 적용하여 풀 수 있다. 분할: 풀고자 하는 문제를 작은 크기의 동일한 문제들로 분할 정복: 각각의 작은 문제들을 순환적으로 해결 합병: 작은 문제의 해들을 합하여 원래 문제에 대한 답을 구함(merging) 1. Merge Sort(합병정렬) 1) 정렬과정 - ① 분할: 배열의 길이가 1이 될때 까지 배열을 반복적으로 반으로 나눔($n \rightarrow \frac{n}{2} \rightarrow \frac{..
