快速排序算法訪問衝突寫入位置

執行下面的快速排序算法有什麼問題。調試報告「訪問衝突寫入位置」。我找不到它。我是否應該將參數的位置作爲參數傳遞給sort和partition函數？此代碼基於此交互式在線演示：http://me.dt.in.th/page/Quicksort。快速排序算法訪問衝突寫入位置

#include <cstdio> 
#include <cstdlib> 
#include <cstdint> 
#include <utility> 

#define LIST_SIZE (UInt)10 

typedef uint64_t UInt; 

void print(UInt * list, UInt size) { 
    for (UInt i = 0; i < size; i++) 
     printf("%llu ", list[i]); 

    printf("\n"); 
} 

void fill(UInt * list, UInt size) { 
    for (UInt i = 0; i < size; i++) 
     list[i] = (UInt)std::rand(); 
} 

UInt partition(UInt * list, UInt left, UInt right) { 
    UInt p = list[left], t = left + 1; 

    for (UInt i = left + 1; i <= right; i++) { 
     if (list[i] < p) { 
      std::swap(list[i], list[t]); 
      t++; 
     } 
    } 

    std::swap(p, list[t]); 

    return t; 
} 

void sort(UInt * list, UInt left, UInt right) { 
    UInt p; 

    if (left < right) { 
     p = partition(list, left, right); 

     sort(list, left, p - 1); 
     sort(list, p + 1, right); 
    } 
} 

void quicksort(UInt * list, UInt size) { 
    sort(list, 0, size - 1); 
} 

int main(int argc, char ** argv) { 
    UInt list[LIST_SIZE]; 

    fill(list, LIST_SIZE); 
    print(list, LIST_SIZE); 
    quicksort(list, LIST_SIZE); 
    print(list, LIST_SIZE); 

    return 0; 
}

來源

2017-03-10 Danilo

得到一些調試打印發生，並確保每一步都在做你認爲正在做的事情。 –

絕對通過調試器運行此代碼並單步執行，以確保它按照您的想法執行。要特別注意'partition（）'的返回值。另一個有用的技術是「assert（）」假設，如果假的話會破壞程序，例如分區值在「left」和「right」之間。 – Davislor

我用調試器查看了你的程序，它看起來被打破了。段錯誤發生在堆棧軌跡非常深的位置（遞歸深度在〜400）。 – OutOfBound

以下更改爲您做了訣竅。在for循環中，你必須檢查我是否有<。如果你在那裏做< =，那麼在某些情況下你不會取得進展。但是，我沒有檢查你的算法在各方面是否正確。

UInt partition(UInt * list, UInt left, UInt right) { 
    UInt p = list[left], t = left + 1; 

    for (UInt i = left + 1; i < right; i++) { 
     if (list[i] < p) { 
      std::swap(list[i], list[t]); 
      t++; 
     } 
    } 

    std::swap(p, list[t]); 

    return t; 
}

來源

2017-03-10 13:17:06 OutOfBound

你的問題解決了嗎？ – OutOfBound

快速排序算法訪問衝突寫入位置

回答

相關問題