今日は、R.Sedgewick による Algorithms in 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 個の要素を入力して Enter キーを押すと、次のようになります。
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.
上記のプログラムを実行する正しい方法は次のとおりです。左右のポインターでは何もありません。配列が n メモリ ロケーションを占有する場合、左ポインタは 0 番目のロケーションを指し、右ポインタは n - 1 ロケーションをポイントする必要があります。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;
}