programme quicksort avec défaut de segmentation

Question

Aujourd'hui, je passais par l'algorithme de tri rapide de Algorithms in C par R.Sedgewick.

J'ai compris une bonne partie du fonctionnement de l'algorithme. La partie codage m'a un peu perturbé et j'ai eu une erreur de segmentation à la fin. Voici le code:

#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; 
} 

L'erreur est comme ceci. Supposons que si j'entre 10 éléments, puis appuyez sur Entrée, voici ce qui se passe:

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

process returned 139(0x8b) 

C'est ce débogueur retourné:

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. 

La bonne façon de faire le programme ci-dessus est la suivante. Il n'y a rien avec le pointeur gauche et droit. Le pointeur gauche doit pointer vers la 0e position et le pointeur droit vers l'emplacement n-1, si le tableau occupe n emplacements de mémoire. J'avais fait une erreur stupide en n'incluant pas la fonction récursive de quicksort à l'intérieur de la condition if. D'où tout ce mal de tête. Le programme est correct:

/* 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

Veuillez exécuter dans un débogueur tel que gdb. Cela vous montrera la ligne exacte sur laquelle votre segfault se passe. Si vous google "gdb cheatsheet" il sera assez facile de commencer. Rappelez-vous de compiler avec -g flag «

Ma session:

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 et r position pour "gauche" et "droite", respectivement.

L'erreur de segmentation se produit parce que vous passez l = 10, donc while (a[++i] < v); casse.

[modifier]

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

Ces deux boucles sont également problématiques: vous devez vérifier que i et j ne sont pas en dehors des limites.

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!!