Błąd w przykładzie quicksort (książka K & R C)?

Question

Ten quicksort ma sortować "v [left] ... v [right] do porządku rosnącego"; kopiowane (bez uwag) od C Programming Language przez K & R (Second Edition):

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

myślę, że jest to błąd w

(left + right)/2 

Załóżmy lewo = INT_MAX - 1 i prawo = INT_MAX. Czy nie spowoduje to niezdefiniowanego zachowania z powodu przekroczenia liczby całkowitej?

Answer 1

Tak, masz rację. Możesz użyć numeru left - (left - right)/2, aby uniknąć przepełnienia.

Answer 2

Nie wyobrażasz sobie tablicy z INT_MAX liczbą elementów, prawda?

Answer 3

Tak, masz rację, chociaż jest to prawdopodobnie napisane tak dla uproszczenia - to przecież przykład, a nie kod produkcyjny.

Answer 4

K & R zawsze było trochę zaniedbane z użyciem argumentów unsigned vs signed. Efekt uboczny pracy z PDP, który przypuszczalnie ma tylko 16 kilobajtów pamięci. To zostało naprawione jakiś czas temu. Obecna definicja qsort to:

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

Zwróć uwagę na użycie size_t zamiast int. I oczywiście pusta * baza, ponieważ nie wiesz, jakiego rodzaju sortujesz.