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);

我建议你一个"proper"解决方案：

#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;是强制性的。因为在函数比较 return 和 pivot != pivot 的情况下，这将导致无限递归。这怎么可能？

函数 cmp 存在错误。
double 有奇异的力量……双倍可以不等于自身！ (-nan).

Answer 2

实施没有给出正确的结果，因为它是错误的。事实上，这是一个非常严重的错误，因为它应该是三向快速排序而不是常规快速排序。

一个基本问题是您省略了在主分区循环之后将枢轴移动到正确位置的位。对于标准的快速排序，这需要在循环后进行一次额外的交换或赋值，具体取决于实现细节。对于涉及一个或两个额外循环的三向快速排序，将等于主元的潜在多个值移动到它们的位置。

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

此外，您的主分区循环对于三向快速排序也是错误的。当你遇到一个等于枢轴的元素时，你只需将它留在原处，但你需要将它移动到一端或另一端（或者移动到某种辅助存储，如果你愿意承担内存成本）所以你可以在最后执行到中间的移动。从某种意义上说，上一个问题是这个问题的一个特例——您没有为或跟踪枢轴值保留 space。解决这个问题也会解决之前的问题。

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

Answer 3

您的实施是不正确的，因为在分区阶段中枢轴可能会移动，并且您使用不再指向它的指针进行比较。其他语言的实现使用枢轴的值而不是它的地址。

还要注意这些缺点：

两种方式递归可能会导致病态分布的堆栈溢出。在您的情况下，已经排序的数组是病态分布。
比较函数应该return相反的值：-1 if a < b，+1 is a > b and 0 if a == b.
API 是非标准的且令人困惑：您应该传递元素的数量而不是包含边界的范围。

这是更正和评论的版本：

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

static void swap(unsigned char *x, unsigned char *y, size_t size) {
    /* sub-optimal, but better than malloc */
    while (size-- > 0) {
        unsigned char c = *x;
        *x++ = *y;
        *y++ = c;
    }
}

void qsort3way(void *base, int n, size_t size,
               int (*cmp)(const void *, const void *))
{
    unsigned char *ptr = (unsigned char *)base;

    while (n > 1) {
        /* use first element as pivot, pointed to by lt */
        int i = 1, lt = 0, gt = n;
        while (i < gt) {
            int c = cmp(ptr + lt * size, ptr + i * size);
            if (c > 0) {
                /* move smaller element before the pivot range */
                swap(ptr + lt * size, ptr + i * size, size);
                lt++;
                i++;
            } else if (c < 0) {
                /* move larger element to the end */
                gt--;
                swap(ptr + i * size, ptr + gt * size, size);
                /* test with that element again */
            } else {
                /* leave identical element alone */
                i++;
            }
        }
        /* array has 3 parts:
         * from 0 to lt excluded: elements smaller than pivot
         * from lt to gt excluded: elements identical to pivot
         * from gt to n excluded: elements greater than pivot
         */
        /* recurse on smaller part, loop on larger to minimize
           stack use for pathological distributions */
        if (lt < n - gt) {
            qsort3way(ptr, lt, size, cmp);
            ptr += gt * size;
            n -= gt;
        } else {
            qsort3way(ptr + gt * size, n - gt, size, cmp);
            n = lt;
        }
    }
}    

static int cmp_double(const void *i, const void *j) {
    /* this comparison function does not handle NaNs */
    if (*(const double *)i < *(const double *)j)
        return -1;
    if (*(const double *)i > *(const double *)j)
        return +1;
    else
        return 0;
}

int main(void) {
    double d[100];
    int i;

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

    qsort3way(d, 100, sizeof(*d), cmp_double);

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

    return 0;
}

3 路快速排序（C 实现）

3 way quicksort (C implementation)

c

sorting

partitioning

quicksort