программа быстрой сортировки с ошибкой сегментации

Question

Сегодня я прошел алгоритм быстрой сортировки из алгоритмов в C. Р. Седгивич.

Я понял хороший кусок того, как работает алгоритм. Кодирующая часть просто немного смутила меня, и в конце концов я получил ошибку сегментации. Вот код:

#include <stdio.h> 
void quicksort(int[], int, int); // prototype 

void quicksort(int a[], int l, int r) // What is the value of l. Why hasn't the author 
             // mentioned it. Is it the size of the array? 
{ 
    int i, j, v, t; 
    if(r > l) 
    { 
     v = a[r]; 
     i = l - 1; // What is l here? Is it the size if yes look at first while statement 
     j = r; 

     for(;;) 
     { 

      /*The algorithm says: scan from right until an element < a[r] is found. Where 
       r is the last position in the array. But while checking in the second while 
       loop elements > a[r] is searched */ 

      while (a[++i] < v); // How can you increment again after reaching end of arrray 
           // size if l is the size of the array 
      while (a[--j] > v); 
      if(i >= j) break; 
      t = a[i]; a[i] = a[j]; a[j] = t; 
     } 
    } 

    t = a[i]; a[i] = a[r]; a[r] = t; 

    quicksort(a, l, i - 1); 
    quicksort(a, i + 1, r); 

    return; 
} 

int main() 
{ 
    int i, a[10]; // assuming size is 10 

    for(i = 0; i < 10; i++) 
    { 
     scanf("%d", &a[i]); 
    } 

    int l = 10; // I am passing size of the array 
    int r = 9; // position of last element 

    quicksort(a, l, r); 
    return 0; 
} 

Ошибка такая. Предположим, если ввести 10 элементов, а затем нажмите клавишу ВВОД, это то, что происходит:

1 4 8 2 3 6 4 7 10 9 
segmentation fault. 

process returned 139(0x8b) 

Это то, что возвращается отладчик:

Breakpoint 1, quicksort (a=0xbffff808, l=0, r=0) at quick.c:11 
11  if(r > 1) 
(gdb) c 
Continuing. 

Program received signal SIGSEGV, Segmentation fault. 
0x080484fb in quicksort (a=0xbffff808, l=0, r=0) at quick.c:28 
28  t = a[i]; a[i] = a[r]; a[r] = t; 
(gdb) c 
Continuing. 

Program terminated with signal SIGSEGV, Segmentation fault. 
The program no longer exists. 
(gdb) c 
The program is not being run. 

Правильный способ сделать выше программы заключается в следующем. Нет ничего с левым и правым указателем. Левый указатель должен указывать на 0-е место и правый указатель на позицию n-1, если массив занимает n мест памяти. Я сделал глупую ошибку, не включая рекурсивную функцию quicksort внутри условия if. Отсюда и вся эта головная боль. Правильная программа:

/* Working quicksort 
* Robert sedgewick best 
*/ 

#include <stdio.h> 

void quicksort(int[], int, int); // prototype 

void quicksort(int a[], int l, int r) 
{ 
    int i, j, v, t; 
    if(r > l) 
    { 
     v = a[r]; 
     i = l - 1; 
     j = r; 

     for(;;) 
     { 
      while (a[++i] < v); 
      while (a[--j] > v); 

      if(i >= j) break; 
      t = a[i]; a[i] = a[j]; a[j] = t; 

     } // End for here 


    t = a[i]; a[i] = a[r]; a[r] = t; 

    quicksort(a, l, i - 1); 
    quicksort(a, i + 1, r); 

    } /* End if here. That is include the recursive 
     functions inside the if condition. Then it works 
     just fine. */ 

    return; 
} 

int main() 
{ 
    int i, a[5]; // assuming size is 10 

    for(i = 0; i < 5; i++) 
    { 
     scanf("%d", &a[i]); 
    } 

    int l = 0; // I am passing size of the array 
    int r = 4; // position of last element 

    quicksort(a, l, r); 

     int s; 

    for(s = 0; s < 5; s++) 
    { 
     printf("%d ", a[s]); 
    } 
    return 0; 
} 

Answer 1

Пожалуйста, запустите в отладчике, таком как gdb. Это покажет вам точную строку, на которой происходит segfault. Если вы google «gdb cheatsheet», вам будет легко начать работу. Не забудьте компилировать с -g флагом «

Моей сессией:

dan@dev1:~ $ gcc -g quick.c 
dan@dev1:~ $ gdb a.out 
... 
(gdb) r 
Starting program: /home/dan/a.out 
1 4 8 2 3 6 4 7 10 9 

Program received signal SIGSEGV, Segmentation fault. 
0x0000000000400572 in quicksort (a=0x7fffffffe530, l=10, r=9) at quick.c:21 
21    while (a[++i] < v); // How can you increment again after reaching end of arrray 

Answer 2

l и r стенд для "влево" и "вправо", соответственно.

Ошибка сегментации происходит потому, что вы проходите l = 10, поэтому while (a[++i] < v); перерывов.

[править]

while (a[++i] < v);         
while (a[--j] > v); 

Эти две петли также проблематичны: вы должны проверить, что i и j не выходит за границы.

Answer 3

int a[10]; 
int l = 10; 
int r = 9; 

quicksort(a, l, r); 

called quicksort(a, l, r) 
//l=10,r=9 
if(r > 1) // 9 > 1 is true 
{ 
    i = l - 1;//i = 10 - 1 = 9 
    for(;;) 
    { 
     while (a[++i] < v);//a[++i] is a[9+1] = a[10] is out of range!!