a.exe прекратил работу с быстрой программой quicksort

Question

Я написал следующую реализацию алгоритма быстрой сортировки. Я не могу догадаться, почему следующий фрагмент кода не работает (хорошо компилируется, но не может работать во время выполнения. A.exe перестает работать) .Я буду рад, если кто-нибудь из вас может помочь мне в этой связи:

main() 
{ 
    int a[ ]={9,2,3,1,6,5,6,3,2,9,8,1,4,5,5,6,5,99}; 
    quicksort(a,0,17); 
    print(a,18);  

}

void print(int a[ ],int n) 
{ 
int i; 
for (i=0;i<n;i++) 
     printf("%d\n",a[i]); 
} 

    void swap(int a[ ],int left,int right) 
     { 
     int t; 
     t=a[left]; 
      a[left]=a[right]; 
      a[right]=t; 
    } 

    void quicksort(int a[ ],int left,int right) 
    { 
    int i,last; 
     if (left >= right) 
      return; 
    swap(a,left,(last+right)/2); 
     last=left; 
     for (i=last+1;i<=right;i++) 
      if (a[i] < a[left]) 
       swap(a,++last,i); 
     swap(a,left,last); 
     quicksort(a,left,last-1); 
     quicksort(a,last+1,right); 

}

Answer 1

Проблема здесь:

void quicksort(int a[ ],int left,int right) 
{ 
    int i,last; 
    if (left >= right) 
     return; 
    swap(a,left,(last+right)/2); 
       ^^^^ 

last не инициализирован, и все же вы используете его в качестве дополнения к right.

Возможно, вы имели в виду (left+right)/2?

Не только мой компилятор предупредил меня (всегда включайте предупреждения), но я также использовал отладчик, чтобы дважды проверить, что это действительно так.

Предупреждение компилятора:

23:22: warning: ‘last’ may be used uninitialized in this function [-Wuninitialized]

Выходной отладчик:

Breakpoint 2, main() at quicksortbroken.c:37 
37  int a[ ]={9,2,3,1,6,5,6,3,2,9,8,1,4,5,5,6,5,99}; 
(gdb) n // go to the next line 
38  quicksort(a, 0, 17); 
(gdb) s // step into the function 
quicksort (a=0xbffff6d8, left=0, right=17) at quicksortbroken.c:21 
21  if (left >= right) 
(gdb) n 
23  swap(a,left,(last+right)/2); // okay, let's examine the variable I suspect is problematic 
(gdb) p last // print the value of last 
$1 = 1872329 // Oh, oh, definitely not supposed to be this value 

Это использует GDB под Linux, не знаю, как вы компиляции кода, но я уверен, что Cygwin поставляется с портом Windows GDB, у Microsoft также есть собственный отладчик. Никаких оправданий не использовать.

Answer 2

Возможно, ваш отсутствует предупреждение как ‘last’ may be used uninitialized in this function

Первое использование last без его инициализации создает ошибку сегментации, чтобы ваш ехе не работает, как ожидалось.

Answer 3

В этом фрагменте есть две проблемы. Одним из основных правил кодирования является то, что каждая переменная должна быть инициализирована значением или может произойти, что ваша переменная может принимать значение мусора и давать неожиданный результат. Во-вторых, в вашем алгоритме есть проблема. В функции quicksort, где вы вызываете функцию свопинга, должны быть указаны правильные параметры: «swap (a, left, (left + right)/2);

P.S. - Предоставляйте прототипы функций также, если работа над проектом иначе игнорирует это.