힙 정렬

들어가기 전에

힙을 이용하여 숫자 배열을 정렬하는 힙 정렬 알고리즘에 대해 살펴보도록 하겠습니다.

 

학습 목표

힙 정렬 알고리즘의 원리를 이해하고 직접 해 볼 수 있습니다.

 

핵심 단어

• 힙 정렬 알고리즘
• 시간 복잡도

 

힙:정렬

 

힙 규칙에 맞게 숫자의 순서를 맞추는 과정을 힙 정렬 알고리즘이라고 합니다. 영상에서와 같이, 임의의 숫자들을 나열하고 힙 규칙에 맞게 TrickleDown을 반복하면 그 숫자들이 정렬됩니다.

 

힙 정렬 알고리즘의 시간 복잡도는  O(nlogn)O(nlogn) 입니다. 두 수를 비교해서 하나를 고르는 방식으로 숫자를 골라내기 때문입니다. (총 n개의 숫자를 logn개의 숫자와 비교합니다.)

 

숫자들의 순서를 바꿔 정렬하기 때문에 데이터의 복사본을 만들 필요가 없다는 점이 힙 정렬의 장점입니다.

 

---

 

생각해보기

1) 힙 정렬 알고리즘 외의 정렬 방법에는 어떤 것이 있을까요?

 

나의 생각 : 선혈 정렬, 버블 정렬, 삽입 정렬 등이 있다.

 

 

출처 : https://www.boostcourse.org/cs204/lecture/626046?isDesc=false