Ahn9807: Ahn9807님이 힙정렬 문서를 Heap sort 문서로 이동했습니다

2023-02-25T11:08:09Z

Ahn9807님이 힙정렬 문서를 Heap sort 문서로 이동했습니다

← 이전 판	2023년 2월 25일 (토) 11:08 판
(차이 없음)

2023년 2월 25일 (토) 11:08에 Ahn9807님의 편집

2023-02-25T11:08:02Z

← 이전 판		2023년 2월 25일 (토) 11:08 판
1번째 줄:		1번째 줄:
	[[분류: 정렬 ]]		[[분류: 정렬 알고리즘]]

	==개요 ==		==개요 ==

Ahn9807: 새 문서: 분류: 정렬 ==개요 == 사실 선택 정렬과 거의 같은 알고리즘으로. 단지 가장 큰 원소를 뒤로 보내는 데에 단순히 매번 쭉 돌면서 알아내느냐 힙을 사용하여 알아내느냐가 유일한 차이점이다. 힙정렬은 추가적인 메모리를 전혀 필요로 하지 않는다는 점과, 최악의 경우에 O(n2)O(n^2)O(n2)의 성능을 내는 퀵정렬과 달리 항상 O(nlog⁡n)O(n \log n)O(nlogn) 정렬의 성능을 발휘...

2023-02-25T11:07:49Z

새 문서: 분류: 정렬 ==개요 == 사실 선택 정렬과 거의 같은 알고리즘으로. 단지 가장 큰 원소를 뒤로 보내는 데에 단순히 매번 쭉 돌면서 알아내느냐 힙을 사용하여 알아내느냐가 유일한 차이점이다. 힙정렬은 추가적인 메모리를 전혀 필요로 하지 않는다는 점과, 최악의 경우에 O(n2)O(n^2)O(n2)의 성능을 내는 퀵정렬과 달리 항상 O(nlog⁡n)O(n \log n)O(nlogn) 정렬의 성능을 발휘...

새 문서

[[분류: 정렬 ]]

==개요 ==
사실 선택 정렬과 거의 같은 알고리즘으로. 단지 가장 큰 원소를 뒤로 보내는 데에 단순히 매번 쭉 돌면서 알아내느냐 힙을 사용하여 알아내느냐가 유일한 차이점이다.

힙정렬은 추가적인 메모리를 전혀 필요로 하지 않는다는 점과, 최악의 경우에 O(n2)O(n^2)O(n2)의 성능을 내는 퀵정렬과 달리 항상 O(nlog⁡n)O(n \log n)O(nlogn) 정렬의 성능을 발휘하는 장점이 있다. 하지만 실제 코드를 짜서 비교를 해 보면 퀵정렬이 힙정렬보다 일반적인 경우에 빠르게 동작한다.

그러나 아래 퀵정렬의 경우 피벗을 잡는 전략에 어느 정도의 휴리스틱이 들어가야 최악의 경우를 회피할 수 있으나 힙정렬은 휴리스틱이 필요없이 항상 일정한 성능을 보이는 장점이 있다. 즉 알고리즘에 꼼수를 쓰지 않고, 각종 하드웨어 가속도 전혀 고려하지 않고 알고리즘이 정의하는 최소한만 구현할 경우 힙정렬이 가장 안정적인 성능을 보인다.

Heap sort - 편집 역사

Ahn9807: Ahn9807님이 힙정렬 문서를 Heap sort 문서로 이동했습니다

2023년 2월 25일 (토) 11:08에 Ahn9807님의 편집