알고리즘에서 '힙 정렬(Heap Sort)'이 퀵 정렬과 다른 핵심 특징은?
보통 freeCodeCamp해설
힙 정렬은 배열을 최대 힙으로 변환한 후, 루트(최댓값)를 끝으로 보내고 힙 크기를 줄이는 과정을 반복합니다. 최악의 경우에도 O(n log n)을 보장하고 추가 메모리가 O(1)입니다. 퀵 정렬은 평균적으로 더 빠르지만 최악의 경우 O(n²)이며, 힙 정렬은 캐시 지역성이 낮아 실전에서는 느릴 수 있습니다.
힙 정렬은 배열을 최대 힙으로 변환한 후, 루트(최댓값)를 끝으로 보내고 힙 크기를 줄이는 과정을 반복합니다. 최악의 경우에도 O(n log n)을 보장하고 추가 메모리가 O(1)입니다. 퀵 정렬은 평균적으로 더 빠르지만 최악의 경우 O(n²)이며, 힙 정렬은 캐시 지역성이 낮아 실전에서는 느릴 수 있습니다.