3路快速排序（C實現）

Question

我嘗試implement一些使用C的純粹通用算法。我堅持使用3路快速排序，但不知何故實現不能提供正確的輸出。輸出幾乎排序，但一些鍵不應該在那裏。代碼如下。提前致謝。

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <time.h> 

static void swap(void *x, void *y, size_t size) { 
    void *tmp = malloc(size); 

    memcpy(tmp, x, size); 
    memcpy(x, y, size); 
    memcpy(y, tmp, size); 

    free(tmp); 
} 

static int cmpDouble(const void *i, const void *j) { 
    if (*(double *)i < *(double *)j) 
     return 1; 
    else if (*(double *)i == *(double *)j) 
     return 0; 
    else 
     return -1; 
} 

void qsort3way(void *base, int lo, int hi, size_t size, 
       int (*cmp)(const void *, const void *)) { 
    if (hi <= lo) 
     return; 
    else { 
     char *ptr = (char*)base; 
     char *v = ptr + lo * size; 

     int lt = lo, gt = hi; 
     int i = lo; 
     while (i <= gt) { 
      int c = cmp(v, ptr + i * size); 
      if (c < 0) 
       swap(ptr + (lt++) * size, ptr + (i++) * size, size); 
      else if (c > 0) 
       swap(ptr + i * size, ptr + (gt--) * size, size);  
      else 
       i++; 
     } 

     qsort3way(base, lo, lt - 1, size, cmp); 
     qsort3way(base, gt + 1, hi, size, cmp); 
    }  
} 

int main(void) { 
    int i; 
    double *d = (double*)malloc(sizeof(double) * 100); 

    for (i = 0; i < 100; i++) 
     d[i] = (double)rand(); 

    qsort3way(d, 0, 100 -1, sizeof(double), cmpDouble); 

    for (i = 0; i < 100; i++) 
     printf("%.10lf\n", d[i]); 

    free(d); 
    return 0; 
} 

輸出樣本：

 
    41.0000000000 
    153.0000000000 
    288.0000000000 
    2082.0000000000 
    292.0000000000 
    1869.0000000000 
    491.0000000000 
    778.0000000000 
    1842.0000000000 
    6334.0000000000 
    2995.0000000000 
    8723.0000000000 
    3035.0000000000 
    3548.0000000000 
    4827.0000000000 
    3902.0000000000 
    4664.0000000000 
    5436.0000000000 
    4966.0000000000 
    5537.0000000000 
    5447.0000000000 
    7376.0000000000 
    5705.0000000000 
    6729.0000000000 
    6868.0000000000 
    7711.0000000000 
    9961.0000000000 
    8942.0000000000 
    9894.0000000000 
    9040.0000000000 
    9741.0000000000 

Answer 1

讀取您提供給@JohnBollinger的book link後。我明白你的算法是如何工作的。您的問題是您的支點移動，但您不改變v的值。你的支點是該指數lt

char *ptr = base; 

int lt = lo, gt = hi; // lt is the pivot 
int i = lo + 1; // we don't compare pivot with itself 
while (i <= gt) { 
    int c = cmp(ptr + lt * size, ptr + i * size); 
    if (c < 0) { 
    swap(ptr + lt++ * size, ptr + i++ * size, size); 
    } 
    else if (c > 0) 
    swap(ptr + i * size, ptr + gt-- * size, size); 
    else 
    i++; 
} 
qsort3way(base, lo, lt - 1, size, cmp); 
qsort3way(base, gt + 1, hi, size, cmp); 

在我建議你一個 「正確」 的解決方案：

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

typedef void qsort3way_swap(void *a, void *b); 
typedef int qsort3way_cmp(void const *a, void const *b); 

static void qsort3way_aux(char *array_begin, char *array_end, size_t size, 
          qsort3way_cmp *cmp, qsort3way_swap *swap) { 
    if (array_begin < array_end) { 
    char *i = array_begin + size; 
    char *lower = array_begin; 
    char *greater = array_end; 
    while (i < greater) { 
     int ret = cmp(lower, i); 
     if (ret < 0) { 
     swap(i, lower); 
     i += size; 
     lower += size; 
     } else if (ret > 0) { 
     greater -= size; 
     swap(i, greater); 
     } else { 
     i += size; 
     } 
    } 
    qsort3way_aux(array_begin, lower, size, cmp, swap); 
    qsort3way_aux(greater, array_end, size, cmp, swap); 
    } 
} 

static void qsort3way(void *array_begin, void *array_end, size_t size, 
         qsort3way_cmp *cmp, qsort3way_swap *swap) { 
    qsort3way_aux(array_begin, array_end, size, cmp, swap); 
} 

static void swap_int_aux(int *a, int *b) { 
    int tmp = *a; 
    *a = *b; 
    *b = tmp; 
} 

static void swap_int(void *a, void *b) { swap_int_aux(a, b); } 

static int cmp_int_aux(int const *a, int const *b) { 
    if (*a < *b) { 
    return 1; 
    } else if (*a > *b) { 
    return -1; 
    } else { 
    return 0; 
    } 
} 

static int cmp_int(void const *a, void const *b) { return cmp_int_aux(a, b); } 

static void print_int(char const *intro, int const *array, size_t const size) { 
    printf("%s:", intro); 
    for (size_t i = 0; i < size; i++) { 
    printf(" %d", array[i]); 
    } 
    printf("\n"); 
} 

#define SIZE 42 

int main(void) { 
    int array[SIZE]; 

    srand((unsigned int)time(NULL)); 
    for (size_t i = 0; i < SIZE; i++) { 
    array[i] = rand() % SIZE - SIZE/2; 
    } 

    print_int("before", array, SIZE); 

    qsort3way(array, array + SIZE, sizeof *array, cmp_int, swap_int); 

    print_int("after", array, SIZE); 
} 

注：優化int i = lo + 1;和char *i = array_begin + size;是強制性的。因爲在函數比較返回pivot != pivot的情況下，這將導致無限遞歸。這將如何可能？

1. 函數cmp是bug。
2. double有奇怪的力量...雙重可以不等於自己！ （-NAN）。

Answer 2

執行不會給出正確的結果，因爲它是錯誤。事實上，這是非常錯誤的，因爲它應該是一種三向快速排序，而不是一個普通排序。

一個基本問題是，在主分區循環之後，您已經省略了將樞軸移到其正確位置的位。對於標準快速排序，在循環之後需要額外的交換或賦值，具體取決於實現細節。對於包含一個或兩個額外循環的三路快速排序，將潛在許多等於樞軸的值移動到其位置。

一個更隱晦的問題是@Stargateur首先指出：你通過指針跟蹤元素，而不是值，並且你（有時）在分區循環過程中將原始值從該位置交換出來。

此外，您的主分區循環對於三向快速排序也是錯誤的。當你遇到一個與pivot相等的元素時，你只需要將它放在適當的位置，但是你需要將它移動到一端或另一端（或者如果你願意承擔這種內存開銷，則需要某種輔助存儲），所以你可以在最後執行到中間的移動。從某種意義上說，前面的問題是這個問題的一個特例 - 您不會預留空間或跟蹤數據透視值。解決這個問題也將解決以前的問題。

我不確定你用什麼參考來準備你的實現，或者你是否從頭開始構建它，但Geeks for Geeks有一個C++（但幾乎C）implementation for int arrays，你可能想要檢查。