힙

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

힙이란?

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

힙 정렬은 선택 정렬(가장 큰 요소 선택)을 응용한 알고리즘
불안정 정렬
힙 정렬의 시간 복잡도 : O(n log n)

• 부모는 a[(i – 1) / 2]
• 왼쪽 자식은 a[i * 2 + 1]
• 오른쪽 자식은 a[i * 2 + 2]

도수 정렬

https://kururu.tistory.com/61

도수 정렬은 요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘
- 데이터의 비교, 교환 작업이 필요 없어 매우 빠름
- 단일 for문만을 사용, 재귀 호출, 이중 for문이 없어 아주 효율적인 알고리즘
- 도수분포표가 필요하기 때문에 데이터의 최솟값과 최댓값을 미리 알고 있는 경우에만 사용할 수 있음
- 뒤에서 순서대로 스캔하므로 안정적인 알고리즘

• 1단계 : 도수분포표 작성
• 2단계 : 누적 도수 분포표 작성
• 3단계 : 목적 배열 만들기
• 4단계 : 배열의 복사

1. 도수분포표 만들기

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

f[i] += f[i-1]

3. 목적 배열 만들기

4. 배열 복사하기

정렬을 마친 작업 배열 b값을 배열 a로 복사

---

• 안정 정렬
  버블, 삽입, 병합, 도수

• 불안정 정렬
  선택, 퀵, 힙