8

このクイックソートは、「v[左]...v[右] を昇順で」ソートすることになっています。K&R の C プログラミング言語 (第 2 版) からコピー (コメントなし):

void qsort(int v[], int left, int right)
{
    int i, last;
    void swap(int v[], int i, int j);

    if (left >= right)
        return;
    swap(v, left, (left + right) / 2);
    last = left;
    for (i = left+1; i <= right; i++)
        if (v[i] < v[left])
            swap(v, ++last, i);
    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

にバグがあると思います

(left + right) / 2

左 = INT_MAX - 1、右 = INT_MAX とします。これにより、整数オーバーフローが原因で未定義の動作が発生することはありませんか?

4

4 に答える 4

7

はい、あなたが正しい。left - (left - right) / 2オーバーフローを回避するために使用できます。

于 2011-06-26T21:47:57.400 に答える
2

INT_MAX要素数の配列を想像していませんか?

于 2011-06-26T21:47:59.147 に答える
1

はい、その通りです。簡単にするためにそのように記述されている可能性がありますが、これはあくまでも例であり、製品コードではありません。

于 2011-06-26T21:49:58.973 に答える
1

K&R は、符号なしと符号付きの引数の使用に関して、常に少しずさんでした。メモリが 16 キロバイトしかない PDP を使用した場合の副作用だと思います。それは少し前に修正されました。qsort の現在の定義は

void qsort(
   void *base,
   size_t num,
   size_t width,
   int (__cdecl *compare )(const void *, const void *) 
);

int の代わりに size_t を使用していることに注意してください。そしてもちろん、ソートしているタイプの種類がわからないため、 void* base です。

于 2011-06-26T22:30:19.343 に答える