힙정렬 / 도수정렬

1. 힙정렬이란?

힙정렬(heap sort)은 힙(heap)을 사용하여 정렬하는 알고리즘.

힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전이진트리

이때 부모의 값이 자식보다 항상 작아도 힙이라고 합니다. (부모와 자식 요소의 관계만 일정하면 됨)

힙의 요소를 배열에 저장하면 부모와 자식의 인덱스 사이에 다음과 같은 관계가 성립합니다.

 1) 부모는 a[(i-1)/2]

 2) 왼쪽 자식은 a[i*2+1]

 3) 오른쪽 자식은 a[i*2+2]

이제 힙정렬 해보겠습니다.

---

---

이런방법으로 계속 진행됩니다.

이제는 정렬되지 않은 배열을 힙으로 만들어보겠습니다.

bottom-up 방식)

---

---

- 힙 정렬의 시간 복잡도

힙정렬은 선택정렬을 응용한 알고리즘입니다.

힙정렬에서는 첫 요소를 꺼내는 것만으로 가장 큰 값이 구해지므로 첫 요소를 꺼낸 다음 나머지 요소를 다시 힙으로 만들어야 그 다음에 꺼낼 첫 요소도 가장 큰 값을 유지합니다.

따라서 단순 선택 정렬에서 가장 큰 요소를 선택할 때의 시간복잡도 %O(n)%의 값을 한번에 선택할 수 있어 $O(1)$로 줄일수 있습니다. 그 대신 힙정렬에서 다시 힙으로 만드는 작업의 시간복잡도는 $O(log {n})$ 입니다.

따라서 단순 선택 정렬은 전체 정렬에 걸리는 시간 복잡도의 값이 $O(n^{2})$이지만 힙 정렬은 힙으로 만드는 작업을 요소의 개수만큼 반복하므로 시간 복잡도의 값이 $O(n log {n})$ 으로 개선됩니다.

---

2. 도수정렬?

도수 정렬은 요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘

1) 도수분포표 만들기

---

2) 누적도수분포표 만들기

---

3. 목적 배열 만들기

---

---

---

---

---

---

---

---

---

---

정리한 결과를 원래 배열 A에 복사하기

코드)