인터뷰 중에이 질문을 받았습니다. 그들은 O (nlogn)이며 대부분의 사람들은 Mergesort 대신 Quicksort를 사용합니다. 왜 그런 겁니까?
답변
Quicksort는 O ( n 2 ) 최악의 런타임과 O ( n log n ) 평균 케이스 런타임을 갖습니다 . 그러나 많은 요인들이 알고리즘의 런타임에 영향을 미치기 때문에 많은 시나리오에서 병합 정렬이 우수합니다.
특히, 자주 인용되는 정렬 알고리즘 런타임은 데이터를 정렬하는 데 필요한 비교 횟수 또는 스왑 수를 나타냅니다. 이는 기본 하드웨어 설계와 무관하기 때문에 실제로 성능을 측정하는 좋은 방법입니다. 그러나 참조의 지역 성과 같은 다른 것 (즉, 캐시에있는 많은 요소를 읽습니까?)도 현재 하드웨어에서 중요한 역할을합니다. 특히 Quicksort는 추가 공간이 거의 필요하지 않으며 캐시 지역성이 우수하므로 많은 경우 병합 정렬보다 빠릅니다.
또한 피벗을 임의로 선택하는 등의 적절한 피벗을 선택하여 퀵소트의 최악의 경우 O ( n 2 ) 의 런타임을 거의 피할 수 있습니다 (이 방법은 탁월한 전략입니다).
실제로, 많은 현대식 quicksort 구현 (특히 libstdc ++ ‘s std::sort)은 실제로 introsort 이며 이론상 최악의 경우는 O ( n log n )이며 병합 정렬과 동일합니다. 재귀 수준을 제한하고 log n을 초과하면 다른 알고리즘 ( heapsort )으로 전환하여이를 달성합니다 .
답변
많은 사람들이 언급했듯이 퀵 정렬의 평균 사례 성능은 병합 정렬보다 빠릅니다. 그러나 요청시 메모리에 액세스하는 데 일정한 시간이 있다고 가정하는 경우에만 해당됩니다.
RAM에서이 가정은 일반적으로 그렇게 나쁘지는 않습니다 (캐시 때문에 항상 사실은 아니지만 너무 나쁘지는 않습니다). 데이터 구조가 디스크에 사는 큰만큼이 그러나 경우, 다음 퀵됩니다 살해 (200)는 임의 초당 추구와 같은 평균 디스크가 무언가를한다는 사실. 그러나 동일한 디스크는 초당 메가 바이트의 데이터를 읽거나 쓰는 데 문제가 없습니다. 어떤 것이 mergesort가하는 것입니다.
따라서 데이터를 디스크에서 정렬해야하는 경우 실제로 mergesort에서 일부 변형을 사용하려고합니다. 일반적으로 하위 목록을 퀵 정렬하여 일부 크기 임계 값 이상으로 병합하기 시작합니다.
또한 해당 크기의 데이터 세트로 무엇이든 해야하는 경우 디스크를 찾지 않는 방법에 대해 열심히 생각하십시오. 예를 들어 데이터베이스에 큰 데이터로드를 수행하기 전에 인덱스를 삭제 한 다음 나중에 인덱스를 다시 작성하는 것이 표준 조언입니다. 로드 중에 인덱스를 유지 관리한다는 것은 지속적으로 디스크를 찾는 것을 의미합니다. 반대로 인덱스를 삭제하면 데이터베이스는 먼저 처리 할 정보를 병합 (물론 병합을 사용하여) 정렬 한 다음 인덱스의 BTREE 데이터 구조에로드하여 인덱스를 다시 작성할 수 있습니다. BTREE는 자연스럽게 순서대로 유지되므로 디스크를 거의 찾지 않고도 정렬 된 데이터 세트에서 하나를로드 할 수 있습니다.
디스크 검색을 피하는 방법을 이해하면 데이터 처리 작업을 며칠 또는 몇 주가 아닌 몇 시간이 걸리는 경우가 많이있었습니다.
답변
실제로 QuickSort는 O (n 2 )입니다. 그 평균의 경우 실행 시간은 O (nlog (n)이)입니다,하지만 최악의 경우 O (n은 2 당신은 몇 가지 고유 항목이 포함 된 목록에서 실행할 때 발생). 무작위 화에는 O (n)이 필요합니다. 물론 이것은 최악의 경우를 변경하지 않으며 악의적 인 사용자가 오랜 시간이 걸리는 것을 방지합니다.
QuickSort는 다음과 같은 이유로 더 인기가 있습니다.
- 제자리에 있습니다 (MergeSort는 정렬 할 요소 수에 따라 추가 메모리가 필요합니다).
- 작은 숨겨진 상수가 있습니다.
답변
“그러나 대부분의 사람들은 Mergesort 대신 Quicksort를 사용합니다. 왜 그런가요?”
주어지지 않은 심리적 이유 중 하나는 단순히 Quicksort의 이름이 더 영리하다는 것입니다. 즉 좋은 마케팅.
그렇습니다. 트리플 파티셔닝 기능이있는 Quicksort는 아마도 가장 일반적인 범용 정렬 알고리즘 중 하나 일 것입니다. 그러나 “Quick”정렬이 “Merge”정렬보다 훨씬 강력하다는 사실은 극복 할 수 없습니다.
답변
다른 사람들이 지적했듯이 Quicksort의 최악의 경우는 O (n ^ 2)이며 mergesort 및 heapsort는 O (nlogn)에 있습니다. 그러나 평균적으로 세 가지 모두 O (nlogn)입니다. 그것들은 대부분의 경우에 필적합니다.
Quicksort의 평균 성능을 향상시키는 것은 내부 루프가 여러 값을 단일 값과 비교하는 것을 의미하지만 다른 두 값은 각 비교마다 다릅니다. 다시 말해, Quicksort는 다른 두 알고리즘보다 절반의 읽기를 수행합니다. 최신 CPU에서는 성능이 액세스 시간에 의해 크게 좌우되므로 결국 Quicksort가 가장 우선적으로 선택됩니다.
답변
지금까지 언급 한 세 가지 알고리즘 (mergesort, quicksort 및 heap sort) 중 하나를 추가하고 싶습니다. mergesort 만 안정적입니다. 즉, 동일한 키를 가진 값에 대해서는 순서가 변경되지 않습니다. 어떤 경우에는 이것이 바람직합니다.
그러나 실제 상황에서 대부분의 사람들은 좋은 평균 성능 만 필요로하며 퀵 정렬은 빠릅니다 … 빠른 =)
모든 정렬 알고리즘에는 기복이 있습니다. 좋은 개요 는 정렬 알고리즘에 대한 Wikipedia 기사를 참조하십시오 .
답변
에서 퀵에 위키 백과 항목 :
Quicksort는 또 다른 재귀 정렬 알고리즘 인 mergesort와 경쟁하지만 최악의 경우 Θ (nlogn) 실행 시간이라는 이점이 있습니다. Mergesort는 quicksort 및 heapsort와 달리 안정적인 정렬 방식이며, 연결된 스토리지 목록 및 디스크 스토리지 또는 네트워크 연결 스토리지와 같은 액세스가 느린 미디어에 저장된 매우 큰리스트에서 쉽게 작동하도록 조정할 수 있습니다. 퀵 정렬은 링크 된 목록에서 작동하도록 작성 될 수 있지만 랜덤 액세스 없이는 피벗을 잘못 선택하는 경우가 종종 있습니다. mergesort의 주요 단점은 배열에서 작업 할 때 최상의 경우 Θ (n) 보조 공간이 필요한 반면, 내부 분할 및 꼬리 재귀가있는 quicksort의 변형은 Θ (logn) 공간 만 사용한다는 것입니다. 연결된 목록에서 작업 할 때 mergesort는 작고 일정한 양의 보조 저장소 만 필요합니다.
