힙 정렬(heap sort)

힙 정렬 알고리즘 개념

---

과정 설명

• 오름차순을 구성하기 위해서는 배열을 최대힙으로 구성
• 최대 힙의 가장 첫번째 원소(배열에서 가장 큰 원소)를 하나씩 빼면서 정렬
• 힙의 원소가 하나 남을 때까지 반복

 

과정 상세 설명

정렬할 요소들을 가지고 배열에 하나씩 요소들을 넣으면서 최대 힙 구성

정렬할 요소 (4, 3, 2, 5, 1, 6)

맨 처음 원소 삽입 과정을 따로 처리할 과정이 없으므로 생략

 

인덱스	1	2	3	4	5	6
	4	3	2

3 삽입

인덱스 2의 부모인 1과 비교, 인덱스 1의 원소가 더 크므로 pass

2 삽입시에도 동일

 

 

인덱스	1	2	3	4	5	6
	4	3	2	5

↓

인덱스	1	2	3	4	5	6
	4	5	2	3

↓

인덱스	1	2	3	4	5	6
	5	4	2	3

5 삽입

인덱스 4의 부모인 인덱스 2의 원소와 값 비교, 인덱스 4의 값이 더 크므로 인덱스 4와 2의 값 swap

인덱스 2의 부모인 인덱스 1과 값 비교, 인덱스 2의 값이 더 크므로 인덱스 2와 1의 값 swap

 

1 삽입시에는 문제 없으므로 pass

 

 

인덱스	1	2	3	4	5	6
	5	4	2	3	1	6

↓

인덱스	1	2	3	4	5	6
	5	4	6	3	1	2

↓

인덱스	1	2	3	4	5	6
	6	4	5	3	1	2

6 삽입

인덱스 6 > 인덱스 3이므로 인덱스 6과 3 swap

인덱스 3 > 인덱스 1이므로 인덱스 3과 1 swap

최대 힙 (6, 4, 5, 3, 1, 2) 완성

 

힙의 원소를 삭제하면서 정렬

인덱스 1의 원소를 인덱스 6과 swap 한 다음인덱스 6을 제외한 나머지 배열이 최대힙을 구성하도록 인덱스 1의 위치를 재조정

인덱스	1	2	3	4	5	6
	2	4	5	3	1	6

↓

인덱스	1	2	3	4	5	6
	5	4	2	3	1	6

인덱스 1의 자식인 인덱스 2, 3과 비교해서 제일 큰 수를 인덱스 1로 올린다.

인덱스 3과 1을 swap

지금 배열에서 인덱스 6은 없는 것으로 간주하므로 인덱스 3의 자식이 없어서 여기서 종료

 

인덱스	1	2	3	4	5	6
	1	4	2	3	5	6

↓

인덱스	1	2	3	4	5	6
	4	1	2	3	5	6

↓

인덱스	1	2	3	4	5	6
	4	3	2	1	5	6

인덱스 1의 자식인 인덱스 2, 3과 비교해서 제일 큰 수를 인덱스 1로 올린다.

인덱스 2와 1을 swap

인덱스 2의 자식인 인덱스 4와 비교해서 (지금 배열에서 인덱스 5, 6은 없는 것으로 간주하므로) 제일 큰 수를 인덱스 2로 올린다.

인덱스 4와 2을 swap

 

인덱스	1	2	3	4	5	6
	1	2	3	4	5	6

이런 과정을 계속 거치게 되면 위와 같이 정렬된 배열이 나타나게 된다.

 

퀵 정렬 알고리즘 시간복잡도

---

Best: nlogn

Avg: nlogn

Worst: nlogn

 

 

References

---

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

[알고리즘] 힙 정렬(heap sort)이란 - Heee's Development Blog