퀵 정렬이 병합 정렬보다 나은 이유는 무엇입니까?

https://stackoverflow.com/questions/70402

09-06-2019
|

문제

인터뷰 중에 이런 질문을 받았어요.둘 다 O(nlogn)이지만 대부분의 사람들은 Mergesort 대신 Quicksort를 사용합니다.왜 그런 겁니까?

해결책

퀵소트는 O(N²) 최악의 런타임 및 O(N통나무N) 평균 사례 런타임.그러나 많은 요소가 알고리즘의 런타임에 영향을 미치고 이를 모두 종합하면 퀵 정렬이 승리하기 때문에 많은 시나리오에서 병합 정렬이 더 우수합니다.

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

게다가 퀵소트의 최악의 경우 O( O(N²) 거의 전적으로 적절한 피벗 선택(예: 무작위로 선택)을 사용합니다(이것은 훌륭한 전략입니다).

실제로 많은 최신 퀵 정렬 구현(특히 libstdc++의 경우) std::sort) 실제로는 내향적인, 이론상 최악의 경우는 O(N통나무N), 병합 정렬과 동일합니다.재귀 깊이를 제한하고 다른 알고리즘으로 전환하여 이를 달성합니다(힙 정렬) 로그를 초과하면N.

다른 팁

많은 사람들이 지적했듯이 퀵 정렬의 평균 사례 성능은 병합 정렬보다 빠릅니다. 하지만 이는 요청 시 메모리에 액세스하는 데 일정한 시간이 걸린다고 가정하는 경우에만 해당됩니다.

RAM에서 이 가정은 일반적으로 그리 나쁘지 않습니다(캐시 때문에 항상 맞는 것은 아니지만 그리 나쁘지는 않습니다).그러나 데이터 구조가 디스크에 저장될 만큼 크다면 Quicksort는 사망 평균 디스크가 초당 200회 정도의 무작위 검색을 수행한다는 사실입니다.그러나 동일한 디스크는 초당 메가바이트의 데이터를 순차적으로 읽거나 쓰는 데 아무런 문제가 없습니다.이것이 바로 mergesort가 수행하는 작업입니다.

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

게다가 해야 할 일이 있다면 아무것 해당 크기의 데이터 세트를 사용하면 디스크 탐색을 방지하는 방법에 대해 열심히 생각해 보세요.예를 들어, 데이터베이스에 대규모 데이터를 로드하기 전에 인덱스를 삭제한 다음 나중에 인덱스를 다시 작성하는 것이 표준 조언인 이유입니다.로드 중에 인덱스를 유지한다는 것은 지속적으로 디스크를 찾는 것을 의미합니다.대조적으로 인덱스를 삭제하면 데이터베이스는 먼저 처리할 정보를 정렬한 다음(물론 mergesort를 사용하여!) 인덱스에 대한 BTREE 데이터 구조에 로드하여 인덱스를 다시 작성할 수 있습니다.(BTREE는 자연스럽게 순서대로 유지되므로 디스크 검색 횟수가 거의 없이 정렬된 데이터 세트에서 하나를 로드할 수 있습니다.)

디스크 탐색을 방지하는 방법을 이해함으로써 데이터 처리 작업을 며칠 또는 몇 주가 아닌 몇 시간이 걸리도록 만들 수 있었던 경우가 많았습니다.

실제로 QuickSort는 O(n²).그것은 평균 사례 실행 시간은 O(nlog(n))이지만 최악의 경우 O(n²), 이는 고유 항목이 거의 포함되지 않은 목록에서 실행할 때 발생합니다.무작위화에는 O(n)이 소요됩니다.물론 이것이 최악의 경우를 바꾸지는 않으며 단지 악의적인 사용자가 귀하의 정렬을 오랜 시간이 걸리게 만드는 것을 방지할 뿐입니다.

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

제자리에 있습니다(MergeSort에는 정렬할 요소 수에 선형적인 추가 메모리가 필요합니다).
작은 숨겨진 상수가 있습니다.

"그러나 대부분의 사람들은 Mergesort 대신 Quicksort를 사용합니다.왜 그런 겁니까?"

아직 제시되지 않은 심리학적 이유 중 하나는 Quicksort의 이름이 더 교묘하다는 것입니다.즉, 좋은 마케팅.

예, 삼중 분할을 사용하는 Quicksort는 아마도 최고의 범용 정렬 알고리즘 중 하나일 것입니다. 그러나 "Quick" 정렬이 "Merge" 정렬보다 훨씬 더 강력하다는 사실을 무시할 수 없습니다.

다른 사람들이 언급했듯이 Quicksort의 최악의 경우는 O(n^2)이고 mergesort와 heapsort는 O(nlogn)에 유지됩니다.그러나 평균적인 경우에는 세 가지 모두 O(nlogn)입니다.그래서 그들은 대부분의 경우에 비교할 수 있습니다.

평균적으로 Quicksort를 더 좋게 만드는 것은 내부 루프가 여러 값을 단일 값과 비교하는 것을 의미하는 반면 다른 두 용어에서는 두 용어가 각 비교마다 다르다는 것입니다.즉, Quicksort는 다른 두 알고리즘에 비해 절반의 읽기 작업을 수행합니다.최신 CPU에서 성능은 액세스 시간에 의해 크게 좌우되므로 결국 Quicksort가 가장 좋은 선택이 됩니다.

지금까지 언급한 세 가지 알고리즘(병합 정렬, 퀵 정렬, 힙 정렬) 중 병합 정렬만이 안정적이라는 점을 추가하고 싶습니다.즉, 동일한 키를 가진 값의 순서는 변경되지 않습니다.어떤 경우에는 이것이 바람직합니다.

그러나 실제로 실제 상황에서 대부분의 사람들은 좋은 평균 성능만 필요하며 퀵 정렬은...빨리 =)

모든 정렬 알고리즘에는 장점과 단점이 있습니다.보다 정렬 알고리즘에 대한 Wikipedia 기사 좋은 개요를 위해.

에서 Quicksort의 Wikipedia 항목:

QuickSort는 또한 또 다른 재귀 정렬 알고리즘 인 Mergesort와 경쟁하지만 최악의 θ (nlogn) 실행 시간의 이점이 있습니다.Mergesort는 QuickSort 및 Heapsort와 달리 안정적인 정렬이며 링크 된 목록 및 디스크 스토리지 또는 네트워크 연결 스토리지와 같은 느린 액세스 미디어에 저장된 매우 큰 목록에서 쉽게 조작 할 수 있습니다.QuickSort는 링크 된 목록에서 작동하도록 작성 될 수 있지만 종종 무작위 액세스가없는 피벗 선택이 불량합니다.Mergesort의 주요 단점은 배열에서 작동 할 때 최상의 경우 θ (n) 보조 공간이 필요하지만, 현장 파티셔닝 및 테일 재귀가있는 QuickSort의 변형은 θ (logn) 공간 만 사용한다는 것입니다.(링크 된 목록에서 작동 할 때 Mergesort는 소량의 일정한 양의 보조 저장소 만 필요합니다.)

뮤!Quicksort는 더 좋지 않으며 mergesort보다 다른 종류의 응용 프로그램에 적합합니다.

Mergesort는 속도가 핵심이고, 나쁜 최악의 성능을 용납할 수 없으며, 추가 공간을 사용할 수 있는 경우 고려해 볼 가치가 있습니다.1

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

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

1 세지윅, 알고리즘

Quicksort는 실제로 가장 빠른 정렬 알고리즘이지만 O(n2)만큼 성능이 저하될 수 있는 병리학적 사례가 많이 있습니다.

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

위키피디아의 설명은 이렇습니다.

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

퀵소트

병합정렬

퀵소트 구현에는 없는 Mergesort(Ω(n))에 필요한 저장 용량에도 문제가 있다고 생각합니다.최악의 경우 알고리즘 시간은 동일하지만 병합 정렬에는 더 많은 저장 공간이 필요합니다.

Quicksort는 mergesort보다 낫지 않습니다.O(n^2)(드물게 발생하는 최악의 경우)의 경우 퀵 정렬은 잠재적으로 병합 정렬의 O(nlogn)보다 훨씬 느립니다.Quicksort는 오버헤드가 적으므로 n이 작고 느린 컴퓨터에서는 더 좋습니다.그러나 오늘날 컴퓨터는 너무 빠르기 때문에 병합 정렬의 추가 오버헤드는 무시할 수 있으며, 매우 느린 퀵 정렬의 위험은 대부분의 경우 병합 정렬의 미미한 오버헤드보다 훨씬 큽니다.

또한 병합 정렬은 항목을 원래 순서대로 동일한 키로 남겨두는데 이는 유용한 속성입니다.

기존의 훌륭한 답변에 QuickSort가 최상의 경우에서 벗어날 때 수행하는 방식과 그 가능성에 대한 몇 가지 수학을 추가하고 싶습니다. 이를 통해 O(n^2) 사례가 실제가 아닌 이유를 사람들이 좀 더 잘 이해하는 데 도움이 되기를 바랍니다. QuickSort의 보다 정교한 구현에 관심이 있습니다.

무작위 액세스 문제 외에도 QuickSort의 성능에 영향을 미칠 수 있는 두 가지 주요 요소가 있으며 둘 다 피벗이 정렬되는 데이터와 비교되는 방식과 관련이 있습니다.

1) 데이터의 키 수가 적습니다.피벗 위치를 제외한 모든 값이 매번 한쪽에 배치되기 때문에 동일한 값의 데이터 세트는 바닐라 2 파티션 QuickSort에서 n^2 시간에 정렬됩니다.최신 구현에서는 3분할 정렬 사용과 같은 방법으로 이 문제를 해결합니다.이러한 메서드는 O(n) 시간 내에 모두 동일한 값의 데이터 세트에서 실행됩니다.따라서 이러한 구현을 사용한다는 것은 적은 수의 키를 사용한 입력이 실제로 성능 시간을 향상시키며 더 이상 문제가 되지 않는다는 것을 의미합니다.

2) 매우 잘못된 피벗 선택은 최악의 성능을 초래할 수 있습니다.이상적인 경우 피벗은 항상 데이터가 50% 더 작고 50%가 더 커지므로 각 반복 중에 입력이 절반으로 나뉩니다.이는 O(n*logn) 시간 동안 n개의 비교 및 스왑 시간 log-2(n) 재귀를 제공합니다.

이상적이지 않은 피벗 선택이 실행 시간에 얼마나 영향을 줍니까?

데이터의 75%가 피벗의 한쪽에 있도록 피벗이 일관되게 선택되는 경우를 고려해 보겠습니다.여전히 O(n*logn)이지만 이제 로그의 기준이 1/0.75 또는 1.33으로 변경되었습니다.베이스 변경 시 성능 관계는 항상 log(2)/log(newBase)로 표시되는 상수입니다.이 경우 해당 상수는 2.4입니다.따라서 이러한 피벗 선택 품질은 이상적인 것보다 2.4배 더 오래 걸립니다.

상황이 얼마나 빨리 악화되나요?

피벗 선택이 (지속적으로) 매우 나빠질 때까지는 그리 빠르지 않습니다.

한쪽에 50%:(이상적인 경우)
한쪽에 75%:2.4배 더 길다
한쪽면 90%:6.6배 더 길다
한쪽면 95%:13.5배 더 길다
한쪽면 99%:69배 더 길다

한쪽에서 100%에 접근하면 실행의 로그 부분이 n에 접근하고 전체 실행이 점근적으로 O(n^2)에 접근합니다.

QuickSort의 순진한 구현에서 정렬된 배열(첫 번째 요소 피벗의 경우) 또는 역정렬된 배열(마지막 요소 피벗의 경우)은 최악의 경우 O(n^2) 실행 시간을 안정적으로 생성합니다.또한 예측 가능한 피벗 선택을 사용하는 구현은 최악의 실행을 생성하도록 설계된 데이터에 의한 DoS 공격을 받을 수 있습니다.최신 구현에서는 정렬 전 데이터 무작위화, 무작위로 선택된 3개의 인덱스의 중앙값 선택 등과 같은 다양한 방법을 통해 이를 방지합니다.이러한 무작위화를 혼합하면 다음과 같은 두 가지 경우가 있습니다.

작은 데이터 세트.최악의 경우는 합리적으로 가능하지만 n은 n^2도 작을 정도로 작기 때문에 O(n^2)는 치명적이지 않습니다.
대규모 데이터 세트.이론상으로는 최악의 경우가 가능하지만 실제로는 그렇지 않습니다.

끔찍한 성과를 볼 가능성은 얼마나 됩니까?

기회는 사라질 정도로 작은.일종의 5,000개의 값을 고려해 보겠습니다.

우리의 가상 구현은 무작위로 선택된 3개의 인덱스의 중앙값을 사용하여 피벗을 선택합니다.25%-75% 범위에 있는 피벗을 "양호"로 간주하고 0%-25% 또는 75%-100% 범위에 있는 피벗을 "나쁨"으로 간주합니다.3개의 무작위 인덱스의 중앙값을 사용하여 확률 분포를 살펴보면 각 재귀가 좋은 피벗으로 끝날 확률은 11/16입니다.수학을 단순화하기 위해 2가지 보수적인(그리고 잘못된) 가정을 만들어 보겠습니다.

좋은 피벗은 항상 정확히 25%/75% 분할로 이루어지며 2.4*이상적인 경우에서 작동합니다.우리는 이상적인 분할이나 25/75보다 더 나은 분할을 결코 얻지 못합니다.
잘못된 피벗은 항상 최악의 경우이며 본질적으로 솔루션에 아무런 기여도 하지 않습니다.

QuickSort 구현은 n=10에서 멈추고 삽입 정렬로 전환하므로 입력된 5,000개 값을 여기까지 나누려면 22개의 25%/75% 피벗 파티션이 필요합니다.(10*1.333333^22 > 5000) 또는 최악의 경우 피벗이 4990개 필요합니다.22개의 좋은 피벗을 축적하면 어느 지점이든 그런 다음 정렬이 완료되므로 최악의 경우 또는 그 근처의 모든 경우에 필요합니다. 극도로 불행.n=10으로 정렬하는 데 필요한 22개의 좋은 피벗을 실제로 달성하는 데 88번의 재귀가 필요했다면 이는 4*2.4*이상적인 경우 또는 이상적인 경우의 실행 시간의 약 10배가 됩니다.우리가 그럴 가능성은 얼마나 됩니까? ~ 아니다 88번의 재귀 후에 필요한 22개의 좋은 피벗을 달성합니까?

이항 확률 분포 그것에 답할 수 있고 그 답은 약 10^-18입니다.(n은 88, k는 21, p는 0.6875) 사용자가 5,000개의 항목 정렬이 실행되는 것을 보는 것보다 [정렬]을 클릭하는 데 걸리는 1초 동안 번개를 맞을 가능성이 약 1000배 더 높습니다. 더 나빠지면 10*이상적인 경우보다.데이터 세트가 커질수록 이 기회는 작아집니다.다음은 몇 가지 배열 크기와 10*이상보다 오래 실행될 가능성입니다.

640개 항목 배열:10^-13(60회 시도 중 15개의 좋은 피벗 포인트 필요)
5,000개 항목 배열:10^-18(88번의 시도 중 22번의 좋은 피벗이 필요함)
40,000개 항목 배열: 10^-23(116개 중 29개의 좋은 피벗 필요)

이는 현실보다 더 나쁜 2가지 보수적인 가정을 사용한 것임을 기억하세요.따라서 실제 성능은 아직 더 좋고, 남은 확률의 균형은 그렇지 않은 것보다 이상적에 더 가깝습니다.

마지막으로, 다른 사람들이 언급했듯이 재귀 스택이 너무 깊어지면 힙 정렬로 전환하여 이러한 터무니없는 경우도 제거할 수 있습니다.따라서 TLDR은 QuickSort를 올바르게 구현하려면 최악의 경우라는 것입니다. 실제로는 존재하지 않는다 엔지니어링되어 O(n*logn) 시간 내에 실행이 완료되기 때문입니다.

대답은 기본 값에 대해 DualPivotQuickSort를 사용하여 가져온 변경 사항에 따라 Quicksort쪽으로 약간 기울어집니다.그것은에서 사용됩니다 자바 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

병합 정렬의 일반적인 알고리즘은 다음과 같습니다.

왼쪽 하위 배열 정렬
오른쪽 하위 배열 정렬
2개의 정렬된 하위 배열을 병합합니다.

최상위 수준에서 2개의 정렬된 하위 배열을 병합하려면 N개 요소를 처리해야 합니다.

한 수준 아래에서는 3단계의 각 반복에서 N/2 요소를 처리하지만 이 프로세스를 두 번 반복해야 합니다.따라서 여전히 2 * N/2 == N 요소를 다루고 있습니다.

한 수준 아래에서는 4 * N/4 == N 요소 등을 병합합니다.재귀 스택의 모든 깊이에는 해당 깊이에 대한 모든 호출에서 동일한 수의 요소를 병합하는 작업이 포함됩니다.

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

피벗 포인트 선택
모든 작은 요소는 왼쪽에, 큰 요소는 오른쪽에 배치하여 배열의 올바른 위치에 피벗점을 배치합니다.
왼쪽 하위 배열 정렬
오른쪽 하위 배열 정렬

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

한 수준 아래에서는 결합된 크기가 N-1인 2개의 하위 배열을 처리합니다(즉, 이전 피벗점을 뺍니다).각 하위 배열에 대한 피벗점을 선택하면 최대 2개의 추가 피벗점이 생성됩니다.

한 수준 아래에서는 위와 같은 이유로 결합된 크기 N-3의 하위 배열 4개를 처리합니다.

그럼 N-7...그렇다면 N-15...그렇다면 N-32...

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

부인 성명:병합 정렬에서는 매번 배열을 정확히 동일한 2개의 청크로 나누기 때문에 재귀 깊이는 정확히 logN입니다.빠른 정렬에서는 피벗 포인트가 정확히 배열의 중앙에 있을 가능성이 낮기 때문에 재귀 스택의 깊이가 logN보다 약간 클 수 있습니다.나는 이 요소와 위에 설명된 요소가 실제로 알고리즘의 복잡성에 얼마나 큰 역할을 하는지 확인하기 위해 수학을 수행하지 않았습니다.

병합 정렬과 달리 빠른 정렬은 보조 공간을 사용하지 않습니다.병합 정렬은 보조 공간 O(n)을 사용합니다.그러나 병합 정렬의 최악의 시간 복잡도는 O(nlogn)인 반면, 빠른 정렬의 최악의 복잡도는 배열이 이미 정렬된 경우 발생하는 O(n^2)입니다.

둘 다 동일한 복잡성 클래스에 속하지만 둘 다 동일한 런타임을 갖는다는 의미는 아닙니다.Quicksort는 일반적으로 mergesort보다 빠릅니다. 왜냐하면 엄격한 구현을 코딩하는 것이 더 쉽고 수행하는 작업이 더 빨라질 수 있기 때문입니다.사람들이 병합 정렬 대신 퀵 정렬을 사용하는 것이 일반적으로 더 빠르기 때문입니다.

하지만!저는 개인적으로 mergesort 또는 퀵소트가 제대로 작동하지 않을 때 mergesort로 저하되는 퀵소트 변형을 자주 사용합니다.기억하다.Quicksort는 O(n log n)에만 적용됩니다. 평균.최악의 경우는 O(n^2)입니다!병합 정렬은 항상 O(n log n)입니다.실시간 성능이나 응답성이 필수이고 입력 데이터가 악의적인 소스에서 나올 수 있는 경우, 일반 퀵 정렬을 사용하면 안 됩니다.

Quicksort는 평균 사례 복잡성이 더 높지만 일부 응용 프로그램에서는 잘못된 선택입니다.Quicksort는 서비스 거부 공격에 취약합니다.공격자가 정렬할 입력을 선택할 수 있다면 그는 o(n^2)의 최악의 시간 복잡도를 취하는 집합을 쉽게 구성할 수 있습니다.

Mergesort의 평균 사례 복잡성과 최악 사례 복잡성은 동일하므로 동일한 문제가 발생하지 않습니다.병합 정렬의 이러한 속성은 실시간 시스템에 대한 탁월한 선택이기도 합니다. 이는 훨씬 더 느리게 실행되도록 하는 병리학적 사례가 없기 때문입니다.

이러한 이유로 저는 Quicksort보다 Mergesort를 더 좋아합니다.

퀵소트가 왜 좋은가요?

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

Quicksort는 항상 Mergesort보다 낫습니까?

설마.

Mergesort는 안정적이지만 Quicksort는 그렇지 않습니다.따라서 출력의 안정성이 필요한 경우 Mergesort를 사용합니다.많은 실제 응용 프로그램에서는 안정성이 필요합니다.
요즘 메모리 가격이 저렴하네요.따라서 Mergesort에서 사용하는 추가 메모리가 응용 프로그램에 중요하지 않은 경우 Mergesort를 사용해도 아무런 해가 없습니다.

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

참조:QuickSort 비디오 보기 3주차, Coursera의 프린스턴 알고리즘 강좌

빠른 정렬은 최악의 경우 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입니다.이 확률을 기반으로 퀵 정렬은 평균(및 일반) 사례에 효율적입니다.

이것은 꽤 오래된 질문이지만 최근에 두 가지를 모두 다루었으므로 여기에 내 2c가 있습니다.

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

평균적으로 빠른 정렬에는 ~ 1.38 N log N 비교가 필요합니다.비교 측면에서 이미 정렬된 배열의 이점은 크지 않습니다(그러나 스왑 측면에서는 그리고 아마도 CPU 내부 분기 예측 측면에서는 그렇습니다).

상당히 현대적인 프로세서에 대한 내 벤치마크는 다음을 보여줍니다.

비교 함수가 콜백 함수인 경우(qsort() libc 구현과 같이) 빠른 정렬은 병합 정렬보다 무작위 입력에서 15% 느리고 64비트 정수에 대해 이미 정렬된 배열에서는 30% 느립니다.

반면에 비교가 콜백이 아닌 경우 내 경험에 따르면 퀵 정렬은 병합 정렬보다 최대 25% 성능이 뛰어납니다.

그러나 (대형) 배열에 고유한 값이 거의 없는 경우 어떤 경우에도 병합 정렬이 퀵 정렬보다 우선하기 시작합니다.

따라서 아마도 결론은 다음과 같습니다.비교 비용이 많이 드는 경우(예:콜백 함수, 문자열 비교, 차이를 만들기 위해 주로 2-3-4 "if"에 도달하는 구조의 여러 부분 비교) - 병합 정렬을 사용하는 것이 더 나을 가능성이 있습니다.간단한 작업의 경우 퀵 정렬이 더 빠릅니다.

이전에 말한 내용은 모두 사실입니다.- QuickSort는 n^2 일 수 있지만 Sedgewick은 좋은 무작위 구현이 컴퓨터를 수행하는 것보다 번개에 맞게 컴퓨터를 수행 할 가능성이 더 높다고 주장합니다.

재귀 호출 수를 계산하여 두 정렬 알고리즘을 실험 할 때 QuickSort는 Mergesort보다 재귀 호출이 덜 있습니다.퀵소트에는 피벗이 있고, 다음 재귀 호출에는 피벗이 포함되지 않기 때문입니다.이렇게 하면 퀵 정렬이 병합 정렬보다 더 빠르게 재귀 기본 사례에 도달할 수 있습니다.

모든 조건이 동일하다면 대부분의 사람들은 가장 편리하게 사용할 수 있는 것을 사용하기를 기대하며 이는 qsort(3) 경향이 있습니다.그 외에는 병합 정렬이 목록에 대한 일반적인 선택과 마찬가지로 배열에서 매우 빠른 것으로 알려져 있습니다.

궁금한 건 왜 이렇게 보기 힘든지 어근 또는 버킷 정렬.적어도 연결된 목록에서는 O(n)이며 필요한 것은 키를 서수로 변환하는 방법뿐입니다.(문자열과 부동 소수점은 잘 작동합니다.)

그 이유는 컴퓨터 과학을 가르치는 방식과 관련이 있다고 생각합니다.나는 심지어 O(n log(n))보다 더 빠르게 정렬하는 것이 실제로 가능하다는 것을 알고리즘 분석 강의에서 강사에게 보여주어야 했습니다.(그는 당신이 그럴 수 없다는 증거를 가지고 있었어. 비교 O(n log(n))보다 빠르게 정렬됩니다. 이는 사실입니다.)

다른 소식으로, 부동소수점은 정수로 정렬될 수 있지만 나중에 음수를 바꿔야 합니다.

편집하다:실제로 부동 소수점을 정수로 정렬하는 훨씬 더 악의적인 방법은 다음과 같습니다. http://www.stereopsis.com/radix.html.실제로 어떤 정렬 알고리즘을 사용하는지에 관계없이 비트 뒤집기 트릭을 사용할 수 있습니다.

말하기는 어렵습니다. MergeSort의 최악은 n(log2n)-n+1입니다. 이는 n이 2^k인 경우 정확합니다(이미 증명했습니다). 그리고 모든 n에 대해 (n lg n - n + 1) 및 (n lg n + n + O(lg n)). 그러나 QuickSort의 경우 가장 좋은 것은 nlog2n입니다(또한 n은 2^k와 같습니다). Mergesort를 QuickSort로 나누면 n이 무한할 때 1과 같습니다. 따라서 마치 MergeSort의 최악의 경우가 QuickSort의 최선의 경우보다 나은 것 같습니다. 왜 퀵 정렬을 사용합니까? 하지만 기억하세요. MergeSort는 제자리에 있지 않으며 2n 메모리 공간이 필요합니다. 그리고 MergeSort는 또한 많은 배열 복사본을 수행해야 합니다. 알고리즘 분석에 포함하지 마십시오. 한마디로 MergeSort는 실제로 Quick Sort보다 빠르지만 실제로는 메모리 공간, 배열 복사 비용, Merger가 Quick Sort보다 느립니다. Java에서 Random 클래스에 의해 1000000자리 숫자가 주어졌고 병합 정렬에서는 2610ms, 퀵 정렬에서는 1370ms가 걸렸습니다.

빠른 정렬과 병합 정렬에 대한 작은 추가 사항입니다.

또한 정렬 항목의 종류에 따라 달라질 수 있습니다.항목에 대한 액세스, 교환 및 비교가 평면 메모리의 정수 비교와 같은 간단한 작업이 아닌 경우 병합 정렬이 선호되는 알고리즘이 될 수 있습니다.

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

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

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

배열과 달리 좋아요 목록에서는 O(1) 공간과 O(1) 시간으로 중간에 항목을 삽입할 수 있으므로 병합 정렬의 병합 작업은 추가 공간 없이 구현할 수 있습니다.그러나 배열에 추가 공간을 할당하고 할당 취소하면 병합 정렬의 런타임에 부정적인 영향을 미칩니다.병합 정렬은 또한 많은 무작위 메모리 액세스 없이 데이터가 순차적으로 액세스되므로 연결 목록을 선호합니다.

반면에 빠른 정렬에는 많은 무작위 메모리 액세스가 필요하며 배열을 사용하면 연결 목록에서 요구하는 대로 순회하지 않고도 메모리에 직접 액세스할 수 있습니다.또한 배열에 사용될 때 빠른 정렬은 배열이 메모리에 연속적으로 저장되므로 참조 위치가 좋습니다.

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

편집하다:방금 병합 정렬 최악/최고/평균은 항상 nlogn이지만 빠른 정렬은 n2(요소가 이미 정렬된 최악의 경우)에서 nlogn(피벗이 항상 배열을 두 개로 나누는 경우의 평균/최상의 경우)까지 다양할 수 있다는 것을 알았습니다. .

시간과 공간 복잡도를 모두 고려하세요.병합 정렬의 경우:시간 복잡도 :o (nlogn), 공간 복잡성 :O(로그인)

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

이제 둘 다 각각 하나의 시나리오에서 승리합니다.그러나 무작위 피벗을 사용하면 거의 항상 Quick 정렬의 시간 복잡도를 O(nlogn)로 줄일 수 있습니다.

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

C/C ++ Land에서는 STL 컨테이너를 사용하지 않을 때 QuickSort를 사용하는 경향이 있습니다.

그래서 저는 많은 경우에 그것이 단순히 저항이 가장 적은 길이라고 믿습니다.

또한 전체 데이터 세트가 작업 세트에 맞지 않는 경우 빠른 정렬을 사용하면 성능이 훨씬 높아질 수 있습니다.

그 이유 중 하나는 더 철학적입니다.Quicksort는 Top->Down 철학입니다.정렬할 요소가 n개 있으면 n개입니다!가능성.상호 배타적인 m과 n-m의 2개 분할을 사용하면 가능성의 수가 몇 배로 줄어듭니다.중!* (n-m)!n보다 몇 차수 더 작습니다!홀로.5를 상상해 보세요!대 3!*2!.5!각각 2와 3으로 구성된 2개의 파티션보다 가능성이 10배 더 많습니다.100만 계승 대 900K!*100K로 추정합니다!대따라서 범위나 파티션 내에서 순서를 설정하는 것에 대해 걱정하는 대신 파티션의 더 넓은 수준에서 순서를 설정하고 파티션 내 가능성을 줄이세요.범위 내에서 이전에 설정된 순서는 파티션 자체가 상호 배타적이지 않으면 나중에 방해를 받습니다.

병합 정렬 또는 힙 정렬과 같은 상향식 순서 접근 방식은 미세한 수준에서 초기에 비교를 시작하는 작업자 또는 직원의 접근 방식과 같습니다.그러나 나중에 그 사이에 있는 요소가 발견되면 이 순서는 사라질 수밖에 없습니다.이러한 접근 방식은 매우 안정적이고 예측 가능성이 매우 높지만 일정량의 추가 작업을 수행합니다.

Quick Sort는 처음에는 어떤 순서에도 관심을 두지 않고 순서를 고려하지 않고 광범위한 기준을 충족하는 데만 관심을 갖는 관리적 접근 방식과 같습니다.그런 다음 정렬된 세트를 얻을 때까지 파티션이 좁아집니다.Quicksort의 실제 과제는 정렬할 요소에 대해 아무것도 모르는 상태에서 어둠 속에서 파티션이나 기준을 찾는 것입니다.그렇기 때문에 우리는 중앙값을 찾기 위해 약간의 노력을 기울이거나 무작위로 1을 선택하거나 임의의 "관리적" 접근 방식을 취해야 합니다.완벽한 중앙값을 찾으려면 상당한 노력이 필요할 수 있으며 다시 어리석은 상향식 접근 방식으로 이어집니다.따라서 Quicksort는 무작위 피벗을 선택하고 그것이 중간 어딘가에 있기를 바라거나 더 나은 중앙값을 찾기 위해 3, 5 또는 그 이상의 중앙값을 찾는 작업을 수행하지만 완벽할 계획은 없으며 낭비하지 않는다고 말합니다. 처음 주문할 때 언제든지.운이 좋으면 잘 되는 것 같으며 때로는 중앙값을 얻지 못하고 그냥 기회를 잡을 때 n^2로 저하되기도 합니다.어쨌든 데이터는 무작위입니다.오른쪽.따라서 나는 퀵 정렬의 상위->하향 논리적 접근 방식에 더 동의하며 이전에 저장한 피벗 선택 및 비교에 필요한 기회는 다음과 같은 세심하고 철저한 안정적인 하단->위 접근 방식보다 더 많은 시간 작동하는 것으로 나타났습니다. 병합 정렬.하지만

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow