이미 정렬 된 데이터에서 내 quicksort가 충돌합니다.

Question

배열에서 다른 데이터의 성능 시간을 확인하고 싶습니다. (임의, 이미 정렬, 내림차순으로 정렬). 여기

void Quicksort(int *T, int Lo, int Hi) 
{ 
    if (Lo<Hi){ 
     int x=T[Lo]; 
     int i=Lo, j=Hi; 
    do 
    { 
     while (T[i] < x) ++i; 
     while (T[j] > x) --j; 
     if (i<=j) 
     { 
     int tmp = T[i]; 
     T[i] = T[j]; 
     T[j] = tmp; 
     ++i; --j; 
     } 
    } while(i < j); 
    if (Lo < j) Quicksort(T, Lo, j); 
    if (Hi > i) Quicksort(T, i, Hi); 
    } 
} 

생성하고 테스트 배열을 작성하는 데 사용되는 기능은 다음과 같습니다

int* createArr(int length){ 
    int* Arr= new int[length]; 
    return Arr; 
    } 

void Random(int *A, int length){ 
     for (int i=0;i<length;i++){ 
     A[i]=rand(); 
    } 
} 
void Order(int *A, int length){ 
     for (int i=0;i<length;i++){ 
     A[i]=i; 
    } 
} 

void Backwards(int *A, int length){ 
     for (int i=0;i<length;i++){ 
     A[i]=length-i; 
    } 
} 

그것은 임의의 숫자에 대해 잘 작동을하지만, 내가하려고 할 때 오름차순으로 그것을 채우기 및 종류, 그와 충돌 할 스택 오버플로. 아무도 저에게 왜 그런 일이 일어날 지에 대한 힌트를 줄 수 있습니까?

Answer 1

[Lo] 항목을 분할 값 (피벗)으로 선택하고 배열이 이미 정렬 된 경우 1부터 (length-1)까지의 분할을 얻습니다. 이로 인해 배열의 더 긴 부분에있는 다음 (재귀 적) 호출은 이전 레벨보다 적은 항목 하나만 처리합니다. @AlexanderM이 지적했듯이 배열의 길이만큼 재귀를 깊숙이 들여다 볼 수 있습니다. 배열이 큰 경우 스택 오버플로가 발생할 가능성이 큽니다.

꼬리 부분 재귀를 사용하십시오. 어느 부분이 더 짧은 지 확인하고 재귀 호출로 정렬 한 다음, 더 긴 부분으로 현재 수준에서 계속하십시오. 그 while와 if 가장 먼저 교체하고이 프로그램 빨리하지 않습니다

if (Lo < j) Quicksort(T, Lo, j); 
if (Hi > i) Quicksort(T, i, Hi); 

if (j-Lo < Hi-i) 
{ 
    Quicksort(T, Lo, j); 
    Lo = i; 
} 
else 
{ 
    Quicksort(T, i, Hi); 
    Hi = j; 
} 

로 교체하려면 - 여전히 온 O (N^2) 시간이 필요합니다 이미 정렬 된 배열이지만 선형 스택 메모리 사용을 막아 최악의 O (log n)로 유지합니다.

더 나은 성능과 관련된 자세한 지침은 위키 피 디아 문서 Quicksort, 부품 선택의 범위을 참조하십시오.