作者superme7 (Bonbodi)
看板C_and_CPP
標題[問題] Quicksort選mid為pivot出現問題
時間Sun Apr 18 14:57:41 2021
開發平台(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://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1618729063.A.8D4.html
1F：推 LPH66: 你知道 Partition 是怎麼運作的嗎? 04/18 15:42
2F：→ LPH66: 我是指, 每一行做了什麼事使得最後得到什麼結果這些細節 04/18 15:42
3F：推 ucrxzero: 不是就是 樞點右邊都比他大 左邊都比他小 04/18 15:47
4F：→ ucrxzero: 然後遞迴下去 若找到越中間的樞點越好 04/18 15:48
5F：→ superme7: tace過code了用pivot = end實作過，但是不知道pivot = m 04/18 15:55
6F：→ superme7: 為甚麼跑不出來 04/18 15:56
7F：推 ucrxzero: 你是不是在寫作業 04/18 15:57
8F：→ superme7: 不是，這是我上網學的 04/18 16:01
9F：推 ucrxzero: 我幫你看一夏 04/18 16:01
10F：→ superme7: 感謝U大 04/18 16:06
11F：推 ucrxzero: 找到了改一下條件 04/18 16:22
12F：→ ucrxzero: while (i<j &&list[i] <= list[pivot]); 04/18 16:22
13F：→ ucrxzero: while (i<j &&list[j] >= list[pivot]); 04/18 16:22
14F：→ ucrxzero: 但還是不對 04/18 16:25
15F：→ ucrxzero: 等等= = 04/18 16:25
16F：推 ucrxzero: www.algolist.net/Algorithms/Sorting/Quicksort 04/18 17:22
17F：推 ko27tye: 你要這樣做的話 partition function內的 最外層swap不要 04/18 19:38
18F：→ ko27tye: 做 然後把i和j傳出去給quickSort當pivot 04/18 19:38
19F：推 ucrxzero: 對 ko27跟我查到的是一樣的方式 04/18 19:42
20F：→ superme7: 感謝各位大大 我知道原因了 04/18 22:06
21F：推 ro9956882: pivot在end可行的話 多一行swap(list[mid],list[end]) 04/24 02:42