[Algorithm] Heap Sort : 힙 정렬, 힙 소트 ( 코드 포함 )

힙 소트는 힙이라는 자료구조를 이용하여 정렬하는 방식이다.

힙은 '각 노드의 값은 자신의 자식 노드의 값보다 항상 작다' 를 만족하는 자료구조이다.

따라서 힙의 머리부분은 항상 제일 작다.

 

정렬을 위해서 궂이 리스트를 이용하여 힙을 만들 필요는 없고 배열로 만들면 된다.

 

주어진 배열을 힙으로 만든 뒤 가장 작은 값을 차례로 줄여 힙의 크기를 감소하는 방법을 사용한다.

힙 배열에서 a[k]의 자식의 위치는 a[k]와 a[k+1]이다. k가 왼쪽, k+1이 오른쪽이다.

a[k]의 부모노드는 a[k/2]이다.

 

먼저 결과 샷

 

 

템플릿을 이용하여 범용성을 구현하기엔 너무 귀찮고 어디서 재활용할 것도 아니기 때문에(퀵소트 *를 이미 템플릿으로 짜놔서 그거 쓸래..)

그냥 int 배열을 인자로 받는 힙 정렬을 구현하였다.

 

먼저 힙을 만드는 함수이다.

 

n-1을 하는 이유는 n은 배열 인자의 개수이다.

알다시피 배열의 갯수가 10개라면 배열인덱스는 0부터 9까지이다.

따라서 a[10]에 접근하면 문제가 될 수 있기 때문에 n-1을 해준다.

for문을 (n-1)/2부터 0까지 감소하는 이유는 (n-1)/2가 리프노드가 아닌 노드 중 맨 마지막 노드의 인덱스이기 때문이다.

 

힙을 실제적으로 만드는 함수이다.

 

자식 노드의 위치를 파악한 뒤 자식이 존재하는지 검사한다.

왼쪽 자식과 오른쪽 자식 중 더 작은 것을 고르고 자신과의 크기를 비교한다.

자신이 더 크다면 자리를 변경하고 힙을 재정립한다.

 

힙을 만들고 출력하면 아래와 같다.

 

잘 보면 첫번째 노드인 0의 자식은 1과 2이다.

이 둘은 0보다 크다.

하지만 완벽하게 정렬이 되어 있는 상태는 아니다.

 

힙을 정렬하는 부분

 

똑같은 크기의 배열을 만든 뒤 0번째 인자를 새로 만든 배열에 넣고 기존 노드를 0부터 n-1까지 다시 재정립한다.

이를 계속 반복한 뒤 원래 노드로 복사한다.

memcpy를 사용하는게 더 간편하고 메모리 복사라 좋은데 왜 난 for문이 더 편할까...

 

 

 

*https://kwonriver.tistory.com/6

[Algorithm] Quick Sort : 퀵 정렬, 퀵 소트