3路快速排序（C实现）

问题描述：

我尝试implement一些使用C的纯粹通用算法。我坚持使用3路快速排序，但不知何故实现不能提供正确的输出。输出几乎排序，但一些键不应该在那里。代码如下。提前致谢。3路快速排序（C实现）

#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

@ Stargateur：你的意思是将'void *'强制转换为'double'？这就是您在C编写通用代码的方式。 – adem

“size”是以字节为单位的变量的大小。在主函数中，我使用'sizeof（double）'传递'double'数据类型的大小。 – adem

答

读取您提供给@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的情况下，这将导致无限递归。这将如何可能？

函数cmp是bug。
double有奇怪的力量...双重可以不等于自己！（-NAN）。

为了解决这个问题，我们需要解释OP代码中的缺陷以及代码如何修复它们。 –

@JohnBollinger我讨厌你，这是一场噩梦来调试。 – Stargateur

真相也伤害了你，@Star和圣诞快乐。但是，在这里，+1发现了神奇的移动枢轴。 –

答

执行不会给出正确的结果，因为它是错误。事实上，这是非常错误的，因为它应该是一种三向快速排序，而不是一个普通排序。

一个基本问题是，在主分区循环之后，您已经省略了将枢轴移到其正确位置的位。对于标准快速排序，在循环之后需要额外的交换或赋值，具体取决于实现细节。对于包含一个或两个额外循环的三路快速排序，将潜在许多等于枢轴的值移动到其位置。

一个更隐晦的问题是@Stargateur首先指出：你通过指针跟踪元素，而不是值，并且你（有时）在分区循环过程中将原始值从该位置交换出来。

此外，您的主分区循环对于三向快速排序也是错误的。当你遇到一个与pivot相等的元素时，你只需要将它放在适当的位置，但是你需要将它移动到一端或另一端（或者如果你愿意承担这种内存开销，则需要某种辅助存储），所以你可以在最后执行到中间的移动。从某种意义上说，前面的问题是这个问题的一个特例 - 您不会预留空间或跟踪数据透视值。解决这个问题也将解决以前的问题。

我不确定你用什么参考来准备你的实现，或者你是否从头开始构建它，但Geeks for Geeks有一个C++（但几乎C）implementation for int arrays，你可能想要检查。

“..你通过指针跟踪主元素，而不是值...”。那么，编写一个纯粹的泛型函数就需要它。语言（C）本身不支持泛型编程，因此我们需要处理指针算术和处理void指针。我将其作为参考Sedgewick算法4版[书籍]（http://algs4.cs.princeton.edu/23quicksort/Quick3way.java.html）。最后，如果我是你，在写了那么多段之前，首先提出一个解决方案。 – adem

3路快速排序（C实现）

相关推荐