[問題] Quicksort選mid為pivot出現問題

看板C_and_CPP作者superme7 (Bonbodi)時間3年前 (2021/04/18 14:57)推噓9(9推 0噓 12→)

留言21則, 5人參與討論串1/1

開發平台(Platform): Win10 編譯器: GCC 額外使用到的函數庫(Library Used): 無問題(Question)：試著優化Quicksort，選mid為pivot和選end結果不同，選end結果正確，mid卻無法sort，請各位幫我看看程式哪裡有錯 P.S. 註解處為選end為pivot 餵入的資料(Input)：9 4 1 6 7 3 8 2 5 預期的正確結果(Expected Output)：1 2 3 4 5 6 7 8 9 錯誤結果(Wrong Output)：未顯示程式碼(Code): #include <iostream> using namespace std; const int n = 9; void swap(int &a, int &b) { int t = a; a = b; b = t; } int Partition(int *list, int front, int end) { int pivot = (front + end) / 2; int i = front - 1; int j = end + 1; while (i < j) { do i++; while (list[i] <= list[pivot]); do j--; while (list[j] >= list[pivot]); swap(list[i], list[j]); } swap(list[pivot], list[i]); return i; } /*int Partition(int *list, int front, int end) { int i = front - 1; for (int j = front; j < end; j++) { if (list[j] < list[end]) { swap(list[++i], list[j]); } } swap(list[++i], list[end]); return i; }*/ void Quicksort(int *list, int front, int end) { if (front < end) { int pivot = Partition(list, front, end); Quicksort(list, front, pivot - 1); Quicksort(list, pivot + 1, end); } } void Print(int *list) { for (int i = 0; i < n; i++) cout << list[i] << " "; cout << endl; } int main() { int a[] = {9, 4, 1, 6, 7, 3, 8, 2, 5}; cout << "Unsorted: \n"; Print(a); cout << "Sorted: \n"; Quicksort(a, 0, n - 1); Print(a); return 0; } -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.136.218 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1618729063.A.8D4.html

推

LPH66

04/18 15:42, 3年前 , 1^F

04/18 15:42, 1^F

→

LPH66

04/18 15:42, 3年前 , 2^F

04/18 15:42, 2^F

推

ucrxzero

04/18 15:47, 3年前 , 3^F

04/18 15:47, 3^F