728x90
Heap Sort
힙 정렬은 힙을 사용해 데이터를 정렬하는 알고리즘이다.
힙의 루트 노드에서 지속적으로 값을 꺼내면 특정한 순서로 정렬할 수 있다.
힙 자료구조를 모른다면 다음 글을 참고하자.
2025.01.13 - [Programming/Data Structure] - [Data Structure] 힙 트리
코드
#include <iostream>
#include "../Chapter5/5.6/MaxHeap.hpp"
void Print(int* arr)
{
for (int i = 0; i < 10; i++)
{
std::cout << arr[i] << " ";
}
std::cout << "\n";
}
int* HeapSort(int* arr)
{
int* result = new int[10];
MaxHeap<int> heap;
for (int i = 0; i < 10; i++)
heap.Push(arr[i]);
for (int i = 9; i >= 0; i--)
{
result[i] = heap.Top();
heap.Pop();
}
return result;
}
int main()
{
std::cin.tie(0);
std::ios::sync_with_stdio(0);
int arr[10] = {8, 31, 48, 73, 3, 65, 20, 29, 11, 15};
Print(arr);
int* result = HeapSort(arr);
Print(result);
}
시간 복잡도
n개의 모든 원소를 뽑을 때마다 힙으로 만드는 Heapify가 O(logn)이 필요하므로 힙 정렬의 시간 복잡도는 O(nlogn)이다.
728x90
'Programming > Algorithm & Data Structure' 카테고리의 다른 글
[Data Structure] 그래프와 기본 연산 (BFS, DFS) (0) | 2025.01.13 |
---|---|
[Data Structure] 이진 탐색 트리 (0) | 2025.01.13 |
[Data Structure] 힙 트리 (0) | 2025.01.13 |
[Data Structure] 이진 트리 순회 (0) | 2025.01.13 |
[Data Structure] 트리, 이진 트리 (0) | 2025.01.12 |
728x90
Heap Sort
힙 정렬은 힙을 사용해 데이터를 정렬하는 알고리즘이다.
힙의 루트 노드에서 지속적으로 값을 꺼내면 특정한 순서로 정렬할 수 있다.
힙 자료구조를 모른다면 다음 글을 참고하자.
2025.01.13 - [Programming/Data Structure] - [Data Structure] 힙 트리
코드
#include <iostream>
#include "../Chapter5/5.6/MaxHeap.hpp"
void Print(int* arr)
{
for (int i = 0; i < 10; i++)
{
std::cout << arr[i] << " ";
}
std::cout << "\n";
}
int* HeapSort(int* arr)
{
int* result = new int[10];
MaxHeap<int> heap;
for (int i = 0; i < 10; i++)
heap.Push(arr[i]);
for (int i = 9; i >= 0; i--)
{
result[i] = heap.Top();
heap.Pop();
}
return result;
}
int main()
{
std::cin.tie(0);
std::ios::sync_with_stdio(0);
int arr[10] = {8, 31, 48, 73, 3, 65, 20, 29, 11, 15};
Print(arr);
int* result = HeapSort(arr);
Print(result);
}
시간 복잡도
n개의 모든 원소를 뽑을 때마다 힙으로 만드는 Heapify가 O(logn)이 필요하므로 힙 정렬의 시간 복잡도는 O(nlogn)이다.
728x90
'Programming > Algorithm & Data Structure' 카테고리의 다른 글
[Data Structure] 그래프와 기본 연산 (BFS, DFS) (0) | 2025.01.13 |
---|---|
[Data Structure] 이진 탐색 트리 (0) | 2025.01.13 |
[Data Structure] 힙 트리 (0) | 2025.01.13 |
[Data Structure] 이진 트리 순회 (0) | 2025.01.13 |
[Data Structure] 트리, 이진 트리 (0) | 2025.01.12 |