[C++] 정렬 #2 삽입 정렬 & 힙 정렬 (Insertion Sort & Heap Sort)

목차

※ 정렬 #1 버블 정렬 & 선택 정렬

 

1. 삽입 정렬 (Insertion Sort)

2. 힙 정렬 (Heap Sort)

---

1. 삽입 정렬 (Insertion Sort)

- 배열의 요소를 앞에서 부터 이미 정렬된 배열과 비교하여 자신의 위치를 찾아 정렬

- 1회전 마다 하나씩 요소들을 정렬해나간다.

- 배열이 길수록 효율이 떨어진다. (비교할 정렬이 길어지므로)

- 본인 위치를 찾아 삽입하여 정렬하므로 삽입 정렬이라 한다.

- 시간 복잡도가 버블 정렬, 선택 정렬과 같은 O(n²) 이지만 둘 보다 빠르다.

 

삽입 정렬 애니메이션

 

가. 구현하기

삽입 정렬 결과

 

2. 힙 정렬 (Heap Sort)

- 완전 이진 트리로 구성되어 최대 힙 트리나 최소 힙 트리를 구성해 정렬.

- 정렬된 최대(최소) 힙에서 루트 노드를 꺼내어 배열에 저장한다.

- 루트 노드가 삭제되면 힙의 재구성을 거쳐 제외된 값을 제외한 가장 큰(작은) 값이 루트 노드가 된다.

- 최대, 최소값 탐색에 최적화 되어있다.

- 시간복잡도가 O(nlog₂n) 으로서 빠르다.

 

※ 힙 트리와 우선 순위 큐

https://yellowtail2357.tistory.com/66

 

가. 구현하기

힙 정렬 결과

 

 ※ 참조

위키 백과 삽입 정렬

https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

위키 백과 힙 정렬

https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC

동빈나 유튜브 힙 정렬

https://www.youtube.com/watch?v=iyl9bfp_8ag&t=1038s