[問題] quicksort swap pivot時出現問題

[nasty1122 (阿寶)]

完整程式碼：
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
int Partition(int *arr, int front, int end){
    int pivot = arr[(end+front)/2];
    int i = front -1, j;
    //i denotes the position of the key where all the elements in the front
are smaller than pivot.
    for (j = front; j < end+1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }

    }
    i++;
    swap(&arr[i], &pivot); //put pivot into the middle of the two subarrays
    return i;
}

void QuickSort(int *arr, int front, int end){

        if (front < end) {
        int p = Partition(arr, front, end);
        QuickSort(arr, front, p - 1);
        QuickSort(arr, p + 1, end);
    }
}

int main() {

    int n,i;
    scanf("%d",&n);
    int arr[n];
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
        }

    QuickSort(arr, 0, n-1);

    for (i = 0; i < n; i++) {
        printf("%d ",arr[i]);
    }

    return 0;
}

這是一個以array中間為pivot的quicksort，
第一個輸入的數字表示有幾個數字要排序，
但我的輸出結果卻是這樣：
假設輸入:10
4 8 7 2 3 5 6 9 10 1
輸出結果：
1 2 3 3 3 5 6 7 8 9 10
有些數字莫名其妙就被換掉了，
好像是在Partition迴圈結束那邊swap arr[i]跟pivot的地方出問題，
但我怎麼看都看不出原因，
求各位大神指教，感謝~~

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.171.201.122
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1554731979.A.52E.html
※ 編輯: nasty1122 (118.171.201.122), 04/08/2019 22:03:55
※ 編輯: nasty1122 (118.171.201.122), 04/08/2019 22:04:35
※ 編輯: nasty1122 (118.171.201.122), 04/08/2019 22:05:30
推 LPH66: 因為你的那個對換不是陣列元素對換
推 james80351: 那個地方是要和前面pivot代表的元素做交換
→ james80351: arr[(front + end) / 2]
但因為pivot是middle的話在迴圈內就會一直被換來換去，所以最後那邊不能寫arr
[(front+end)/2]，有其他方式可以表示pivot最後在的位置嗎?
※ 編輯: nasty1122 (118.171.201.122), 04/08/2019 23:47:52
推 LPH66: 所以一個常見的方法其實是先把 pivot 放在陣列"開頭"
→ LPH66: 接著用你的方法維護成 [pv][<pv ... <pv][>pv ... >pv]
→ LPH66: 最後再用你這一步想做的交換把 [pv] 擺在兩塊中間
→ LPH66: 概念上其實和你已經寫好的差不多, 只是不是另起變數存 pv
→ LPH66: 重點在於這一步既然要是陣列元素對換, 那就把 pv 也擺進去
→ LPH66: 定位問題就先找個好定位的地方放就好 (例如陣列開頭)
感謝回答，其實我原本寫的就是把pivot放最後的，這樣交換不會有問題沒錯，但就是想
試試看把pivot放中間，有沒有方法可以追蹤pivot最後換到的位子呢?
※ 編輯: nasty1122 (101.9.7.42), 04/09/2019 15:09:44
推 goddbird: 其實在swap裡改成&arr[你的pivot_idx]就會對了吧？小弟
→ goddbird: 也弱弱的還麻煩分享一下結果
後來再加一個變數存pivot index就可以了，感謝你~~
※ 編輯: nasty1122 (115.82.133.211), 04/12/2019 12:59:23
※ 編輯: nasty1122 (101.8.162.223), 04/14/2019 13:08:51