it-swarm-ko.tech

왜 quicksort가 mergesort보다 나은가요?

나는 인터뷰에서이 질문을 받았다. 둘 다 O(nlogn)이지만 대부분의 사람들은 Mergesort 대신 Quicksort를 사용합니다. 그게 왜?

339

Quicksort에는 O (2) 최악의 경우 런타임 및 O (로그) 평균 사례 런타임. 그러나 여러 가지 요인이 알고리즘의 런타임에 영향을 미치고 모든 것을 함께 가져갈 때 quicksort가 이기기 때문에 많은 시나리오에서 병합 정렬보다 우수합니다.

특히 정렬 알고리즘의 자주 인용되는 런타임은 데이터를 정렬하는 데 필요한 비교 횟수 또는 스왑 수를 나타냅니다. 이것은 실제로 성능의 좋은 척도이며, 특히 기본 하드웨어 설계와 독립적입니다. 그러나 참조의 지역성 (예 : 캐시에있는 많은 요소를 읽습니까?)과 같은 다른 것들도 현재 하드웨어에 중요한 역할을합니다. Quicksort는 특히 추가 공간을 거의 필요로하지 않고 캐시 위치를 잘 나타내므로 많은 경우 병합 정렬보다 빠르게 만듭니다.

또한, quicksort의 최악의 실행 시간 인 O를 피하는 것은 매우 쉽다.2) 거의 모든 선택의 피벗 - 무작위로 선택 (예 : 훌륭한 전략)을 사용합니다.

실제로, quicksort (특히 libstdc ++의 std::sort)의 많은 현대 구현은 실제로 introsort 인데, 이론 최악의 경우는 O (로그), 병합 정렬과 동일합니다. 재귀 깊이를 제한하고 로그를 초과하면 다른 알고리즘 ( heapsort )으로 전환하여이를 달성합니다.

253
Konrad Rudolph

많은 사람들이 지적했듯이, quicksort의 평균 사례 성능은 mergesort보다 빠릅니다. But 요청에 따라 메모리에 액세스하는 일정한 시간을 가정 할 경우에만 해당됩니다.

RAM에서이 가정은 일반적으로 너무 나쁘지 않습니다 (캐시 때문에 항상 올바르지는 않지만 그렇게 나쁘지는 않습니다). 그러나 데이터 구조가 디스크에 저장하기에 충분히 큰 경우 평균 디스크가 초당 200 회의 무작위 탐색과 같은 작업을 수행하므로 quicksort가 죽습니다 . 하지만 동일한 디스크는 데이터를 초당 메가 바이트 단위로 읽거나 쓰는 데 문제가 없습니다. 어느 mergesort 정확히 않습니다.

따라서 데이터를 디스크에 정렬해야한다면 정말로, mergesort에 약간의 변형을 사용하고 싶을 것입니다. 일반적으로 하위 목록을 정리 한 다음 크기 임계 값 이상으로 함께 병합을 시작합니다.

또한 그 크기의 데이터 세트로 를해야한다면, 디스크 검색을 피하는 방법에 대해 열심히 생각하십시오. 예를 들어 이것이 데이터베이스에서 많은 양의 데이터를로드하기 전에 인덱스를 삭제 한 다음 나중에 인덱스를 다시 작성하는 것이 표준 조언 인 이유입니다. 로드 중에 색인을 유지 관리한다는 것은 지속적으로 디스크를 찾는 것을 의미합니다. 반대로 인덱스를 삭제하면 데이터베이스는 먼저 처리 할 정보를 정렬하여 색인을 다시 작성한 다음 (이를 mergesort를 사용하여) 인덱스의 BTREE 데이터 구조로로드합니다. (BTREE는 자연스럽게 순서대로 유지되기 때문에 소수의 탐색만으로 정렬 된 데이터 세트에서 하나씩 디스크에로드 할 수 있습니다.)

디스크 검색을 피하는 방법을 이해하면 몇 일 또는 몇 주일이 아닌 몇 시간이 걸리는 데이터 처리 작업을 할 수있는 경우가 많습니다.

271
user11318

사실 QuickSort는 O (n2). 그것의 평균 경우 실행 시간은 O (nlog (n))이지만 최악의 경우는 O (n2). 고유 항목이 거의없는 목록에서 실행할 때 발생합니다. 무작위 화에는 O (n)이 필요합니다. 물론, 이것은 최악의 경우를 변경하지 않으며 단지 악의적 인 사용자가 사용자의 정렬을 오랜 시간이 걸리는 것을 방지합니다.

QuickSort는 다음과 같은 이유로 더 많이 사용됩니다.

  1. 현재 위치에 있습니다 (MergeSort는 정렬 할 요소 수에 선형으로 여분의 메모리가 필요합니다).
  2. 작은 숨겨진 상수가 있습니다.
87
Dark Shikari

"하지만 대부분의 사람들은 Mergesort 대신 Quicksort를 사용합니다. 왜 그런가요?"

주어진 심리학 적 이유 중 하나는 단순히 퀵 소트가 더 똑똑하게 명명 된 것입니다. 즉 좋은 마케팅.

그렇습니다, 트리플 파티셔닝이 포함 된 퀵 포트는 아마도 가장 일반적인 범용 정렬 알고리즘 중 하나 일 수 있습니다. 그러나 "빠른"정렬은 "병합"정렬보다 훨씬 강력합니다.

29
Ash

다른 사람들이 언급했듯이, Quicksort의 최악의 경우는 O (n ^ 2)이며, mergesort와 heaport는 O (nlogn)에 머물러 있습니다. 그러나 평균적인 경우에 세 가지 모두 O (nlogn)입니다. 그래서 그것들은 대다수의 경우에 필적합니다.

Quicksort를 평균적으로 개선하는 이유는 내부 루프가 여러 값을 하나의 값과 비교하는 것을 의미하는 반면 다른 두 값은 비교할 때마다 두 용어가 서로 다르다는 것을 의미합니다. 즉, Quicksort는 다른 두 알고리즘의 절반만큼 읽습니다. 현대 CPU에서 성능은 액세스 시간에 의해 크게 좌우되므로 Quicksort는 결국 최고의 선택입니다.

15
Javier

지금까지 언급 된 세 가지 알고리즘 (mergesort, quicksort 및 heap sort) 중 mergesort 만 안정적인 것을 추가하고 싶습니다. 즉, 동일한 키가있는 값에 대해서는 순서가 변경되지 않습니다. 어떤 경우에는 이것이 바람직하다.

그러나 진실은 실제 상황에서 대부분의 사람들은 좋은 평균 성과를 필요로하고 quicksort는 ... =

모든 정렬 알고리즘은 기복이 있습니다. 좋은 개요를 보려면 정렬 알고리즘에 대한 Wikipedia 기사 를 참조하십시오.

8
Antti Rasinen

Quicksort의 위키피디아 항목 :

Quicksort는 또한 다른 재귀 정렬 알고리즘 인 mergesort와 경쟁하지만 최악의 경우 Θ (nlogn) 실행 시간의 이점을 제공합니다. Mergesort는 quicksort 및 heaport와는 달리 안정적인 정렬이며 디스크 저장소 나 네트워크 연결 저장소와 같이 액세스가 느린 미디어에 저장된 매우 큰 목록과 연결된 목록에서 작동하도록 쉽게 조정할 수 있습니다. quicksort는 연결된 목록에서 작동하도록 작성할 수 있지만 임의 액세스가없는 피벗 선택이 좋지 않은 경우가 종종 있습니다. mergesort의 가장 큰 단점은 어레이에서 작동 할 때 최상의 경우에 Θ (n) 보조 공간이 필요하지만 in-place 파티셔닝 및 tail 재귀가있는 quicksort의 변형은 Θ (logn) 공간 만 사용한다는 것입니다. (연결된 목록에서 작동 할 때, mergesort는 작고 일정한 양의 보조 기억 장치 만 필요합니다.)

7
gnobal

Mu! Quicksort는 좋지 않습니다. mergesort와는 다른 종류의 응용 프로그램에 적합합니다.

Mergesort는 스피드가 본질적이고 나쁜 최악의 성능이 용인 될 수없고 여분의 공간이 있다면 고려할 가치가 있습니다 . 1

당신은 그들 둘 다 O(nlogn) [...]"라고 말했습니다. 이것은 잘못된 것입니다. "Quicksort는 최악의 경우 n ^ 2/2 비교를 사용합니다." 1 .

그러나 내 경험에 따르면 가장 중요한 속성은 명령형 패러다임으로 프로그래밍 언어를 사용할 때 정렬 할 때 사용할 수있는 순차 액세스를 쉽게 구현할 수 있다는 것입니다.

1 Sedgewick, 알고리즘

7
Roman Glass

Quicksort는 실제로는 가장 빠른 정렬 알고리즘이지만 O (n2)만큼 나쁘게 수행 할 수있는 병적 인 경우가 많이 있습니다.

Heapsort는 O (n * ln (n))에서 실행되도록 보장되며 한정된 추가 저장 영역 만 필요합니다. 그러나 힙소가 평균적으로 퀵소트보다 현저히 느린 것을 보여주는 실제 테스트에 대한 많은 인용이 있습니다.

6
Niyaz

Wikipedia의 설명은 다음과 같습니다.

일반적으로 quicksort는 다른 Θ (nlogn) 알고리즘보다 훨씬 빠릅니다. 왜냐하면 내부 루프가 대부분의 아키텍처에서 효율적으로 구현 될 수 있고 대부분의 실제 데이터에서 2 차 시간 요구 확률을 최소화하는 설계 선택을 할 수 있기 때문입니다 .

퀵 소트

Mergesort

Quicksort 구현에는없는 Mergesort (Ω (n))에 필요한 스토리지 양과 관련된 문제도 있다고 생각합니다. 최악의 경우 알고리즘 시간은 같지만 mergesort는 더 많은 저장 공간이 필요합니다.

5
Mat Mannion

Quicksort는 mergesort보다 좋지 않습니다. O (n ^ 2) (최악의 경우는 거의 발생하지 않음)에서 퀵 정렬은 병합 정렬의 O(nlogn)보다 훨씬 느립니다. Quicksort는 오버 헤드가 적기 때문에 작은 n 컴퓨터와 느린 컴퓨터에서는 더 좋습니다. 그러나 컴퓨터는 오늘날 매우 빨라서 병합 설비의 추가 오버 헤드는 무시할 수 있으며, 매우 느린 퀵 소트의 위험은 대부분의 경우 병합 설비의 중요하지 않은 오버 헤드보다 훨씬 큽니다.

또한, mergesort는 원래의 순서대로 동일한 키를 가진 항목을 남깁니다. 이는 유용한 속성입니다.

4
xpda

병합 정렬과 달리 빠른 정렬은 보조 공간을 사용하지 않습니다. Merge Sort는 보조 공간 O (n)을 사용합니다. 그러나 Merge Sort는 O(nlogn)의 최악의 시간 복잡성을 갖지만 빠른 정렬의 최악의 복잡성은 배열이 이미 정렬 될 때 발생하는 O (n ^ 2)입니다.

3
Shantam Mittal

대답은 기본 값에 대해 DualPivotQuickSort로 가져온 변경 사항에 대해 quicksort w.r.t쪽으로 약간 기울어집니다. 그것은 Java 7 에서 Java.util.Arrays 로 정렬하는 데 사용됩니다.

It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.

여기에서 Java7 구현을 찾을 수 있습니다. http://grepcode.com/file/repository.grepcode.com/Java/root/jdk/openjdk/7-b147/Java/util/Arrays.Java

DualPivotQuickSort에 대한 신난 독서 - http://permalink.gmane.org/gmane.comp.Java.openjdk.core-libs.devel/2628

3
SSR

Merge-sort에서 일반 알고리즘은 다음과 같습니다.

  1. 왼쪽 하위 배열 정렬
  2. 올바른 하위 배열 정렬
  3. 2 개의 정렬 된 하위 배열 병합

최상위 레벨에서 2 개의 정렬 된 하위 배열을 병합하면 N 개의 요소를 처리합니다.

한 단계 아래에서 3 단계의 각 반복에는 N/2 요소를 다루는 것이 포함되지만이 과정을 두 번 반복해야합니다. 그래서 당신은 여전히 ​​2 * N/2 == N 요소를 다루고 있습니다.

그것보다 한 수준 아래에 4 * N/4 == N 요소가 합쳐집니다. 재귀 스택의 모든 깊이에는 해당 깊이에 대한 모든 호출에서 같은 수의 요소가 병합됩니다.

대신 빠른 정렬 알고리즘을 고려하십시오.

  1. 피벗 포인트 선택
  2. 피벗 점을 배열의 올바른 위치에 배치하고 모든 작은 요소를 왼쪽으로, 큰 요소를 오른쪽으로 배치합니다.
  3. 왼쪽 하위 배열 정렬
  4. 오른쪽 하위 배열 정렬

최상위 레벨에서는 N 크기의 배열을 처리합니다. 그런 다음 하나의 피벗 점을 선택하여 올바른 위치에 놓은 다음 알고리즘의 나머지 부분을 완전히 무시할 수 있습니다.

한 수준 아래에, N-1의 결합 된 크기 (즉, 이전 피벗 점 빼기)가있는 2 개의 하위 배열을 다루고 있습니다. 각 하위 배열에 대해 피벗 점을 선택합니다.이 점은 최대 2 개의 피벗 점까지 제공됩니다.

그 아래 하나의 레벨, 당신은 위와 같은 이유로, 결합 된 크기 N-3을 가진 4 개의 서브 어레이를 다루고 있습니다.

그런 다음 N-7 ... N-15 ... N-32 ...

재귀 적 스택의 깊이는 거의 동일하게 유지됩니다 (logN). merge-sort를 사용하면 재귀 적 스택의 각 레벨에서 항상 N 요소 병합을 처리 할 수 ​​있습니다. 그러나 빠른 정렬을 사용하면 처리 할 요소의 수가 스택 아래로 갈수록 줄어 듭니다. 예를 들어, 재귀 적 스택의 중간 부분을 보면, 다루는 요소의 수는 N-2 ^ ((logN)/2)) == N - sqrt (N)입니다.

면책 조항 : merge-sort에서는 매번 2 개의 똑같은 청크로 배열을 나누기 때문에 재귀 깊이는 정확히 logN입니다. 빠른 정렬에서는 피벗 포인트가 배열의 중간에 있지 않기 때문에 재귀 스택의 깊이가 logN보다 약간 클 수 있습니다. 나는 알고리즘의 복잡성에서 실제로 작용하는이 요소와 위에 설명 된 요소가 얼마나 큰 역할을했는지 알아보기 위해 수학을하지 않았습니다.

3
RvPr

Quicksort는 평균 케이스 복잡성이 더 우수하지만 일부 어플리케이션에서는 잘못된 선택입니다. Quicksort는 서비스 거부 공격에 취약합니다. 공격자가 입력을 선택하여 정렬 할 수 있다면, 그는 o (n ^ 2)의 최악의 시간 복잡도를 취하는 세트를 쉽게 만들 수 있습니다.

Mergesort의 평균 사례 복잡성과 최악의 경우의 복잡성은 동일하며 동일한 문제가 발생하지 않습니다. merge-sort의이 속성은 또한 실시간 시스템에있어 탁월한 선택이 될 수 있습니다. 병리학 적 사건이 많이 발생하지 않고 훨씬 느리게 진행되기 때문입니다.

나는 Mergesort에 대해 Quicksort보다 더 큰 팬입니다.

2
Simon Johnson

둘 다 동일한 복잡성 등급에 속하지만, 둘 다 동일한 런타임을 의미하는 것은 아닙니다. Quicksort는 보통 mergesort보다 빠릅니다. 단단한 구현을 코딩하는 것이 더 쉽고, 동작이 더 빨라질 수 있기 때문입니다. quicksort가 일반적으로 사람들이 mergesort 대신에 사용하는 것이 일반적으로 빠르기 때문입니다.

하나! 나는 개인적으로 자주 mergesort 또는 quicksort가 열악한 경우 mergesort로 저하되는 quicksort 변형을 사용할 것입니다. 생각해 내다. Quicksort는 O (n log n) on 평균 입니다. 최악의 경우는 O (n ^ 2)입니다! Mergesort는 항상 O (n log n)입니다. 실시간 성능이나 응답 성이 필수이고 입력 데이터가 악의적 인 소스에서 오는 경우 일반 quicksort는 사용하지 않아야합니다.

2
DJ Capelis

빠른 정렬은 최악의 경우 O (n ^ 2)이지만, 평균적으로 일관된 정렬은 병합 정렬을 수행합니다. 각 알고리즘은 O (nlogn)이지만, Big O에 관해 이야기 할 때 우리는 더 낮은 복잡성 요소를 무시한다는 것을 기억해야합니다. 빠른 정렬은 상수 요소와 관련하여 병합 정렬보다 중요한 개선 사항이 있습니다.

병합 정렬에는 O(2n) 메모리가 필요하지만 빠른 정렬은 제자리에서 수행 할 수 있습니다 (O (n) 만 필요함). 이는 빠른 정렬이 일반적으로 병합 정렬보다 선호되는 또 다른 이유입니다.

추가 정보 :

빠른 정렬의 최악의 경우는 피벗이 잘못 선택 될 때 발생합니다. 다음 예제를 고려하십시오.

[5, 4, 3, 2, 1]

피벗이 그룹에서 가장 작은 또는 가장 큰 숫자로 선택되면 빠른 정렬은 O (n ^ 2)에서 실행됩니다. 목록의 최대 또는 최소 25 %에있는 요소를 선택할 확률은 0.5입니다. 따라서 알고리즘에 0.5의 기회가 주어집니다. 일반적인 피벗 선택 알고리즘 (임의의 요소 선택)을 사용하면 피벗의 모든 선택에 대해 좋은 피벗을 선택할 수있는 가능성이 0.5입니다. 큰 사이즈의 콜렉션의 경우 항상 빈약 한 피벗을 선택할 확률은 0.5 * n입니다. 이 확률에 따라 빠른 정렬은 평균적인 (그리고 전형적인) 경우에 효율적입니다.

2
Wade Anderson

Quicksort가 좋은 이유는 무엇입니까

  • QuickSort는 최악의 경우 N ^ 2, NlogN 평균의 경우를 필요로합니다. 최악의 경우는 데이터가 정렬 될 때 발생합니다. 정렬이 시작되기 전에 랜덤 셔플로 완화 할 수 있습니다.
  • QuickSort는 병합 정렬에 의해 추가 메모리를 사용하지 않습니다.
  • 데이터 세트가 크고 동일한 항목이있는 경우 3 방향 파티션을 사용하여 Quicksort의 복잡성을 줄입니다. 더 나은 동일한 항목의 더 나은 정렬. 모든 항목이 동일하면 선형 시간으로 정렬됩니다. [이것은 대부분의 라이브러리에서 기본 구현입니다]

Quicksort는 항상 Mergesort보다 나은가요?

그렇지 않습니다.

  • Mergesort는 안정적이지만 Quicksort는 그렇지 않습니다. 따라서 출력에 안정성이 필요하면 Mergesort를 사용하십시오. 안정성은 많은 실제 응용 분야에서 필요합니다.
  • 요즘 메모리가 저렴합니다. 따라서 Mergesort에서 사용하는 추가 메모리가 응용 프로그램에 중요하지 않은 경우 Mergesort를 사용할 때 아무런 해가 없습니다.

참고 : Java에서 Arrays.sort () 함수는 원시 데이터 형식으로 Quicksort를 사용하고 객체 데이터 형식으로 Mergesort를 사용합니다. 객체가 메모리 오버 헤드를 소비하기 때문에 Mergesort에 약간의 오버 헤드가 추가되어 성능 관점에서 문제가되지 않을 수 있습니다.

참고 자료 : QuickSort 비디오보기 주차, Coursera의 프린스턴 알고리즘 코스

2

이것은 꽤 오래된 질문이지만, 최근에 두 가지를 다루었 기 때문에 여기에 제 2c :

평균 ~ N 로그 N 비교에서 정렬 요구를 병합합니다. 병합하는 동안 우리는 거의 "왼쪽"파트 1/2 N을 선택한 다음 오른쪽 1/2 N 요소를 복사하기 때문에 이미 (거의) 정렬 된 정렬 된 배열의 경우 1/2 N log N이됩니다. 또한 이미 정렬 된 입력은 프로세서의 분기 예측기를 빛나게하지만 거의 모든 분기를 올바르게 추측하여 파이프 라인의 실속을 방지한다고 추측 할 수 있습니다.

평균에 대한 빠른 정렬에는 ~ 1.38 N log N 비교가 필요합니다. 비교의 측면에서 이미 정렬 된 배열로부터 큰 이점을 얻지는 못합니다 (그러나 스왑 및 CPU 내부의 분기 예측과 관련하여).

상당히 현대적인 프로세서의 벤치 마크에서는 다음과 같은 결과를 보여줍니다.

비교 함수가 (qsort () libc 구현에서와 같이) 콜백 함수 일 때, quicksort는 mergesort보다 무작위 입력에서 15 % 더 빠르며 64 비트 정수에서는 이미 정렬 된 배열에서 30 % 느립니다.

반면에 비교가 콜백이 아니라면, 내 경험에 따르면 퀵소트가 mergesort를 최대 25 % 능가하는 것입니다.

그러나 귀하의 (대형) 배열에 매우 적은 고유 값이있는 경우, 병합 정렬은 어떤 경우에도 quicksort를 통해 획득하기 시작합니다.

어쩌면 결론은 : 비교가 비싸면 (예 : 콜백 함수, 문자열 비교, 구조의 많은 부분을 주로 비교하여 차이를 만들기 위해 "3 분의 2"에 이르는 경우) - 기회는 당신이 더 좋을 것이라는 것입니다 병합 정렬. 간단한 작업을 위해 quicksort가 더 빠릅니다.

그 말은 모두 이전에 말한 바와 같다 : - Quicksort는 N ^ 2 일 수 있지만, Sedgewick은 좋은 랜덤 화 된 구현은 N ^ 2가 아닌 일종의 컴퓨터 번개가 번개에 맞을 확률이 더 높다고 주장한다. Mergesort는 여분의 공간이 필요하다.

2
virco

재귀 호출의 수를 계산하여 두 정렬 알고리즘을 모두 실험했을 때 quicksort는 mergesort보다 재귀 호출이 일관되게 적습니다. quicksort에는 피벗이 있고 피벗은 다음 재귀 호출에 포함되어 있지 않기 때문입니다. 그렇게하면 quicksort가 mergesort보다 재귀 적 기본 케이스에 더 빨리 도달 할 수 있습니다.

2
Aldian Fazrihady

빠른 대 작은 병합은 일종의 병합입니다.

또한 정렬 항목의 종류에 따라 다를 수 있습니다. 항목에 대한 액세스, 스왑 및 비교가 평면 메모리의 정수를 비교하는 것과 같은 간단한 작업이 아닌 경우 병합 정렬이 바람직한 알고리즘이 될 수 있습니다.

예를 들어 원격 서버의 네트워크 프로토콜을 사용하여 항목을 정렬합니다.

또한 "연결된 목록"과 같은 사용자 지정 컨테이너에서는 빠른 정렬의 이점이 없습니다.
1. 연결된 목록에 병합 정렬, 추가 메모리가 필요하지 않습니다. 2. 빠른 정렬의 요소에 대한 액세스가 순차적이지 않습니다 (메모리에서).

1
minorlogic

그것은 말하기 어렵습니다. MergeSort의 최악은 n (log2n) -n + 1입니다. n이 2 ^ k와 같으면 정확합니다 (이미 증명했습니다). 그리고 어떤 n에 대해서도 (nlg n - n + 그러나 quickSort의 경우 가장 좋은 것은 nlog2n (또한 n은 2 ^ k와 같습니다)입니다. quickSort로 Mergesort를 나눌 경우 n이 무한대 일 때 1과 같습니다. MergeSort의 최악의 경우가 QuickSort의 가장 좋은 경우보다 퀵 소켓을 사용하는 이유는 무엇입니까?하지만 MergeSort가 없기 때문에 2 초의 memeroy 공간이 필요합니다. 또한 MergeSort는 많은 배열 복사본을 처리해야합니다. 알고리즘의 분석에 포함되지 않습니다. 단어에서 MergeSort는 정말로 theroy의 quicksort보다 faseter지만, 실제로 당신은 memeory 공간, 배열 복사 비용을 고려해야합니다, 합병은 빠른 정렬보다 느립니다. 나는 한 번 실험에서 Java에서 Random 클래스에 의해 1000000 자릿수를 받았고, mergesort에 의해 2610ms, quicksort에 의해 1370ms 걸렸습니다.

1
Peter

모든 것이 평등 해지면 대부분의 사람들이 가장 편리하게 사용할 수있는 것이 무엇이든 사용하기를 기대하며 qsort (3) 경향이 있습니다. 그 quicksort 이외에 배열에 매우 빠르다고 알려져 있습니다. mergesort가 목록에 대한 일반적인 선택 인 것처럼.

내가 궁금해하는 이유는 기수 또는 버킷 정렬을 보는 것이 그렇게 드문 이유입니다. 그것들은 O (n)이고, 적어도 링크 된 목록에 있으며, 필요한 것은 키를 서수로 변환하는 몇 가지 방법입니다. 문자열과 수레는 잘 동작합니다.

그 이유는 컴퓨터 과학이 어떻게 가르쳐 지는지와 관련이 있다고 생각합니다. 나는 심지어 알고리즘 분석의 강사에게 O (n log (n))보다 빨리 정렬 할 수 있음을 보여 주어야했습니다. (그는 당신이 비교 가 O (n log (n))보다 빨리 정렬 할 수 없다는 증거를 가지고있었습니다.

다른 뉴스에서는 부동 소수점을 정수로 정렬 할 수 있지만 나중에 음수를 돌려야합니다.

편집 : 실제로, float-as-integer를 정렬하는 더욱 악의적 인 방법이 있습니다 : http://www.stereopsis.com/radix.html . 비트 플 리핑 트릭은 실제로 사용하는 정렬 알고리즘과 상관없이 사용할 수 있습니다.

1
Anders Eurenius

시간과 공간의 복잡성을 모두 고려하십시오. 병합 정렬 : 시간 복잡도 : O(nlogn), 공간 복잡성 : O (nlogn)

빠른 정렬 : 시간 복잡도 : O (n ^ 2), 공간 복잡성 : O (n)

이제, 그들은 각각 하나의 풍경에서 각각 승리합니다. 그러나 무작위 피벗을 사용하면 거의 항상 O (nlogn)로 빠른 정렬의 시간 복잡성을 줄일 수 있습니다.

따라서 빠른 정렬은 병합 정렬 대신 많은 응용 프로그램에서 선호됩니다.

0
pankaj

빠른 정렬은 내부 정렬 알고리즘이므로 배열에 더 적합합니다. 반면에 병합 정렬에는 O (N)의 추가 저장 공간이 필요하며 링크 된 목록에 더 적합합니다.

배열과 달리, 좋아하는 목록에서는 O(1) 및 O(1) 시간을 사용하여 항목을 가운데에 삽입 할 수 있으므로 병합 정렬의 병합 작업을 추가 공간없이 구현할 수 있습니다. 그러나 배열에 대한 추가 공간 할당 및 할당 해제는 병합 정렬 실행 시간에 나쁜 영향을줍니다. 병합 정렬은 많은 랜덤 메모리 액세스없이 순차적으로 데이터에 액세스하므로 링크 된 목록을 선호합니다.

반면에 빠른 정렬은 많은 랜덤 메모리 액세스를 필요로하며, 배열을 사용하면 연결된 목록에서 요구하는대로 트래버스없이 메모리에 직접 액세스 할 수 있습니다. 또한 배열에 사용되는 빠른 정렬은 배열이 메모리에 연속적으로 저장되므로 참조가 잘됩니다.

두 가지 정렬 알고리즘의 평균 복잡성은 모두 O (NlogN)이지만 일반적으로 일반 작업의 사용자는 저장 용 배열을 사용하므로 빠른 정렬은 선택 알고리즘이어야합니다.

편집 : 방금 병합 정렬 최악/최고/평균 경우 항상 nlogn 있지만 알았지 만 빠른 정렬 n2 (최악의 경우 요소가 이미 정렬 된) nlogn (avg/best 경우 피벗 항상 항상 두 배열을 나눌 때 다를 수 있습니다. 절반).

0
Saad