728x90 힙소트1 [Algorithm] Heap Sort : 힙 정렬, 힙 소트 ( 코드 포함 ) 힙 소트는 힙이라는 자료구조를 이용하여 정렬하는 방식이다. 힙은 '각 노드의 값은 자신의 자식 노드의 값보다 항상 작다' 를 만족하는 자료구조이다. 따라서 힙의 머리부분은 항상 제일 작다. 정렬을 위해서 궂이 리스트를 이용하여 힙을 만들 필요는 없고 배열로 만들면 된다. 주어진 배열을 힙으로 만든 뒤 가장 작은 값을 차례로 줄여 힙의 크기를 감소하는 방법을 사용한다. 힙 배열에서 a[k]의 자식의 위치는 a[k]와 a[k+1]이다. k가 왼쪽, k+1이 오른쪽이다. a[k]의 부모노드는 a[k/2]이다. 먼저 결과 샷 템플릿을 이용하여 범용성을 구현하기엔 너무 귀찮고 어디서 재활용할 것도 아니기 때문에(퀵소트 *를 이미 템플릿으로 짜놔서 그거 쓸래..) 그냥 int 배열을 인자로 받는 힙 정렬을 구현하였.. [프로그래밍 공부]/Algorithm 2022. 1. 22. 더보기 ›› 728x90 이전 1 다음
