快速排序示例中的錯誤（K＆R C書）？

這個快速排序應該按照升序排列「v [left] ... v [right]」;從C程序設計語言複製（沒有評論）的K & R（第二版）：快速排序示例中的錯誤（K＆R C書）？

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。這不會由於整數溢出而導致未定義的行爲嗎？

來源

2011-06-26 functionptr

它可能是在假設數組在運行時不會很大的情況下編程的。 :) – sarnold

這是一個非常好的假設，因爲您的快速排序程序沒有內存空間 –

另請參閱：http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it -nearly.html –

是的，你說得對。您可以使用left - (left - right)/2來避免溢出。

來源

2011-06-26 21:47:57 Artefact2

什麼溢出？ –

偉大的解決方案！ – functionptr

@Jerry：ITYM：'left +（right-left）/ 2' –

你不是在想象一個數組元素，INT_MAX元素，是嗎？

來源

2011-06-26 21:47:59

假設32位整數，這只是8千兆字節的地址空間。在現代硬件上不僅可行。 :) – sarnold

我們可能不得不原諒K＆R不考慮從kB到GB的內存增長。「640k應該足夠每個人」？ –

@Bo有16位int的平臺，你知道的，我很確定他們中的一些有超過64Kb的內存。 'int'！='intptr_t'。 –

是的，你說得對，雖然它可能就是爲了簡單而寫的 - 畢竟這只是一個例子，而不是生產代碼。

來源

2011-06-26 21:49:58

K & R對於使用unsigned vs signed參數總是有點草率。使用我認爲只有16千字節內存的PDP工作的副作用。剛纔這個問題已經解決了。 qsort的當前定義是

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

請注意使用size_t而不是int。因爲你不知道你正在排序的是什麼類型，所以當然是void * base。

來源

2011-06-26 22:30:19

'__cdecl'疣不是標準定義的一部分。 – caf

我確信這是事實，他們可能只有*一個*調用約定當時。以* 2 *開頭的關鍵字少得多。留給供應商使其變得複雜。必要如此，標準有點麻煩。 –

快速排序示例中的錯誤（K＆R C書）？

回答

相關問題