C++에서 빠른 정렬 구현 (실패에 대한 테스트)

Question

C++에서 Quicksort를 구현하도록 과제를 부여했으며 제대로 작동하는 코드를 작성했습니다. 실패에 대한 알고리즘을 테스트 할 때 백만 개의 요소가 포함 된 이진 파일에서 숫자를 정렬 할 때 충돌이 발생했습니다. 각 요소에 100 만 개의 파일이 두 개 있다는 점에 유의하십시오. 그 중 하나는 정렬되지 않은 것이고 다른 하나는 "거의 정렬 된"것이며, ​​알고리즘은 "거의 정렬 된"파일을 정렬 할 때만 실패하는 것처럼 보입니다. 내 코드는 다음과 같습니다.

int partition(int arr[], int low, int high) 
{ 
    int pivotI = low; //pivot index 
    int pivot = arr[pivotI]; 
    int temp = arr[low]; 
    arr[low] = pivot; 
    arr[pivotI] = temp; 
    int partitionI = low; 
    low++; 
    while (low <= high) 
    { 
     if (arr[low] >= pivot) 
     { 
      if (arr[high] <= pivot) 
      { 
       temp = arr[high]; 
       arr[high] = arr[low]; 
       arr[low] = temp; 
       low++; 
      } 
      high--; 
     } 
     else if (arr[high] <= pivot) 
     { 
      low++; 
     } 
     else 
     { 
      low++; 
      high--; 
     } 
    } 
    if (low == high) 
    { 
     if (arr[low - 1] < pivot) 
     { 
      temp = arr[low]; 
     } 
     else 
     { 
      temp = arr[low - 1]; 
     } 
    } 
    else 
    { 
     temp = arr[high]; 
    } 
    arr[high] = arr[partitionI]; 
    arr[partitionI] = temp; 
    return high; 
} 

void quickSort(int arr[], int left, int right) 
{ 
    if (left < right) 
    { 
     int p = partition(arr, left, right); 
     quickSort(arr, left, p); 
     quickSort(arr, p + 1, right); 
    } 
} 

* "거의 정렬 된"이진 파일을 실행할 때 스택 오버플로 오류가 발생합니다. 왜 이런 일이 일어나는 지 아십니까? 감사합니다

Answer 1

피벗 값이 항상 파티션에서 가장 낮은 값이되기 때문에 quicksort에서 피벗 값의 첫 번째 값을 사용하는 경우 이미 정렬 된 목록이 나쁜 경우입니다. 이것은 재귀 깊이를 크게 증가시킬 수 있습니다. 각 재귀 호출에는 스택 프레임에 공간이 필요합니다 (매개 변수, 지역 변수 및 복귀 주소로 구성됨). 거의 정렬 된 백만 개의 숫자 목록을 보려면 한 번에 백만 개의 스택 프레임을 활성화해야합니다. 사용 가능한 스택 공간을 쉽게 소모하여 오류를 생성 할 수 있습니다.

다른 피벗 알고리즘을 사용하여 중간 값 3과 같이이를 해결할 수 있습니다.

Answer 2

스택 오버플로를 방지하는 방법 중 하나는 루프와 재귀의 조합을 사용하는 것입니다. 각 파티션() 후에 quicksort()에서 (p - 왼쪽) < = (right - p - 1)을 확인하고 더 작은 부분에 대해서만 재귀를 사용한 다음 큰 부분을 분리하기 위해 루프백합니다. 이것은 최악의 스택 오버 헤드를 log2 (n)로 제한합니다. 최악의 경우에 대한 시간 복잡성은 O (n^2)에 남아 있습니다.

복잡도가 O로 줄일 수 최악의 시간은 중간 값의 중간 값을 사용하여 (N) N (로그)

http://en.wikipedia.org/wiki/Median_of_medians

했으나 일정한 계수 인자는 평균 최고 대한 퀵 느려지고 크다 사례.