그걸로 정렬 - Quicksort

Question

우리는 자신의 Comparable 기본 클래스에 최적화 된 quicksort를 만들어야합니다. 나에게있어서 나는 그것을 작동시킬 수 없다. 알고리즘은 간단하지만 앞으로는 코드를 작동시키지 못합니다. 나는 Comparable를 확장하는 DateTime 클래스를 가지고 있는데, 테스트 할 때 정렬은 작동하는 것처럼 보이지만 매 20 분의 1은 하나의 값만 실행됩니다. 그리고 더 적은 배열의 덩어리에 삽입 정렬을 사용할 때 하나의 값이 실행됩니다. 8보다 전체 정렬은 헛소리에서 던져집니다.

내 파티션 방법에서는 피벗을 끝까지 움직이고 시작과 끝에서 포인터를 시작할 때 작동합니다. 1. 처음과 마지막이 이미 정렬되어 있으므로 피벗을 끝으로 이동하고 싶습니다. 처음에 포인터를 시작하고 1과 2를 끝내지 만 시도하면 모든 것이 무너져 버리고 나는 왜 그런지 이해하지 못합니다.

그래서 지금 뭔가 효과가 있습니다. 그것은 성가신 작은 아랫 배열에 삽입 정렬을 사용하지 않을 때 약간의 경련을 일으 킵니다. 배열에서 떨어지는 것에 대해 지적한 Ben j에게 감사드립니다. 삽입 정렬 문제가 발생했습니다. :)

내 현재 코드는 당신이 우리와 내 유일한 추측이 from 및 to 당신이 무슨 생각을 의미하지 않는다는 것입니다 무엇이 잘못되었는지에 대한 의견을 표시 한 코드에서

Comparable** partition(Comparable** from, Comparable** to) 
{ 
    Comparable** pivot = from + (to - from)/2; 
    SortFirstMiddleLast(from, pivot, to - 1); 
    swap(*pivot, *to); 
    pivot = to; 
    ++from; to -= 2; 
    while (from <= to) 
    { 
     while (**from <= **pivot && from <= to) ++from; 
     while (**to >= **pivot && from <= to) --to; 
     if (from < to) 
     { 
      swap(*from, *to); 
      ++from; --to; 
     } 
    } 
    swap(*from, *pivot); 
    return from; 
} 

Answer 1

이하입니다. 정렬 할 세그먼트의 길이는 to - from입니다. 정확한 것이고 피벗 선택에 대한 근사치가 아니라면 to은 실제로 영역을 넘어서 정렬 할 수있는 요소를 가리키고 있음을 의미합니다. 그것은 합리적이지만, swap<Comparable*>(*pivot, *(to))은리스트의 끝에서 피벗을 교환 할 것입니다.