- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
作为学习练习,我正在用 C 语言实现快速排序算法。枢轴是 3 个值的中位数,对于具有 4 个或更少元素的分区,我切换到插入排序。
现在我一直在测试两种变体:一种使用 Hoare's partition scheme , 另一个用途 Dutch Flag .
更新:包括两个变体的整个文件。
霍尔的:
#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); \
if((*cmp_q)((void *)m, (void *)l) < 0) {\
SWAP(m, l); \
} \
if((*cmp_q)((void *)r, (void *)m) < 0) {\
SWAP(r, m); \
} else { \
goto jump; \
} \
if((*cmp_q)((void *)m, (void *)l) < 0) {\
SWAP(m, l); \
} \
jump:; \
}
#define COPY(dest, src) \
{ \
char *src_copy = (src); \
char *dest_copy = (dest); \
size_t size_copy = size_q; \
while(size_copy-- > 0) { \
*dest_copy++ = *src_copy++; \
} \
}
static size_t size_q = 0;
static char *e = NULL;
static int (*cmp_q)(const void *, const void *) = NULL;
void sort(char *left, char *right) {
int elements = (right+size_q-left)/size_q;
//========== QUICKSORT ==========
if(elements > THRESHOLD) {
//========== PIVOT = MEDIAN OF THREE ==========
char *mid = left+size_q*((right-left)/size_q>>1);
MEDIAN_OF_3(left, mid, right);
char *pivot = mid;
//========== PARTITIONING ==========
char *left_part = left+size_q;
char *right_part = right-size_q;
while(left_part < right_part) {
while((*cmp_q)((void *)left_part, (void *)pivot) < 0) {
left_part += size_q;
}
while((*cmp_q)((void *)right_part, (void *)pivot) > 0) {
right_part -= size_q;
}
if(left_part < right_part) {
SWAP(left_part, right_part);
if(pivot == left_part) {
pivot = right_part;
} else if(pivot == right_part) {
pivot = left_part;
}
left_part += size_q;
right_part -= size_q;
}
}
//========== RECURSIVE CALLS ==========
sort(left, right_part);
sort(left_part, right);
} else if(elements > 1) {
//========== INSERTION SORT ==========
char *i, *j;
for(i = left+size_q; i <= right; i += size_q) {
if((*cmp_q)((void *)i, (void *)(i-size_q)) < 0) {
COPY(e, i);
for(j = i-size_q; j >= left && (*cmp_q)((void *)e, (void *)j) < 0; j -= size_q) {
COPY(j+size_q, j);
}
COPY(j+size_q, e);
}
}
}
}
void quicksort(void *array, size_t num, size_t size, int (*cmp)(const void *a, const void *b)) {
char *array_q = (char *)array;
size_q = size;
cmp_q = cmp;
e = malloc(size_q);
sort(array_q, array_q+size_q*(num-1));
free(e);
}
荷兰国旗:
#include <stdlib.h>
#include "quicksort.h"
#define THRESHOLD 4
#define SWAP(a, b) \
{ \
char *a_q = (a); \
char *b_q = (b); \
int size_swap = size_q; \
char tmp; \
while(size_swap-- > 0) {\
tmp = *a_q; \
*a_q++ = *b_q; \
*b_q++ = tmp; \
} \
\
}
#define MEDIAN_OF_3(left, mid, right) \
{ \
char *l = (left); \
char *m = (mid); \
char *r = (right); \
if((*cmp_q)((void *)m, (void *)l) < 0) {\
SWAP(m, l); \
} \
if((*cmp_q)((void *)r, (void *)m) < 0) {\
SWAP(r, m); \
} else { \
goto jump; \
} \
if((*cmp_q)((void *)m, (void *)l) < 0) {\
SWAP(m, l); \
} \
jump:; \
}
#define COPY(dest, src) \
{ \
char *src_copy = (src); \
char *dest_copy = (dest); \
size_t size_copy = size_q; \
while(size_copy-- > 0) { \
*dest_copy++ = *src_copy++; \
} \
}
static size_t size_q = 0;
static char *pivot = NULL;
static char *e = NULL;
static int (*cmp_q)(const void *, const void *) = NULL;
void sort(char *left, char *right) {
int elements = (right+size_q-left)/size_q;
//========== QUICKSORT ==========
if(elements > THRESHOLD) {
//========== PIVOT = MEDIAN OF THREE ==========
char *mid = left+size_q*((right-left)/size_q>>1);
MEDIAN_OF_3(left, mid, right);
COPY(pivot, mid);
//========== 3-WAY PARTITIONING (DUTCH FLAG PROBLEM) ==========
char *less = left;
char *equal = left;
char *greater = right;
int value;
while(equal <= greater) {
value = (*cmp_q)((void *)equal, (void *)pivot);
if(value < 0) {
SWAP(less, equal);
less += size_q;
equal += size_q;
} else if(value > 0) {
SWAP(equal, greater);
greater -= size_q;
} else {
equal += size_q;
}
}
//========== RECURSIVE CALLS ==========
sort(left, less-size_q);
sort(greater+size_q, right);
} else if(elements > 1) {
//========== INSERTION SORT ==========
char *i, *j;
for(i = left+size_q; i <= right; i += size_q) {
if((*cmp_q)((void *)i, (void *)(i-size_q)) < 0) {
COPY(e, i);
for(j = i-size_q; j >= left && (*cmp_q)((void *)e, (void *)j) < 0; j -= size_q) {
COPY(j+size_q, j);
}
COPY(j+size_q, e);
}
}
}
}
void quicksort(void *array, size_t num, size_t size, int (*cmp)(const void *a, const void *b)) {
char *array_q = (char *)array;
size_q = size;
cmp_q = cmp;
pivot = malloc(size_q);
e = malloc(size_q);
sort(array_q, array_q+size_q*(num-1));
free(pivot);
free(e);
}
两者得到相同的输入,一系列文件,每个文件包含 10^n
范围为 [0:(10^n)+1]< 的随机整数值
。 n
的范围从 1 到 7(10 到 1000 万个元素)。我希望 Dutch Flag 的实现速度至少与 Hoare 的一样快,但事实并非如此。
标志:-O3
Implementation Size Runs Time
Hoare's 10^7 10 avg=2.148s
Dutch Flag 10^7 10 avg=3.312s
然后我更改了输入:相同的大小,10^n
,但值是 [0:10^(n-1)]
,这保证了很多重复值(value)观。
结果:
Implementation Size Runs Time
Hoare's 10^7 10 avg=0.170s
Dutch Flag 10^7 10 avg=0.260s
即使对于重复值,Dutch Flag 也比 Hoare 慢。为什么?所选择的枢轴似乎不太可能是唯一的。
我的环境,如果重要的话:
CPU=Intel(R) Core(TM) i7-6820HK @ 2.70GHz
VM OS=Linux version 4.4.0-36-generic, Ubuntu 16.04.2, gcc version 5.4.0
Host=Microsoft Windows 10 Home
IDE=Eclipse CDT Neon
最佳答案
不要使用malloc
和free
。每次递归调用(总共N次)都要用到它们,耗费大量时间。
如果启用优化 (-O3
),比较将更有用。
SWAP
是宏还是函数?如果是函数,尽量让它内联
。
关于c - Quicksort - 为什么我的 dutch-flag 实现比我的 Hoare-2-partition 实现慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39424799/
这是我 4 天后的考试,我刚刚和我的讲师谈过,他对讲座的这一部分非常不清楚,我和许多学生一起很难理解如何理解这一点。 基本上,如果您想使用信号量实现霍尔监视器,所涉及的步骤序列是什么? 下面是伪代码
所以用一个数组 [6, 3, 8, 7, 2, 5, -9, 1, 4, 10] 我期望使用 Hoare 的分区算法 [-9, 1, 2, 3, 4, 5, 6, 7, 8, 10] 但是我的代码中的
考虑一个未排序的列表 9,3,5,3,9,其中 5 是主元。当比较索引 0 和索引 4 处的元素时,它们的值彼此相等,并且都大于基准值。在这种情况下会发生什么?它们不能互换,因为“小于”部分仍然有 9
在阅读有关它的维基百科文章后,我在 C++ 中实现了快速排序。只是想重温我在学校为换工作面试做准备的内存。 这是我的实现 #include size_t partition(std::vector
我正在尝试编写自己的 hoare 分区函数以更好地理解它。我以为我很好地遵循了它的定义和伪代码,但即使它在很多情况下似乎都按预期工作,但当传入一个具有多个等于 pivot 的值的列表时,它会分崩离析并
我尝试用 Hoare 的分区方案实现快速排序算法,但是当我在测试列表上运行它时 {412, 123, 57, 12, 1, 5}然后打印出来,我得到原始顺序的数字。有人可以帮我发现我做错了什么吗?下面
所以,我写了一个快速排序算法和一个霍尔分区算法。不知何故,当我尝试在 main () 中运行示例案例时,它卡在了 fastSort(test, 0,3) 上。似乎存在无限循环。我不知道如何修复它,因为
正如标题所说,我如何用霍尔三元组验证下面的功能?我阅读了有关它的各种讲座,但我不知道该怎么做。 int uguaglianza_insiemi(elem_lista_t *insieme_A,
您能举例说明 2 个分区方案给出不同的结果吗?对于 Lomuto,我们必须这样写: quicksort(A,l,p) quicksort(A,p+1,h) 与霍尔在一起时: quicksort(A,l
是否可以使用 Hoare 分区实现 QuickSelect 算法? 至少乍一看似乎无法完成,因为 Hoare 分区不一定返回主元的索引。 我错过了什么吗? 最佳答案 使用 Hoare 分区方案,由于主
我已经为 Quicksort 实现了经典的 Hoare 分区算法。它适用于任何唯一数字列表 [3、5、231、43]。唯一的问题是当我有一个包含重复项 [1, 57, 1, 34] 的列表时。如果我得
所有变量名均来自Quicksort's wikipedia page Lomuto 和 Hoare 的快速排序伪代码。 如果 p 是 partition 函数返回的值,Hoare 将他的数组从 lo
我遇到过两种不同的监视器实现。一种使用 while 循环,每次在进入休眠前和从 sleep 中醒来时检查特定条件是否为真。另一个只检查一次 if 条件是否为真,如果不是,则进入休眠状态,但在醒来时不会
看看这句话取自The examples from Tony Hoare's seminal 1978 paper : Go's design was strongly influenced by Ho
我不确定 { true } x := y { x = y } 是有效的 Hoare triple . 我不确定是否允许引用一个变量(在本例中为 y ),而无需先在三重程序主体或前提条件中明确定义它。
作为学习练习,我正在用 C 语言实现快速排序算法。枢轴是 3 个值的中位数,对于具有 4 个或更少元素的分区,我切换到插入排序。 现在我一直在测试两种变体:一种使用 Hoare's partition
目前我正在研究霍尔逻辑以了解程序的正确性。特别是,我正在阅读 Hoare logic我正在分析 while 规则中的以下示例: 我想知道的是简化步骤:为什么 {x <= 10 ^ x < 10}简化为
我是一名优秀的程序员,十分优秀!