항상 힙 정렬을 사용하지 않는 이유

항상 힙 정렬을 사용하지 않는 이유

---

이 질문에 이미 답변이 있습니다.

• Quicksort vs heapsort 11 답변
• Heap Sort 5 답변 보다 Quicksort 우월성

힙 정렬 정렬 알고리즘은 O (nlogn)의 최악의 복잡성을 갖는 것, 및 분류 동작 O (1)의 공간을 사용한다.

이것은 대부분의 정렬 알고리즘보다 낫습니다. 그렇다면 왜 항상 정렬 알고리즘으로 힙 정렬을 사용하지 않는 것일까 요 (그리고 사람들이 병합 정렬 또는 빠른 정렬과 같은 정렬 메커니즘을 사용하는 이유는 무엇입니까?)?

또한 사람들이 힙 정렬과 함께 '불안정성'이라는 용어를 사용하는 것을 보았습니다. 그것은 무엇을 의미합니까?

---

안정적인 정렬은 동일한 키를 가진 항목의 상대적 순서를 유지합니다. 예를 들어 데이터 세트에 직원 ID와 이름이있는 레코드가 포함되어 있다고 가정 해보십시오. 초기 주문은 다음과 같습니다.

1, Jim
2, George
3, Jim
4, Sally
5, George

이름별로 정렬하고 싶습니다. 안정적인 정렬은 다음 순서로 항목을 정렬합니다.

2, George
5, George
1, Jim
3, Jim
4, Sally

"George"에 대한 중복 레코드는 초기 목록에있는 것과 동일한 상대적 순서에 있습니다. 두 개의 "Jim"레코드와 동일합니다.

불안정한 정렬은 다음과 같이 항목을 정렬 할 수 있습니다.

5, George
2, George
1, Jim
3, Jim
4, Sally

힙에 대한 작업이 동일한 항목의 상대적 순서를 변경할 수 있으므로 힙 정렬은 안정적이지 않습니다. 모든 Quicksort 구현이 안정적인 것은 아닙니다. 파티션을 구현하는 방법에 따라 다릅니다.

Heapsort는 최악의 복잡성을 가지고 있지만 이것이 O(n log(n))전체 이야기를 말해주지는 않습니다. 실제 구현에는 이론적 분석에서 고려하지 않는 일정한 요소가 있습니다. Heapsort 대 Quicksort의 경우, Quicksort의 최악의 경우를 매우 드물게 만드는 방법 (예 : 중앙값 5)이 있습니다. 또한 힙을 유지하는 것은 무료가 아닙니다.

정규 분포를 사용하는 배열이 주어지면 Quicksort와 Heapsort는 모두 O(n log(n)). 그러나 Quicksort는 상수 인자가 Heapsort의 상수 인자보다 작기 때문에 더 빨리 실행됩니다. 간단히 말해, 파티셔닝은 힙을 유지하는 것보다 빠릅니다.

---

힙 정렬 의 최악의 복잡도를 갖는다 O(n log(n)). 그러나 경험적 연구에 따르면 일반적으로 빠른 정렬 (및 기타 정렬 알고리즘)이 힙 정렬보다 상당히 빠르지 만 최악의 경우 복잡성은 O(n²)다음과 같습니다. http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort3.html

또한 Wikipedia 의 빠른 정렬 기사 에서 :

quicksort의 가장 직접적인 경쟁자는 heapsort입니다. 힙 소트의 최악의 실행 시간은 항상 O (n log n)입니다. 그러나 힙 정렬은 표준 내부 빠른 정렬보다 평균적으로 다소 느리다고 가정합니다. 이것은 여전히 ​​논란이되고 있으며 연구 중이며 일부 출판물은 그 반대를 나타냅니다. [13] [14] Introsort는 Quicksort의 최악의 실행 시간을 피하기 위해 불량 사례가 감지되면 heapsort로 전환하는 quicksort의 변형입니다. 힙 정렬이 필요하다는 것을 미리 알고있는 경우 직접 사용하는 것이 introsort가 전환 될 때까지 기다리는 것보다 빠릅니다.

그러나 응답 시간을 보장해야하는 애플리케이션에서는 빠른 정렬을 사용해서는 안됩니다!

Stackoverflow의 소스 : Quicksort vs heapsort

---

은색 총알이 없습니다 ...

아직 여기에서 보지 못한 또 다른 주장을 언급합니다.

데이터 세트가 정말 크고 메모리에 맞지 않으면 병합 정렬이 매력처럼 작동합니다. 데이터 세트가 수백 대의 머신에 걸쳐있을 수있는 클러스터에서 자주 사용됩니다.

---

안정적인 정렬 알고리즘은 동일한 키로 레코드의 상대적 순서를 유지합니다.

이러한 종류의 안정성과 같은 일부 응용 프로그램은 대부분 상관하지 않습니다. 예를 들어 Google은 친구입니다.

"사람들은 병합 정렬 또는 빠른 정렬과 같은 정렬 메커니즘을 사용한다"는 당신의 주장에 관해서는 대부분의 사람들이 그들의 언어에 내장 된 것을 사용하고 정렬 알고리즘에 대해 그다지 생각하지 않을 것이라고 확신합니다. 스스로 굴리는 사람들은 아마도 힙 정렬에 대해 들어 보지 못했을 것입니다 (마지막은 개인적인 경험입니다).

마지막이자 가장 큰 이유는 모든 사람이 정렬 된 힙을 원하지 않는다는 것입니다. 어떤 사람들은 정렬 된 목록을 원합니다. 평균적인 Joe Programmer의 상사가 "이 목록 정렬"이라고 말하고 Joe가 "당신이 들어 본 적이없는 힙 데이터 구조입니다.

---

80 년대 중반에 Tandem Non-Stop 컴퓨터에서 잠시 작업했을 때 시스템 인 코어 정렬 루틴이 HeapSort라는 것을 알았습니다. 바로 이것이 보장 된 NlogN 성능을 제공했기 때문입니다. 그래도 사용할 이유가있는 사람이 없어서 실제로 어떻게 작동했는지 모르겠습니다. 나는 heapsort를 좋아하지만 위에서 언급 한 결점들과 함께, 그것은 메모리가 모든 곳에서 접근하게하기 때문에 현대적인 메모리를 잘 활용하지 못한다고 들었습니다. 반면에 quicksort와 작은 기수 정렬은 상대적으로 적은 수를 섞습니다. 순차 읽기 및 쓰기 스트림의 수-캐시가 더 효과적입니다.

참고 URL : https://stackoverflow.com/questions/8311090/why-not-use-heap-sort-always