c - 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

看完book link您提供给@JohnBollinger。我了解您的算法是如何工作的。您的问题是您的枢轴移动了，但您没有更改 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 是错误的。
2. double 有一种奇怪的力量……一个 double 可以不等于它自己! (-nan).