퀵 소트가 실제로 사용되는 이유는 무엇입니까?

Question

퀵소트는 최악의 경우 성능이 O (n)이지만 실제로는 실제로 널리 사용됩니다. 왜 이런거야?

Answer 1

평균적으로 (경과 시간 기준으로) 가장 빠른 비교 정렬이기 때문입니다.

Answer 2

일반적으로 가장 빠른 정렬 알고리즘 중 하나이기 때문에.

Answer 3

QuickSort의 평균 점근 순서는 O(nlogn)이며 더 작은 상수 (더 엄격한 루프)로 인해 일반적으로 힙보다 효율적입니다. 실제로 이론적 인 선형 시간 중간 선택 알고리즘이 있으므로 최상의 피벗을 항상 찾을 수 있으므로 최악의 경우가 발생합니다 O(nlogn). 그러나 일반적인 QuickSort는 일반적으로이 이론적 인 QuickSort보다 빠릅니다.

, 그것은 분별하게 이것은 QuickSort가 O(n 2 )에 완료 할 가능성을 고려해야합니다. 단지 1/n! 일 뿐이므로 거의 악의적 인 사례가 발생하지 않습니다.

Answer 4

최악의 경우에만 집중해야하며 시간 복잡성에만 집중해야합니다. 최악의 경우보다 평균치가 더 많으며 시간은 이고 시간입니다.

퀵 :

• 는 Θ (N 로그 N)의 평균 시간 복잡도를 갖는다;
• 은 Θ의 공간 복잡도 (log n)로 구현 될 수 있습니다.

또한 큰 O 표기법은 어떤 상수를 고려하지 않지만 알고리즘이 몇 배 빠르면 실제로 차이를 만듭니다. Θ (N 로그 N)는 그 알고리즘 K는 상수 K   N   로그 ( N)에서 실행되는 것을 의미한다. Quicksort는 가장 낮은 K 인 비교 정렬 알고리즘입니다.

Answer 5

C는 라이브러리 기능이 qsort()이지만 실제로 컴파일러 공급 업체가 제공하는 실제 QuickSort를 사용하여 구현할 필요는 없습니다.

Answer 6

가장 빠른 것 외에도 배열을 정렬하기 전에 배열을 뒤섞어서 나쁜 시나리오를 피할 수 있습니다. 작은 데이터 세트의 약점은 데이터 세트가 작고 정렬 시간이 아무리 작아도 분명히 큰 문제는 아닙니다.

예를 들어, QuickSort 및 버블 정렬을위한 파이썬 함수를 작성했습니다. 버블 정렬은 10,000 레코드를 정렬하는 데 20 초, 7500으로 11 초, 5000으로 5 초가 소요됩니다. 퀵 소트는 이러한 모든 종류의 작업을 약 0.15 초 내에 수행합니다!

Answer 7

흥미롭게도 quicksort는 평균보다 더 많은 비교를 수행합니다 - quicksort는 1.44 ng (예상), mergesort는 ngn입니다.모든 것이 중요하다면, mergesort가 quicksort보다 강력 할 것입니다.

quicksort가 빠르다는 이유는 현대 하드웨어에서 매우 잘 작동하는 많은 다른 바람직한 특성을 가지고 있기 때문입니다. 예를 들어, quicksort는 동적 할당이 필요 없습니다. 재귀에 필요한 스택 프레임을 저장하기 위해 O (log n) 스택 공간 (올바르게 구현 된 경우 최악의 경우)을 사용하여 원래 배열에서 제자리에서 작동 할 수 있습니다. mergesort가이를 수행 할 수는 있지만 일반적으로 병합 단계에서 큰 성능 저하가 발생합니다. heaport와 같은 다른 정렬 알고리즘에도이 속성이 있습니다.

또한 quicksort는 참조 할 수있는 지역이 뛰어납니다. Hoare의 in-place 파티셔닝 알고리즘을 사용하여 파티셔닝 단계를 수행하는 경우 본질적으로 어레이 양 끝에서 안쪽으로 수행되는 두 개의 선형 스캔입니다. 즉, quicksort에는 매우 적은 수의 캐시 누락이있을 수 있습니다. 이는 최신 아키텍처에서 성능에 결정적인 요소입니다. 반면에 Heaport는 매우 좋은 지역을 가지고 있지는 않습니다. 대부분의 mergesort 구현은 합리적으로 지역적입니다.

퀵 포트도 매우 병렬 처리가 가능합니다. 어레이를 더 작은 영역과 더 큰 영역으로 나눌 수있는 초기 파티셔닝 단계가 발생하면이 두 부분을 서로 독립적으로 정렬 할 수 있습니다. mergesort를 포함하여 많은 정렬 알고리즘을 병렬 처리 할 수 ​​있지만 병렬 퀵 정렬의 성능은 위의 이유로 다른 병렬 알고리즘보다 나은 경향이 있습니다. 반면 Heaport는 그렇지 않습니다.

quicksort의 유일한 문제점은 O (n)로 저하 될 가능성이 있다는 것입니다. 큰 데이터 세트의 경우 매우 심각 할 수 있습니다. 이를 방지하는 한 가지 방법은 알고리즘을 자체적으로 인트로 스펙 션 (introspect)하고 퇴화하는 경우 더 느리지 만 더 신뢰할 수있는 알고리즘 중 하나로 전환하는 것입니다. introsort이라고하는이 알고리즘은 병리학 적 사례없이 퀵 소트의 많은 이점을 얻는 훌륭한 하이브리드 정렬 알고리즘입니다. 요약

:

• 퀵이 제자리 O 공간 (로그 n)를 취 재귀에서 사용한 스택 프레임을 제외하고있다.
• 퀵소트 (Quicksort)는 훌륭한 참조 지역입니다.
• 퀵 포트는 쉽게 병렬 처리됩니다.

왜 quicksort가 종이에서 더 좋을지 정렬 알고리즘을 능가하는 경향이 있는지를 설명합니다.

희망이 도움이됩니다.

Answer 8

Bcs 이것은 O (NlogN) 복잡성이있는 큰 데이터 세트에서 잘 작동하는 알고리즘 중 하나입니다. 이것은 일정한 공간을 차지하는 제자리 알고리즘입니다. 피벗 요소를 현명하게 선택하면 빠른 정렬의 경우를 피할 수 있으며 정렬 된 배열에서도 항상 O (NlogN)에서 수행됩니다.