`정렬`이란 레코드들을 키 값의 순서로 재배열하는 것입니다. 지금까지 정렬 알고리즘이 개발되었지만 모든 경우에 최상의 성능을 보여주는 알고리즘은 존재하지 않습니다. 따라서 프로그램에 가장 효율적인 알고리즘을 선택해야 합니다. - 단순하지만 비효율적인 방법엔 `삽입 정렬, 선택 정렬, 버블 정렬` 등이 있고 - 복잡하지만 효율적인 방법엔 `퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬` 등이 있습니다. 정렬 알고리즘에서 **`안정성`** 이란 동일한 키 값을 갖는 레코드가 여러 개 존재할 경우 이들의 `상대적 위치가 정렬 후에도 바뀌지 않는 것`을 의미합니다. `안정성이 요구되는 경우`에는 `삽입 정렬, 버블 정렬, 합병 정렬` 등을 사용해야 합니다. --- ## 1. 버블 정렬 Bubble Sort는 Selection Sort와 유사한 알고리즘으로 **`서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘`** 입니다. 이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 합니다. 모든 싸이클마다 모든 레코드를 교환해야 합니다. 즉 버블 정렬의 시간 복잡도는 $O(N^2)$이고 `순서에 맞지 않은 요소를 인접한 요소와 교환한다는 문제점`이 있기에 단순성에 불구하고 거의 쓰이지 않습니다. 1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환합니다. 2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외됩니다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어납니다. ```cpp void bubbleSort(int[] arr) { int temp = 0; for(int i = 0; i < arr.length; i++) { // 1. for(int j= 1 ; j < arr.length-i; j++) { // 2. if(arr[j-1] > arr[j]) { // 3. // swap(arr[j-1], arr[j]) temp = arr[j-1]; arr[j-1] = arr[j]; arr[j] = temp; } } } for(int i : arr){ cout >> i >> " "; } } ``` 시간복잡도를 계산하면, `(n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2`이므로, 최선, 평균, 최악의 경우 모두 시간복잡도가 **$O(n^2)$** 으로 동일 **공간복잡도** 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 **O(n)** 입니다. **장점** - 구현이 매우 간단하고, 소스코드가 직관적입니다. - 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다. => 제자리 정렬(in-place sorting) - 안정 정렬(Stable Sort) 입니다. **단점** - 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적입니다. - 정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 됩니다. --- ## 2. 선택 정렬(Selection Sort) Selection Sort는 Bubble Sort과 유사한 알고리즘으로, **해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘**입니다. Selection Sort와 Insertion Sort를 헷갈려하시는 분들이 종종 있는데, Selection Sort는 배열에서 **`특정자리를 선택하고 그 자리에 오는 값을 찾는 것`**이라고 생각하시면 편합니다. **선택 정렬**은 `입력` 배열에서 `최소값`을 찾은 다음 `배열의 첫 번째 요소와 교환하는 과정을 반복`하는 알고리즘입니다. 이 절차를 `숫자 개수-1` 만큼 되풀이하면 전체 숫자가 정렬됩니다. 즉 $O(N^2)$의 시간 복잡도를 가집니다. 선택 정렬의 장점은 `이동 횟수가 미리 결정`된다는 점입니다. 그러나 안정성을 만족하지 않는다는 단점이 있어 같은 값을 가진 레코드의 상대적 위치가 변경될 수 있습니다. ```cpp void selectionSort(int[] arr) { int indexMin, temp; for (int i = 0; i < arr.length-1; i++) { // 1. indexMin = i; for (int j = i + 1; j < arr.length; j++) { // 2. if (arr[j] < arr[indexMin]) { // 3. indexMin = j; } } // 4. swap(arr[indexMin], arr[i]) temp = arr[indexMin]; arr[indexMin] = arr[i]; arr[i] = temp; } for (int i : arr) { cout << i << " "; } } ``` > 최선, 평균, 최악의 경우 시간복잡도는 **$O(n^2)$** 으로 동일 > > `공간복잡도`는 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 **$O(n)$** 입니다. > **장점** - Bubble sort와 마찬가지로 알고리즘이 단순합니다. - 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적입니다. - Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다. ⇒ 제자리 정렬(in-place sorting) **단점** - 시간복잡도가 $O(n^2)$으로, 비효율적입니다. - **불안정 정렬(Unstable Sort)** 입니다. --- ## 3. 삽입 정렬(Insertion Sort) 손 안의 카드를 정렬하는 방법과 유사합니다. Insertion Sort는 Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘입니다. **삽입 정렬**은 `두 번째 요소`부터 시작하여 `그 앞의 요소들`과 비교하여 삽입할 위치를 지정한 후 `요소들을 뒤로 옮기고` `지정한 자리에 요소를 삽입하여 정렬하는 알고리즘`입니다. 최선의 경우 $O(N)$이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘입니다. 선택 정렬과 유사하게 `배열을 정렬된 부분`과 `정렬되지 않은 부분`으로 나누어서 사용합니다. 삽입정렬의 시간 복잡도는 입력 자료의 구조에 따라 달라집니다. 자료가 `이미 정렬되어 있는 경우`엔 $O(N)$이지만 입력 자료가 역순인 `최악의 경우`엔 $O(N^2)$의 시간 복잡도를 가집니다. 삽입 정렬은 안정적인 방법으로 레코드의 수가 작거나 대부분이 이미 정렬되어 있다면 효율적이라고 할 수 있습니다. **Process (Ascending)** 1. 정렬은 2번째 위치(index)의 값을 temp에 저장합니다. 2. temp와 이전에 있는 원소들과 비교하며 삽입해나갑니다. 3. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복합니다. ```cpp void insertionSort(int[] arr) { for(int index = 1 ; index < arr.length ; index++){ // 1. int temp = arr[index]; int prev = index - 1; while( (prev >= 0) && (arr[prev] > temp) ) { // 2. arr[prev+1] = arr[prev]; prev--; } arr[prev + 1] = temp; // 3. } for(int i : arr){ cout >> i >> " "; } } ``` 1. 첫 번째 원소 앞(왼쪽)에는 어떤 원소도 갖고 있지 않기 때문에, 두 번째 위치(index)부터 탐색을 시작합니다. temp에 임시로 해당 위치(index) 값을 저장하고, prev에는 해당 위치(index)의 이전 위치(index)를 저장합니다. 2. 이전 위치(index)를 가리키는 prev가 음수가 되지 않고, 이전 위치(index)의 값이 '1'번에서 선택한 값보다 크다면, 서로 값을 교환해주고 prev를 더 이전 위치(index)를 가리키도록 합니다. 3. '2'번에서 반복문이 끝나고 난 뒤, prev에는 현재 **temp 값보다 작은 값들 중 제일 큰 값의 위치(index)** 를 가리키게 됩니다. 따라서, (prev+1)에 temp 값을 삽입해줍니다. ![insertion-sort-001.gif](attachment:cf281d17-10b7-4f1b-9da4-35c1b57ca54b:insertion-sort-001.gif) > **시간복잡도** > 최악의 경우(역으로 정렬되어 있을 경우) Selection Sort와 마찬가지로, `(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2` 즉, **$O(n^2)$** 입니다. 하지만, 모두 정렬이 되어있는 경우(Optimal)한 경우, 한번씩 밖에 비교를 안하므로 **O(n)** 의 시간복잡도를 가지게 됩니다. 또한, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는, 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문입니다. 최선의 경우는 **$O(n)$** 의 시간복잡도를 갖고, 평균과 최악의 경우 **$O(n^2)$**의 시간복잡도를 갖게 됩니다. > **공간복잡도** > 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 **O(n)** 입니다. **장점** - 알고리즘이 단순합니다. - 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있습니다. - 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다. => 제자리 정렬(in-place sorting) - **안정 정렬(Stable Sort)** 입니다. - Selection Sort나 Bubble Sort과 같은 $O(n^2)$ 알고리즘에 비교하여 상대적으로 빠릅니다. **단점** - 평균과 최악의 시간복잡도가 $O(n^2)$으로 비효율적입니다. - Bubble Sort와 Selection Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적입니다. ## 4. 퀵 정렬 (Quick Sort) **퀵 정렬**은 `분할 정복 알고리즘`의 하나로 빠른 속도를 자랑합니다. --- ***분할 정복이란?*** 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식 --- 합병 정렬과 달리 `리스트를 비균등하게 분할한다는 특징`이 있습니다. 분할 시 리스트 안의 한 요소를 선택하는데 이를 `피벗`이라고 합니다. 그리고 `피벗`을 중심으로 2개의 리스트로 나누는데 이때 `partition 함수`를 사용합니다. `작은 요소`는 `왼쪽`, `큰 요소`는 `오른쪽` 리스트로 옯겨지게 됩니다. 분할된 부분 리스트에 대해 `순환(재귀)호출`을 이용하여 부분리스트의 크기가 `0`이나 `1`이 될 때까지 정렬을 반복합니다. 속도가 빠르고 추가 메모리 공간을 필요로 하지 않는다는 장점이 있지만 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 시간이 오히려 더 걸린다는 단점이 있습니다. 그래서 피벗 선택 시에 `데이터의 중간값`을 선택하여 리스트를 균등하게 분할 수 있게 하기도 합니다. 최악의 경우 $O(n^2)$, 평균적으로 $O(nlogn)$ ✅ **partition = O(n)** (항상) > T(n) = T(왼쪽) + T(오른쪽) + O(n) 여기서 **왼쪽/오른쪽 크기가 어떻게 나뉘느냐**가 전부야. > ### 최선의 경우 (이상적인 분할) ### 상황 - pivot이 항상 **정확히 가운데** - 배열이 반씩 나뉨 ``` n→ n/2 + n/2 ``` ### 점화식 ``` T(n)=2T(n/2)+ O(n) ``` ### 결과 ``` T(n)= O(nlog n) ``` 📌 이유: - 깊이: log n - 각 레벨에서 partition 비용: n ### 최악의 경우 ### 대표적인 최악 입력 1. 이미 **오름차순 정렬** 2. 이미 **내림차순 정렬** 3. pivot을 항상 **최솟값 또는 최댓값**으로 고르는 경우 ### 예시 ``` n → 0 + (n-1) ``` ### 점화식 ``` T(n)=T(n-1)+ O(n) ``` ### 전개 ``` T(n) = n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²) ``` ```java pivot = array[left]; ``` ➡️ **정렬된 배열에서 최악 케이스 발생** > 피벗 선택 방식 : 첫번째, 중간, 마지막, 랜덤 (선택 방식에 따라 속도가 달라지므로 중요함) > ```cpp public int partition(int[] array, int left, int right) { int pivot = array[left]; // 현재 피봇의 값은 array[left]의 값. int i = left, j = right; //i와 j는 인덱스를 가르킴 while(i < j) { while(pivot < array[j]) { //배열의 오른쪽에서 피벗보다 작은 값을 찾기 위함 j--; } while(i= array[i]){ // 배열의 왼쪽에서 피벗보다 큰 값을 찾기 위함 i++; } swap(array, i, j); // 위 두 조건이 일치하여 넘어가면 i와 j 스왑 } //i와 j의 인덱스가 같은 상황이 발생했을 때. array[left] = array[i]; // 피봇이 있던 array[left]의 값이 중앙 겹친 값이 됨. array[i] = pivot; // 중앙 값은 피봇의 값으로 됨 => 중앙 값과 피봇값을 교환 // 피봇값을 중심으로 왼쪽은 피봇값 보다 작은 값들이 위치, 오른쪽은 피봇값보다 큰 값들이 위치함 // 즉 partition은 정렬이 아니라 "분할" return i; } public void quickSort(int[] array, int left, int right) { if(left >= right) return; int pi = partition(array, left, right); quickSort(array, left, pi-1); quickSort(array, pi+1, right); } ``` 1. 피벗 선택 2. 오른쪽(j)에서 왼쪽으로 가면서 피벗보다 작은 수 찾음 3. 왼쪽(i)에서 오른쪽으로 가면서 피벗보다 큰 수 찾음 4. 각 인덱스 i, j에 대한 요소를 교환 5. 2,3,4번 과정 반복 6. 더이상 2,3번 진행이 불가능하면, 현재 피벗과 교환 7. 이제 교환된 피벗 기준으로 왼쪽엔 피벗보다 작은 값, 오른쪽엔 큰 값들만 존재함 `버블 정렬`은 모든 배열의 요소에 대한 인덱스를 하나하나 증가하며 비교해나가는 $O(n^2)$ `퀵 정렬`의 경우 인접한 것이 아닌 서로 먼 거리에 있는 요소를 교환하면서 속도를 줄일 수 있음 But, **피벗 값이 최소나 최대값으로 지정되어 파티션이 나누어지지 않았을 때** $O(n^2)$에 대한 시간복잡도를 가짐 **퀵소트 O(n^2) 해결 방법** --- 이런 상황에서는 퀵소트 장점이 사라지므로, 피벗을 선택할 때 `중간 요소`로 선택하면 해결이 가능함 → 정렬된 배열에서 최솟값이나 최대값을 선택하는 경우의 수를 없애줌 하지만 이 방법이 무조건 O(n^2)의 시간복잡도를 해결할 수 있는 절대적인 방법이 아님(값들이 중복인 경우, 특정 숫자패턴만 밀집되어있는 특수 배열인경우) ```cpp public int partition(int[] array, int left, int right) { int mid = (left + right) / 2; swap(array, left, mid); ... } ``` 이는 다른 $O(nlogn)$ 시간복잡도를 가진 소트들보다 빠르다고 알려져있음 > 먼거리 교환 처리 + 캐시 효율(한번 선택된 기준은 제외시킴) > ```cpp private void solve() { int[] array = { 80, 70, 60, 50, 40, 30, 20 }; quicksort(array, 0, array.length - 1); for (int v : array) { System.out.println(v); } } public static int partition(int[] array, int left, int right) { int mid = (left + right) / 2; swap(array, left, mid); int pivot = array[left]; int i = left, j = right; while (i < j) { while (pivot < array[j]) j--; while (i < j && pivot >= array[i]) i++; swap(array, i, j); } array[left] = array[i]; array[i] = pivot; return i; } public static void swap(int[] array, int a, int b) { int temp = array[b]; array[b] = array[a]; array[a] = temp; } public static void quicksort(int[] array, int left, int right) { if (left >= right) { return; } int pi = partition(array, left, right); quicksort(array, left, pi - 1); quicksort(array, pi + 1, right); } ``` --- ## 5. 병합 정렬(Merge Sort) **병합 정렬**은 `분할 정복 알고리즘`을 기반으로 합니다. 빠른 정렬로 분류되며, 퀵소트와 함께 많이 언급되는 정렬 방식이다. 퀵소트와는 반대로 `안정 정렬`에 속함 --- ***분할 정복이란?*** 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식 --- 문제를 작은 2개의 문제로 분리 후 각각을 해결하여 모아서 원래의 문제를 해결하는 것인데 분리된 문제가 충분히 작지 않다면 분할 정복 방법을 다시 적용합니다. `안정적인 정렬 방법`이라는 장점이 있고 레코드를 배열로 구성하면 `임시 배열이 필요하다는 단점`이 있습니다. 이 단점은 레코드를 `연결리스트`로 구성하여 `링크 인덱스 값`만 변경하는 방법으로 보완할 수 있습니다. 즉 `연결리스트`를 사용한다면 병합 정렬은 퀵 정렬보다 효율적일 수 있습니다. 최악, 평균, 최선의 경우 모두 $O(nlogn)$의 시간 복잡도를 가집니다. ```cpp static void merge_vec(vector& arr, int left, int mid, int right) { vector L(arr.begin() + left, arr.begin() + mid + 1); vector R(arr.begin() + mid + 1, arr.begin() + right + 1); int i = 0, j = 0, k = left; int ll = (int)L.size(), rl = (int)R.size(); while(i < ll && j < rl) { // 두 배열 중 한 배열이라도 끝나면 종료 // 두 배열의 현재 값 중 더 작은 값을 arr[left]에 해당하는 부분부터 시작하여 저장 if(L[i] <= R[j]) arr[k++] = L[i++]; else arr[k++] = R[j++]; } // 남은 원소 처리 ( 한쪽 배열이 먼저 끝나면 다른 쪽도 이미 정렬된 상태이므로 그대로 복사) while(i < ll) arr[k++] = L[i++]; while(j < rl) arr[k++] = R[j++]; } static void mergeSort(vector& a, int left, int right) { if (left < right) { int mid = left + (right - left) / 2; // overflow 방지 mergeSort(a, left, mid); mergeSort(a, mid + 1, right); merge_vec(a, left, mid, right); } } ``` ### 병합 정렬의 핵심 아이디어 1. **분할(Divide)** : 배열을 절반으로 나눈다 2. **정복(Conquer)** : 각 부분을 재귀적으로 정렬한다 3. **병합(Merge)** : 정렬된 두 배열을 하나로 합친다 📌 이 코드는: - `mergeSort` → **분할 + 재귀** - `merge_vec` → **병합** *퀵소트와의 차이점* > 퀵정렬 : 우선 `피벗`을 통해 정렬(partition) → 영역을 쪼갬(quickSort) > > > 병합정렬 : `영역을 쪼갤 수 있을 만큼 쪼갬`(mergeSort) → 정렬(merge) > 이미 **합병의 대상이 되는 두 영역이 각 영역에 대해서 정렬이 되어있기 때문**에 단순히 두 배열을 **순차적으로 비교하면서 정렬할 수가 있다.** ★★★ 합병정렬은 `순차적인 비교로 정렬을 진행`하므로, **`LinkedList`의 정렬이 필요할 때 사용하면 효율적**이다. ★★★ *LinkedList를 퀵정렬을 사용해 정렬하면?* > 성능이 좋지 않음 > > > 퀵정렬은, 순차 접근이 아닌 **임의 접근(random access)이기 때문** > >

> 👉 > > 배열(Array)은 > > - `A[i]`가 **O(1)** (주소 계산으로 바로 점프) > > 반면 LinkedList는 > > - `node i`에 가려면 **head부터 i번 next를 타야 해서 O(i)** > - 평균적으로도 접근이 **O(n)** > > 즉, “i번째 원소를 가져오는 행위” 자체가 비싸다. > > 퀵정렬의 partition 과정은 보통 이렇게 생겼지: > > - 양끝 포인터 `i`, `j`를 두고 > - `array[i]`, `array[j]`를 계속 비교하면서 > - 조건이 맞으면 **원소를 swap**하고 > - pivot 기준으로 좌우를 쪼갠다 > > 배열에서는 `array[i]`, `array[j]` 접근이 O(1)이니까 partition이 **O(n)**으로 깔끔하게 돌아가. > > 하지만 LinkedList에서 “i번째, j번째 원소”를 찾으려고 하면: > > - 매번 head부터 (또는 tail부터) 타고 가야 함 → 접근이 O(n) > - partition 중 비교/이동이 n번 일어나면 → **O(n²)** 수준으로 비용이 튄다 > > 즉, 퀵정렬 자체의 수학적 평균복잡도 O(n log n)와 별개로, > > **LinkedList에서는 ‘원소 접근’이 비싸서 실제 실행 시간은 훨씬 더 나빠진다**. > > 요약. > > 합병정렬은 병합 과정에서 두 부분 리스트의 현재 노드만 순차적으로 비교하며 한 번씩만 진행하므로, `임의 접근(random access)`이 불가능한 `LinkedList`에서도 `O(n)` 병합이 가능하다. 또한 LinkedList는 `포인터 재연결`만으로 `병합`을 수행할 수 있어 배열처럼 큰 임시 버퍼가 필수적이지 않다. > > 반면 퀵정렬은 파티션 과정에서 양쪽 끝 인덱스를 기반으로 원소에 반복적으로 접근하고 swap을 수행하는데, > `LinkedList`는 특정 위치의 원소에 접근하려면 head부터 `순차 탐색`이 필요해 접근 비용이 $O(n)$이다. 따라서 파티션 과정에서 발생하는 다수의 비교/교환이 노드 탐색 비용과 결합되어 `오버헤드가 크게 증가`하며, 배열에서 기대하는 퀵정렬의 장점($O(n log n)$ 평균)이 실제 성능으로 잘 이어지지 않는다. > >

> **LinkedList는 삽입, 삭제 연산에서 유용**하지만 **접근 연산에서는 비효율적**임 (위 콜아웃) 따라서 임의로 접근하는 `퀵소트`를 활용하면 `오버헤드 발생`이 `증가`하게 됨 > 배열은 인덱스를 이용해서 접근이 가능하지만, LinkedList는 Head부터 탐색해야 함 > > > 배열[O(1)] vs LinkedList[O(n)] > --- ## 6. 힙 정렬(트리 개념 필요) > 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 방식 > 힙 소트는 `불안정 정렬`에 속함 **시간복잡도** | **평균** | **최선** | **최악** | | --- | --- | --- | | Θ(nlogn) | Ω(nlogn) | O(nlogn) | **과정** 1. `최대 힙`을 구성 2. 현재 힙 루트는 가장 큰 값이 존재함. 루트의 값을 `마지막 요소`와 바꾼 후, 힙의 사이즈 하나 줄임 3. 힙의 사이즈가 1보다 크면 위 과정 반복 **힙 정렬**은 최대, 최소 힙 트리를 구성해 정렬하는 방법입니다. 내림차순 정렬을 위해서는 최대 힙, 오름차순 정렬을 위해서는 최소 힙을 구성하면 됩니다. 내림차순을 기준으로 정렬해야 할 요소들로 `완전 이진 트리` 형태의 `최대 힙`을 만듭니다. 그 다음 요소를 힙에서 하나씩 꺼내 배열의 뒤에서부터 저장하는 것입니다. 그러면 배열 요소들은 값이 증가되는 순서로 정렬됩니다. 힙 트리의 높이는 완전 이진 트리이므로 log입니다. 즉 시간 복잡도 또한 $O(logN)$가 됩니다. 힙 정렬은 `가장 큰 값, 작은 값 몇 개만 필요한 경우` 유용한 알고리즘입니다.

[알고리즘] 정렬 알고리즘