재귀 Quicksort가 스택 오버플로 예외를 throw합니다.

Question

Visual Studio를 사용하여 C#에서 재귀 빠른 방법을 작성했습니다. 이상하게 생각되는 것은, 정렬 될 숫자의 모음 인 입력이 배열에서 9500보다 낮 으면 최상, 최악 및 최다의 결과 모두에서 결과를 제공한다는 것입니다. 그러나 입력이 9500보다 클 경우 stackoverflow 예외가 발생합니다. 나는 현장에서 내 질문과 거의 같은 또 다른 질문이 있다는 것을 알고 있지만 재귀적인 조건을 만들었다.

---

public int[] quick(int [] myarray,int p,int r) 
    { 
     int q; 
     if (p < r) 
     { 
      q = partition(myarray, p, r); 
      quick(myarray, p, q - 1); 
      quick(myarray, q + 1, r); 
     } 
     return myarray; 
    } 
    public int partition(int [] myarray, int left, int right) 
    { 
     int i = left - 1; 
     int tmp = 0; 
     int pivot = myarray[right]; 
     for (int j = left; j < right; j++) 
     { 
      if (myarray[j] < pivot) 
      { 
       i = i + 1; 
       tmp = myarray[i]; 
       myarray[i] = myarray[j]; 
       myarray[j] = tmp; 
      } 
     } 
     tmp = myarray[i + 1]; 
     myarray[i + 1] = myarray[right]; 
     myarray[right] = tmp; 
     return i + 1; 

    } 

static void Main(string[] args) 
    { 
     Stopwatch mwatch = new Stopwatch(); 
     Program quickprogram = new Program(); 
     int[] mydizi = new int[9000]; 
     //int counter = 9000; 

     //initialization of quick array 
     for (int i = 0; i < mydizi.Length; i++) 
     { 
      mydizi[i] = i + 1; 

     } 

     int[] result = new int[9000]; //return array 
     //time is starting 
     mwatch.Start(); 
     //algorithm is called 
     result = quickprogram.quick(mydizi,0,mydizi.Length-1); 

     //result is returned from quickprogram 
     for (long j = 0; j < result.Length;j++) 
     { 
      Console.Write(result[j] + ","); 
     } 
     mwatch.Stop(); 
     //time is up 
     //Printing the time that show how it takes 
     Console.Write("Ms:" + mwatch.Elapsed.Milliseconds + " S:" + mwatch.Elapsed.Seconds + " Mn:" + mwatch.Elapsed.Minutes + " Hr:" + mwatch.Elapsed.Hours); 
     Console.ReadLine(); 
    } 

Answer 1

당신은 최악의 퀵을한다. 배열이 이미 정렬되어 있고 다시 정렬하려고합니다.

이

다음, 파티션() 코드가 참으로 이상한 같습니다

quick(0, 8) 
> quick(0, 7) 
>> quick(0, 6) 
>>> quick(0, 5) 
>>>> quick(0, 4) 
>>>>> quick(0, 3) 
>>>>>> quick(0, 2) 
>>>>>>> quick(0, 1) 
>>>>>>>> quick(0, 0) 
>>>>>>>> quick(2, 1) 
>>>>>>> quick(3, 2) 
>>>>>> quick(4, 3) 
>>>>> quick(5, 4) 
>>>> quick(6, 5) 
>>> quick(7, 6) 
>> quick(8, 7) 
> quick(9, 8) 

: 최종 결과에서

int i = left - 1;     // i = left-1 
int pivot = myarray[right]; 
for (int j = left; j < right; j++) // j = left 
{ 
    if (myarray[j] < pivot) 
    { 
     i = i + 1;     // now i = left-1+1 = left = j 
     tmp = myarray[i]; 
     myarray[i] = myarray[j]; 
     myarray[j] = tmp;   

     // congratulations! 
     // you successfully exchanged a value with itself! 
    } 

, 당신은 (배열 크기 = 9) 재귀 적으로이 인수) (빠른 호출

9000 개의 요소로이를 수행하면 9000 중첩 호출의 재귀 수준에 쉽게 도달 할 수 있습니다.