빠른 정렬 반복기 요구 사항

Question

tl; dr : 이중 연결 목록에서 quicksort를 효율적으로 구현할 수 있습니까? 그것에 대해 생각하기 전에 나의 이해는 아니었다.

요 전날은 기본 정렬 알고리즘에 대한 반복기 요구 사항을 고려할 기회가있었습니다. 기본적인 O (N²) 것들은 상당히 간단합니다.

• 버블 정렬 - 2 개의 순방향 반복자는 다른 하나를 드래그하면서 멋지게 수행합니다.
• 삽입 정렬 - 2 개의 양방향 반복자가 수행합니다. 하나는 순서가 잘못된 요소이고 하나는 삽입 포인터입니다.
• 선택 정렬 - 좀 더 까다 롭지만 앞으로 반복자가 트릭을 수행 할 수 있습니다.

은 퀵는

표준 : 종류의 introsort_loop (는 GNU 표준 라이브러리/마력 (1994)에서와 같이/실리콘 그래픽 (1996)) random_access 수를 필요로한다.

__introsort_loop(_RandomAccessIterator __first, 
     _RandomAccessIterator __last, 
     _Size __depth_limit, _Compare __comp) 

예상대로.

이제 더 자세히 살펴보면 quicksort에 이것을 요구하는 실제 이유를 찾을 수 없습니다. 명시 적으로 random_access_iterator가 필요한 유일한 것은 std::__median 호출이며 중간 요소를 계산해야합니다. 일반 바닐라 퀵 소트 은 중간 값을 계산하지 않습니다.

파티셔닝은 체크

if (!(__first < __last)) 
    return __first; 

정말

하지 bidirectionalS를위한 유용한 검사로 구성되어 있습니다. 그러나 하나

if (__first == __last) this_partitioning_is_done = true; 

의 간단한 조건 (오른쪽 왼쪽/왼쪽에서 오른쪽으로) 이전 파티션 여행 수표와 이것을 대체 할 수 있어야하는 것이 가능에만 양방향 반복자를 사용하여 매우 효율적으로 퀵을 구현하는 것입니다 ? 재귀 깊이는 여전히 지켜 질 수 있습니다.

NB. 나는 아직 실제 구현을 시도하지 않았다.

Answer 1

TL; DR : 예 당신은 문제가 랜덤 액세스와 함께이 문제를 발견, 중간에 요소 피벗 요소를 찾을 수 있습니다 말하는 것처럼

는 그것을 발견, (1) O 소요 양방향 반복자는 O (n) (정확한 n/2 연산)을 필요로합니다. 그러나 각 단계에서 하위 컨테이너로 만들고, 왼쪽과 오른쪽에는 더 작은 수와 큰 수를 각각 포함시켜야합니다. 이것은 빠른 정렬의 주요 작업이 이루어지는 곳입니다.

이제 (재귀 단계의) 하위 컨테이너를 만들 때 내 접근법은 각각의 앞 요소를 가리키는 반복자 h을 만드는 것입니다.이제 하위 컨테이너로 이동할 다음 요소를 선택할 때마다 간단하게 h을 미리 전달하십시오. 새 재귀 단계로 내려갈 준비가되면 h은 피벗 요소를 가리 킵니다.

O (n log n + n/2) = O (n log n)이므로 실제로 중요하지 않은 첫 번째 피벗을 찾아야합니다.

실제로 이것은 런타임 최적화에 불과하지만 목록에 대해 한 번 반복 (각 하위 컨테이너에 각 값 넣기) 또는 두 번 반복 (피벗을 찾은 다음 각 O (2n) = O (n)이다.
이것은 단순히 실행 시간 (복잡하지 않음)의 문제입니다.

Answer 2

일반적으로 목록의 중간에서 피벗 요소를 선택하려는 경우 임의 액세스 반복기가 필요합니다. 첫 번째 또는 마지막 요소를 대신 피벗으로 선택하면 양방향 반복기로 충분하지만 미리 정렬 된 목록의 경우 Quicksort가 O (n^2)로 변합니다.

Answer 3

이중 연결 목록에 빠른 정렬 전략을 구현하는 데 전혀 문제가 없습니다. (단일 링크 된 목록에도 쉽게 적용될 수 있다고 생각합니다.) 랜덤 액세스 요구 사항에 따라 달라지는 전통적인 빠른 정렬 알고리즘의 유일한 위치는 피벗 요소를 선택하기 위해 "까다로운"무언가를 사용하는 설치 단계입니다. 현실적으로이 모든 "속임수"는 거의 똑같이 효과적인 순차적 방법으로 대체 될 수있는 단순한 경험적 방법 일뿐입니다.

이전에 연결된 목록에 대한 빠른 정렬을 구현했습니다. 그것에 관해 특별한 것은 없으며 재 연결되는 적절한 요소에 세심한주의를 기울일 필요가 있습니다. 이해할 수 있듯이 목록 정렬 알고리즘의 상당 부분은 명시 적 값 교환 대신 을 다시 연결하여 요소를 재정렬 할 수 있다는 사실에서 비롯됩니다. 더 빨라질뿐만 아니라 목록의 요소에 첨부 될 수있는 외부 참조의 가치 유효성을 보존합니다.

P. 그러나 링크드 목록의 경우 merge-sort 알고리즘을 사용하면 훨씬 더 우아한 구현이 가능하며 성능은 똑같습니다 (빠른 정렬을 사용하면 더 나은 성능을 보이는 경우는 제외).