Ошибка в примере быстрой сортировки (книга K & R C)?

Question

Эта быстрая сортировка должна сортировать «v [left] ... v [right] в порядке возрастания»;скопировано (без комментариев) из языка программирования C от K & R (второе издание):

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.Не приведет ли это к неопределенному поведению из-за целочисленного переполнения?

Answer 1

Да, вы правы.Вы можете использовать left - (left - right) / 2, чтобы избежать переполнения.

Answer 2

Вы не представляете себе массив с INT_MAX количеством элементов?

Answer 3

K & R всегда был немного неаккуратен в использовании неподписанных и подписанных аргументов. Полагаю, побочный эффект от работы с PDP, у которого было только 16 килобайт памяти. Это было исправлено некоторое время назад. Текущее определение qsort:

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

Обратите внимание на использование size_t вместо int. И, конечно, void * base, так как вы не знаете, какой тип вы сортируете.

Answer 4

Да, вы правы, хотя, возможно, это просто написано для простоты - в конце концов, это пример, а не рабочий код.