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

[superme7 (Bonbodi)]

開發平台(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: 你知道 Partition 是怎麼運作的嗎?
→ LPH66: 我是指, 每一行做了什麼事使得最後得到什麼結果這些細節
推 ucrxzero: 不是就是 樞點右邊都比他大 左邊都比他小
→ ucrxzero: 然後遞迴下去 若找到越中間的樞點越好
→ superme7: tace過code了用pivot = end實作過，但是不知道pivot = m
→ superme7: 為甚麼跑不出來
推 ucrxzero: 你是不是在寫作業
→ superme7: 不是，這是我上網學的
推 ucrxzero: 我幫你看一夏
→ superme7: 感謝U大
推 ucrxzero: 找到了改一下條件
→ ucrxzero: while (i<j &&list[i] <= list[pivot]);
→ ucrxzero: while (i<j &&list[j] >= list[pivot]);
→ ucrxzero: 但還是不對
→ ucrxzero: 等等= =
推 ucrxzero: www.algolist.net/Algorithms/Sorting/Quicksort
推 ko27tye: 你要這樣做的話 partition function內的 最外層swap不要
→ ko27tye: 做 然後把i和j傳出去給quickSort當pivot
推 ucrxzero: 對 ko27跟我查到的是一樣的方式
→ superme7: 感謝各位大大 我知道原因了
推 ro9956882: pivot在end可行的話 多一行swap(list[mid],list[end])