Lỗi trong ví dụ quicksort (sách K & R C)?

Question

Quicksort này được coi là sắp xếp "v [left] ... v [right] thành thứ tự tăng dần"; sao chép (không có bình luận) từ Ngôn ngữ lập trình C của 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); 
} 

Tôi nghĩ rằng có một lỗi ở

(left + right)/2 

Giả sử trái = INT_MAX - 1 và ngay = INT_MAX. Điều này sẽ không dẫn đến hành vi không xác định do tràn số nguyên không?

Answer 1

Có, bạn nói đúng. Bạn có thể sử dụng left - (left - right)/2 để tránh bị tràn.

Answer 2

Bạn không tưởng tượng ra một mảng có số lượng thành phần INT_MAX, phải không?

Answer 3

Có, bạn nói đúng, mặc dù nó có thể chỉ được viết theo cách đó để đơn giản - đó là một ví dụ sau khi tất cả, không phải mã sản xuất.

Answer 4

K & R luôn hơi cẩu thả với việc sử dụng các đối số chưa được ký và đã ký. Tác dụng phụ của việc làm việc với PDP chỉ có 16 kilobyte bộ nhớ mà tôi cho là. Đó là cố định một thời gian trước đây. Định nghĩa hiện tại của qsort là

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

Lưu ý việc sử dụng size_t thay vì int. Và tất nhiên là void * base vì bạn không biết loại bạn đang phân loại là gì.