标签: dutch-national-flag-problem

作为一个学习练习,我在C中实现Quicksort算法.Pivot是3个值的中值,对于4个或更少元素的分区,我切换到Insertion Sort.

现在我一直在测试两种变体:一种使用Hoare的分区方案,另一种使用荷兰旗.

更新:包括两个变体的整个文件.

霍尔的:

#include <stdlib.h>
#include "quicksort.h"

#define THRESHOLD 4
#define SWAP(a, b)          \
{                           \
    char *a_swap = (a);     \
    char *b_swap = (b);     \
    int size_swap = size_q; \
    char tmp;               \
    while(size_swap-- > 0) {\
        tmp = *a_swap;      \
        *a_swap++ = *b_swap;\
        *b_swap++ = tmp;    \
    }                       \
}

#define MEDIAN_OF_3(left, mid, right)       \
{                                           \
    char *l = (left);                       \
    char *m = (mid);                        \
    char *r = (right); …