排序基于分区（如在快速排序） [英] sorting based partition (like in quick-sort)
本文介绍了排序基于分区（如在快速排序）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
这是一个面试问题：
由于采用3种对象白色，红色，黑色的数组 - 一个人应该执行数组的排序，这样它看起来：
{白} * {黑} * {红} *。
该interwier说 - 你不能老是使用计数排序。他暗示是去想一些快速 - 排序相关technique.So我建议使用patition这好比快 - 排序partition.He只需要使用交换只有一次每个array`s element.I不`吨知道该怎么办呢....任何建议？（我不知道如果有可能的话）
我的解决方案：
的typedef枚举{白，黑，红颜色};无效掉期（彩色* P1，色* P2）
{
颜色TMP;
TMP = * P1;
* P1 = P2 *;
* P2 = tmp目录;
}无效sort3（彩色*改编，无符号整型N）
{
unsigned int类型W = 0，R = N - 1，I = 0; 而（I＆LT; = R）
{ 而（ARR [W] == WHITE）
{
W¯¯++;
}
而（ARR [R] == RED）
{
R--;
}
I =（并且R wⅰ）？ W：I;
开关（ARR [I]）
{
案例WHITE：
掉期（ARR + I，编曲+ W）;
W¯¯++;
打破;
案例RED：
{
掉期（ARR + I，编曲+ R）;
R--;
如果（ARR [I] == WHITE）
{
掉期（ARR + I，编曲+ W）;
W¯¯++;
}
打破;
}
}
我++;
}
}
解决方案
您用的空白部分的数组开始知白的价值观，未知值的最初大段，以及一个空的部分知道是红色的价值观。
首先：
- 通过计算的领先白色值的数量树立知白部分的大小。
- 通过计算后的红色值的数量树立已知的红色部分的大小。
这是好的，如果不是大小为零;你只需要知道的大小是什么。
您可以通过未知一节一个值在一个时间步骤：
- 如果下一个值是红色的，与已知的红色值前的最后的值将其交换，延长该部分。
- 如果下一个值是白色，与'已知是白'值之后的最后一个的值将其交换，延伸该部分。
- 否则，离开它在哪里。
- Restablish的'知白'和'已知的红色部分。
当环路结束后，所有的白色物体是在一开始，所有的红色物体是在末端，而黑色的对象必须是在中间
请注意，该试验的顺序是重要的（从这个code的原始版本颠倒）。由于雅科夫在他的<一个指出href=\"http://stackoverflow.com/questions/20164204/sorting-based-partition-like-in-quick-sort/20165129#comment30059837_20165129\">comment,在方案中，其中所述电流值是红色和之前的值的已知是红色部分是白的，第一测试移动红色到已知是红色部分而移动的白色到当前位置。然后，您可以检查当前位置是否是白色的，移动它。
的如果这是太多的掉期，有乐趣的工作如何做到这一点的另一种方式。的
这code似乎工作。它有相当广泛的自检和测试。完整的调试code可应要求提供（GPL V3）。
/ * SO 20164204 * /
将#define DEBUG＃包括LT＆;＆ASSERT.H GT;
＃包括LT＆;＆stdbool.h GT;
＃包括LT＆;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;
＃包括LT＆;＆time.h中GT;
＃包括LT＆;＆unistd.h中GT;
＃包括range.h
＃包括stderr.h
＃包括debug.h的typedef枚举{白，黑，红颜色};静态字符colour_ code（彩色C）;
静态无效trace_colours（FILE * FP，字符常量*标签，彩色*数据，符号NUM，为size_t W，为size_t R，为size_t C）;静态无效掉期（彩色* P1，彩色* P2）
{
颜色TMP;
TMP = * P1;
* P1 = P2 *;
* P2 = tmp目录;
}静态无效partition3（为size_t N，彩色* ARR）
{
如果（N下; = 1）
返回; 为size_t W = 0;
为size_t R = N; DB_TRACE（1，\\ NW0 =％祖; R0 =％祖：W，R）;
而（W＆LT; R＆放大器;＆安培;常用3 [W] == WHITE）
W¯¯++;
而（R＆GT; W＆放大器;＆安培; ARR [R-1] == RED）
R--;
DB_TRACE（1，W1 =％祖; R1 =％祖\\ n，W，R）; 用于（为size_t我= W; I＆LT; R;我++）
{
DB_TRACE（1，我=％2zu [1] W =％2zu，R =％2zu，C = C％，我，W，R，colour_ code（ARR [I]））;
DB_CALL（1，trace_colours（标准错误，，编曲，N，W，R，I））;
如果（ARR [I] == RED）
{
掉期（安培;常用3 [I]，和放大器;常用3 [ - R]）;
DB_TRACE（1，我=％2zu [2] W =％2zu，R =％2zu，C = C％，我，W，R，colour_ code（ARR [I]））;
DB_CALL（1，trace_colours（标准错误，，编曲，N，W，R，I））;
}
如果（ARR [I] == WHITE）
{
交换（安培;常用3 [I]，＆放大器;常用3 [W ++]）;
DB_TRACE（1，我=％2zu [3] W =％2zu，R =％2zu，C = C％，我，W，R，colour_ code（ARR [I]））;
DB_CALL（1，trace_colours（标准错误，，编曲，N，W，R，I））;
}
而（R＆GT; W＆放大器;＆安培; ARR [R-1] == RED）
R--;
而（W＆LT; R＆放大器;＆安培;常用3 [W] == WHITE）
W¯¯++;
如果（ⅰ＆所述; W＆放大器;＆安培;并且R w 0）
I = W - 1;
}
}/ *调试和测试基础* /静态字符常量* colour_name（彩色C）
{
返回（碳==白色的白：C = = RED红色：黑？）;
}静态字符colour_ code（彩色C）
{
返回（C == WHITEW：C = = RED'R'：？'B'）;
}静态无效print_colours（FILE * FP，字符常量*标签，彩色*数据，为size_t NUM）
{
fprintf中（FP，％S（％祖）的标签，NUM）;
用于（为size_t我= 0; I＆LT;民;我++）
fprintf中（FP，％C，colour_ code（数据由[i]））;
putc将（'\\ n'，FP）;
}静态无效dump_colours（字符常量*标签，彩色*数据，为size_t NUM）
{
print_colours（标准输出，标签，数据，NUM）;
}静态无效trace_colours（FILE * FP，字符常量*标签，彩色*数据，符号NUM，为size_t W，为size_t R，为size_t C）
{
断言（W＆LT; = R）;
断言（为r = NUM）;
fprintf中（FP，％S：标签）;
对（无符号I = 0; I＆LT;民;我++）
{
焦炭垫='';
如果（我== W ||我== R）
垫=|;
如果（我== C）
垫='[';
如果（我== C + 1）
垫=']';
fprintf中（FP，％C％C，垫，colour_ code（数据由[i]））;
}
如果（C = = NUM - 1）
putc将（']'，FP）;
否则，如果（R = = || NUM ==W¯¯NUM）
putc将（'|'，FP）;
putc将（'\\ n'，FP）;
}静态彩色* dup_sequence（为size_t N，颜色常量*一）
{
彩色* D =的malloc（N * sizeof的（* D））;
如果（D == 0）
{
fprintf中（标准错误，内存不足的\\ n）;
出口（1）;
}
用于（为size_t我= 0; I＆LT; N;我++）
D [i] = a [i];
返回D组;
}静态布尔is_invalid_sequence（为size_t N，颜色*一，布尔报告）
{
布尔RC = FALSE;
为size_t瓦;
为（W = 0; W＆LT; N; W-- ++）
{
如果（A [W]！= WHITE）
打破;
} 为size_t B：
对于（B = W; B＆LT; N; b ++）
{
如果（一个并[b] ==白）
{
如果（报告）
{
fprintf中（标准错误，错误：％C OUT的位置（％祖），colour_ code（A [B]），B）;
print_colours（标准错误，，A，N）;
}
RC = TRUE;
}
如果（A [B]！= BLACK）
打破;
} 为size_tř;
为（R = B; R＆LT; N，R ++）
{
如果（A [R]！= RED）
{
如果（报告）
{
fprintf中（标准错误，错误：％C OUT的位置（％祖），colour_ code（A [R]），R）;
print_colours（标准错误，，A，N）;
}
RC = TRUE;
}
} 返回RC;
}静态为size_t SEQNO = 0;
静态布尔WFLAG = FALSE;
静态布尔冗长= FALSE;typedef结构测试
{
彩色*数据;
为size_t的大小;
}测试;静态无效write_sequence（SEQ为size_t，为size_t N，彩色*一）
{
为size_t我;
的printf（色彩seq_％03zu [] = \\ N {\\ N的，SEQ）;
对于（i = 0; I＆LT; N;我++）
{
的printf（％S，colour_name（A []））;
如果（I％10 == 9）
的putchar（'\\ n'）;
}
如果（I％10！= 0）
的putchar（'\\ n'）;
的printf（}; \\ n）;
}静态布尔test_sequence（t检验）
{
布尔RC = TRUE;
为size_t N = t.size;
彩色* A = t.data;
彩色* D = dup_sequence（N，A）;
如果（详细）
dump_colours（之前，A，N）;
partition3（N，D）;
如果（详细）
dump_colours（后，D，N）;
如果（is_invalid_sequence（N，D，FALSE））
{
如果（！详细）
dump_colours（之前，A，N）;
is_invalid_sequence（N，D，真正的）;
如果（！详细）
dump_colours（后，D，N）;
如果（WFLAG）
write_sequence（++ SEQNO，N，A）;
RC = FALSE;
}
免费（D）;
返回RC;
}静态为size_t fixed_tests（字符常量*范围，为size_t *计数器）
{
SIZE_T失败= 0; 颜色seq_001 [] = {白，黑，红};
颜色seq_002 [] = {白色，白色，白色};
颜色seq_003 [] = {红，红，红};
颜色seq_004 [] = {黑，黑，黑};
颜色seq_005 [] = {红，黑，白};
颜色seq_006 [] = {白，白，红，红，黑，黑，白};
颜色seq_007 [] =
{
黑色，黑色，白色，白色，红色，红色，黑色，黑色，白色，
黑色，黑色，
};
颜色seq_008 [] = {WHITE，BLACK};
颜色seq_009 [] = {黑色，黑色，红色，红色，白色，白色，红色};
颜色seq_010 [] = {黑，黑，红，白，红};
颜色seq_011 [] =
{
红色，黑色，红色，白色，红色，红色，黑色，白色，红色，黑色，红色，
黑色，黑色，红色，黑色，白色，黑色，白色，白色，白色，
白，红，红，红，红，黑，白
};
颜色seq_012 [] =
{
白色，白色，红色，白色，红色，黑色，红色，黑色，白色，黑色，
红，红，红，白，红，红，黑，黑，黑，红，红，
黑色，黑色，白色，白色，红色，白色，黑色，红色，黑色，
白色，红色，白色，白色，红色，白色，黑色，红色，红色，红色，
白色，
};
颜色seq_013 [] = {红，白，红，};
颜色seq_014 [] = {红，白，};
颜色seq_015 [] = {红，黑，};
颜色seq_016 [] = {红，红，};
颜色seq_017 [] = {黑，白，};
颜色seq_018 [] = {黑，黑，};
颜色seq_019 [] = {黑，红，};
颜色seq_020 [] = {白，白，};
颜色seq_021 [] = {白，红，};
颜色seq_022 [] = {红，白，红，白，};
颜色seq_023 [] =
{
红色，白色，红色，白色，红色，红色，白色，白色，白色，
};
测试测试[] =
{
{seq_001，sizeof的（seq_001）/的sizeof（seq_001 [0]）}，
{seq_002，sizeof的（seq_002）/的sizeof（seq_002 [0]）}，
{seq_003，sizeof的（seq_003）/的sizeof（seq_003 [0]）}，
{seq_004，sizeof的（seq_004）/的sizeof（seq_004 [0]）}，
{seq_005，sizeof的（seq_005）/的sizeof（seq_005 [0]）}，
{seq_006，sizeof的（seq_006）/的sizeof（seq_006 [0]）}，
{seq_007，sizeof的（seq_007）/的sizeof（seq_007 [0]）}，
{seq_008，sizeof的（seq_008）/的sizeof（seq_008 [0]）}，
{seq_009，sizeof的（seq_009）/的sizeof（seq_009 [0]）}，
{seq_010，sizeof的（seq_010）/的sizeof（seq_010 [0]）}，
{seq_011，sizeof的（seq_011）/的sizeof（seq_011 [0]）}，
{seq_012，sizeof的（seq_012）/的sizeof（seq_012 [0]）}，
{seq_013，sizeof的（seq_013）/的sizeof（seq_013 [0]）}，
{seq_014，sizeof的（seq_014）/的sizeof（seq_014 [0]）}，
{seq_015，sizeof的（seq_015）/的sizeof（seq_015 [0]）}，
{seq_016，sizeof的（seq_016）/的sizeof（seq_016 [0]）}，
{seq_017，sizeof的（seq_017）/的sizeof（seq_017 [0]）}，
{seq_018，sizeof的（seq_018）/的sizeof（seq_018 [0]）}，
{seq_019，sizeof的（seq_019）/的sizeof（seq_019 [0]）}，
{seq_020，sizeof的（seq_020）/的sizeof（seq_020 [0]）}，
{seq_021，sizeof的（seq_021）/的sizeof（seq_021 [0]）}，
{seq_022，sizeof的（seq_022）/的sizeof（seq_022 [0]）}，
{seq_023，sizeof的（seq_023）/的sizeof（seq_023 [0]）}，
};
枚举{NUM_TESTS = sizeof的（测试）/ sizeof的（测试[0]）}; *计数器= 0;
如果（范围！= 0）
{
为const char * PTR =范围;
为const char * NXT;
罗长;
长喜;
而（（NXT = parse_range（PTR，和放大器;不料，＆安培;！喜））= 0）
{
如果（NXT == PTR）
err_error（无效的字符串范围（％S）\\ n，范围）;
如果（高== 0）
HI = NUM_TESTS-1;
为（长I = LO; I＆LT; =您好;我++）
{
（*计数器）++;
如果（test_sequence（测试[I]）== FALSE）
{
的printf（测试％LD：失败\\ n，I）;
失败++;
}
}
PTR = NXT;
}
}
其他
{
用于（为size_t我= 0; I＆LT; NUM_TESTS;我++）
{
（*计数器）++;
如果（test_sequence（测试[I]）== FALSE）
{
的printf（测试％LD：失败\\ n，I）;
失败++;
}
}
} 返回失败;
}静态为size_t random_tests（为size_t种子，为size_t号，为size_t MAXSIZE）
{
SIZE_T失败= 0;
函数srand（种子）;
的printf（种子：％祖\\ n，种子）; 用于（为size_t我= 0; I＆LT;数;我++）
{
t检验;
t.size =兰特（）％MAXSIZE;
t.data =的malloc（t.size * sizeof的（* t.data））;
如果（t.data == 0）
{
fprintf中（标准错误，内存不足的\\ n）;
出口（1）;
}
如果（详细）
的printf（测试：％祖（祖％）\\ n，我，t.size）;
用于（为size_t J = 0; J＆LT; t.size; J ++）
t.data [J] =兰特（）％3;
如果（test_sequence（T）== FALSE）
{
失败++;
打破;
}
}
返回失败;
}INT主（INT ARGC，字符** argv的）
{
静态字符常量optstr [] =DFM：N：○：RS：T：VW
静态字符常量usestr [] =[-dfrvw] [ - 米MAXSIZE] [ - N号] [ - 后裔] [ - t检验];
字符常量*范围= 0;
无符号的种子=时间（0）;
为size_t数= 1000;
为size_t MAXSIZE = 100;
bool的固定=真;
布尔随机= TRUE;
INT选择; err_setarg0（的argv [0]）; 而（（选择= getopt的（ARGC，ARGV，optstr））！= -1）
{
开关（OPT）
{
案D：
db_setdebug（1）;
详细= 1;
打破;
案例'F'：
固定= FALSE;
打破;
案件的m：
MAXSIZE = strtoul将（OPTARG，0，0）;
打破;
案例'N'：
数= strtoul将（OPTARG，0，0）;
打破;
案例'R'：
随机= FALSE;
打破;
案件的：
种子=的atoi（OPTARG）;
打破;
案例'T'：
范围= OPTARG;
打破;
案例'V'：
详细= TRUE;
打破;
案W：
WFLAG = TRUE;
打破;
默认：
err_usage（usestr）;
打破;
}
}
如果（OPTIND！= ARGC）
err_usage（usestr）; SIZE_T失败= 0; 如果（固定）
{
为size_t计数器;
失败= fixed_tests（范围，＆安培;计数器）;
的printf（失败：在％祖固定测试\\ n％俎，失败，计数器）;
}
如果（故障== 0安培;＆安培;随机）
{
失败= random_tests（种子数，MAXSIZE）;
的printf（失败：在％祖抽查\\ n％俎，失败，数）;
} 返回0;
}
示例输出：
前：（3）W，; B R
后：（3）W，; B R
之前：（3）W，W W
后：（3）W，W W
之前：（3）R R R
后：（3）R R R
之前：（3）B B B
后：（3）B B B
之前：（3）R BW¯¯
后：（3）W，; B R
之前：（7）W W R R B BW¯¯
后：（7）W，W W B B R R
之前：（11）B B W W R R B B W B乙
后：（11）W W W B B B B B B R R
之前：（2）W B
后：（2）W B
之前：（7）B B R R W W R
后：（7）W W B B R R R
之前：（5）乙; B R W R
后：（5）W，B B R R
前：（27）R; B R W R R B W R; B R B B R B W B W W W W R R R R BW¯¯
后：（27）W W W W W W W W B B B B B B B B R R R R R R R R R R R
前：（41）W W RW¯¯R B R B W B R R R W R R B B B R R B B W W R W B R B W R W W R W B R R RW¯¯
后：（41）W W W W W W W W W W W W W B B B B B B B B B B B R R R R R R R R R R R R R R R R R
之前：（3）R W R
后：（3）W，R R
之前：（2）RW¯¯
后：（2）W R
之前：（2）R B
后：（2）; B R
之前：（2）R R
后：（2）R R
之前：二（乙）W¯¯
后：（2）W B
之前：（2）B B
后：（2）B B
之前：（2）; B R
后：（2）; B R
之前：（2）W W
后：（2）W W
之前：（2）W R
后：（2）W R
之前：（4）R W RW¯¯
后：（4）W W R R
前：（9）R W RW¯¯R R W WW¯¯
后：（9）W W W W W R R R R
失败：0 23固定测试
种子：1385363222
测试：0（0）
之前：（0）
之后：（0）
测试：1（7）
前：（7）W B W R W RW¯¯
后：（7）W，W W W B R R
测试：2（1）
之前：（一）乙
后：（一）乙
测试：3（4）
之前：（4）乙R RW¯¯
后：（4）W B R R
试验：4（3）
之前：（3）R RW¯¯
后：（3）W，R R
试验：5（8）
前：（8）R W R B BW¯¯W B
后：（8）W W W B B B R R
测试：6（3）
之前：（3）B R R
后：（3）B R R
测试：7（7）
之前：（7）W B W R W WW¯¯
后：（7）W，W W W W; B R
测试：8（4）
之前：（4）W B W W
后：（4）W W W B
测试：9（0）
之前：（0）
之后：（0）
测试：10（6）
之前：（6）R R R W BW¯¯
后：（6）W，W B R R R
测试：11（3）
之前：（3）R W W
后：（3）W W R
测试：12（5）
之前：（5）W B W R乙
后：（5）W，W B; B R
测试：13（7）
之前：（7）R B R B W R乙
后：（7）W B B B R R R
测试：14（5）
之前：（5）W W R R B
后：（5）W，W B R R
测试：15（3）
之前：（3）W，B B
后：（3）W，B B
测试：16（5）
之前：（5）R B W W R
后：（5）W，W B R R
测试：17（3）
之前：（3）B W B
后：（3）W，B B
测试：18（2）
之前：（2）R B
后：（2）; B R
测试：19（9）
之前：（9）R; B R W B R B W R
后：（9）W W B B B R R R R
失败：0在20个随机试验
它已经经过了几百万的随机测试运行。
This is an interview question: Given an array with 3 kind of objects white,red,black - one should implement the sorting of the array ,such that it will look: {white}*{black}*{red}*. The interwier said - "you can`t use counting sort".His hint was to think about some quick - sort related technique.So I proposed to use a patition which is like quick - sort partition.He just required to use swap only once for each array`s element.I don`t know how to do it....Any advices ?(I am not sure if it is possible at all) My solution:
typedef enum {WHITE,BLACK,RED} color;
void swap (color* p1,color* p2)
{
color tmp;
tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void sort3(color* arr,unsigned int n)
{
unsigned int w = 0,r = n - 1,i = 0;
while (i <= r)
{
while (arr[w] == WHITE)
{
w++;
}
while (arr[r] == RED)
{
r--;
}
i = (w > i)? w :i;
switch (arr [i])
{
case WHITE:
swap(arr + i, arr + w);
w++;
break;
case RED:
{
swap(arr + i,arr + r);
r--;
if (arr [i] == WHITE)
{
swap(arr + i,arr + w);
w++;
}
break;
}
}
i++;
}
}
解决方案
You start with an array with an empty section of 'known to be white' values, an initially large section of 'unknown' values, and an empty section of 'known to be red' values.
First:
- Establish the size of the 'known to be white' section by counting the number of leading white values.
- Establish the size of the 'known to be red' section by counting the number of trailing red values.
It is fine if either size is zero; you just need to know what the size is.
You can step through the 'unknown' section one value at a time:
- If the next value is red, swap it with the value before the last 'known to be red' value, extending that section.
- If the next value is white, swap it with the value after the last 'known to be white' value, extending that section.
- Otherwise, leave it where it is.
- Restablish the 'known to be white' and 'known to be red' sections.
When the loop finishes, all the white objects are at the start, all the red objects are at the end, and the black objects must be in the middle.
Note that the order of the tests is important (and reversed from the original version of this code). As Yakov points out in his comment, in the scenario where the current value is red and the value before the 'known to be red' section is white, the first test moves the red to the 'known to be red' section but moves a white into the current position. You then have to check whether the current position is white and move it.
If this is too many swaps, have fun working out how to do it another way.
This code seems to work. It has rather extensive self-checking and testing. The full debug code is available on request (GPL v3).
/* SO 20164204 */
#define DEBUG
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include "range.h"
#include "stderr.h"
#include "debug.h"
typedef enum { WHITE, BLACK, RED } Colour;
static char colour_code(Colour c);
static void trace_colours(FILE *fp, char const *tag, Colour *data, unsigned num, size_t w, size_t r, size_t c);
static void swap(Colour *p1, Colour *p2)
{
Colour tmp;
tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
static void partition3(size_t n, Colour *arr)
{
if (n <= 1)
return;
size_t w = 0;
size_t r = n;
DB_TRACE(1, "\nw0 = %zu; r0 = %zu: ", w, r);
while (w < r && arr[w] == WHITE)
w++;
while (r > w && arr[r-1] == RED)
r--;
DB_TRACE(1, "w1 = %zu; r1 = %zu\n", w, r);
for (size_t i = w; i < r; i++)
{
DB_TRACE(1, "i = %2zu [1] w = %2zu, r = %2zu, c = %c", i, w, r, colour_code(arr[i]));
DB_CALL(1, trace_colours(stderr, "", arr, n, w, r, i));
if (arr[i] == RED)
{
swap(&arr[i], &arr[--r]);
DB_TRACE(1, "i = %2zu [2] w = %2zu, r = %2zu, c = %c", i, w, r, colour_code(arr[i]));
DB_CALL(1, trace_colours(stderr, "", arr, n, w, r, i));
}
if (arr[i] == WHITE)
{
swap(&arr[i], &arr[w++]);
DB_TRACE(1, "i = %2zu [3] w = %2zu, r = %2zu, c = %c", i, w, r, colour_code(arr[i]));
DB_CALL(1, trace_colours(stderr, "", arr, n, w, r, i));
}
while (r > w && arr[r-1] == RED)
r--;
while (w < r && arr[w] == WHITE)
w++;
if (i < w && w > 0)
i = w - 1;
}
}
/* DEBUGGING and TEST infrastructure */
static char const *colour_name(Colour c)
{
return(c == WHITE ? "WHITE" : c == RED ? "RED" : "BLACK");
}
static char colour_code(Colour c)
{
return(c == WHITE ? 'W' : c == RED ? 'R' : 'B');
}
static void print_colours(FILE *fp, char const *tag, Colour *data, size_t num)
{
fprintf(fp, "%s: (%zu)", tag, num);
for (size_t i = 0; i < num; i++)
fprintf(fp, " %c", colour_code(data[i]));
putc('\n', fp);
}
static void dump_colours(char const *tag, Colour *data, size_t num)
{
print_colours(stdout, tag, data, num);
}
static void trace_colours(FILE *fp, char const *tag, Colour *data, unsigned num, size_t w, size_t r, size_t c)
{
assert(w <= r);
assert(r <= num);
fprintf(fp, "%s: ", tag);
for (unsigned i = 0; i < num; i++)
{
char pad = ' ';
if (i == w || i == r)
pad = '|';
if (i == c)
pad = '[';
if (i == c+1)
pad = ']';
fprintf(fp, "%c%c", pad, colour_code(data[i]));
}
if (c == num - 1)
putc(']', fp);
else if (r == num || w == num)
putc('|', fp);
putc('\n', fp);
}
static Colour *dup_sequence(size_t n, Colour const *a)
{
Colour *d = malloc(n * sizeof(*d));
if (d == 0)
{
fprintf(stderr, "Out of memory\n");
exit(1);
}
for (size_t i = 0; i < n; i++)
d[i] = a[i];
return d;
}
static bool is_invalid_sequence(size_t n, Colour *a, bool report)
{
bool rc = false;
size_t w;
for (w = 0; w < n; w++)
{
if (a[w] != WHITE)
break;
}
size_t b;
for (b = w; b < n; b++)
{
if (a[b] == WHITE)
{
if (report)
{
fprintf(stderr, "Error: %c out of position (%zu)", colour_code(a[b]), b);
print_colours(stderr, "", a, n);
}
rc = true;
}
if (a[b] != BLACK)
break;
}
size_t r;
for (r = b; r < n; r++)
{
if (a[r] != RED)
{
if (report)
{
fprintf(stderr, "Error: %c out of position (%zu)", colour_code(a[r]), r);
print_colours(stderr, "", a, n);
}
rc = true;
}
}
return rc;
}
static size_t seqno = 0;
static bool wflag = false;
static bool verbose = false;
typedef struct Test
{
Colour *data;
size_t size;
} Test;
static void write_sequence(size_t seq, size_t n, Colour *a)
{
size_t i;
printf("Colour seq_%03zu[] =\n{\n", seq);
for (i = 0; i < n; i++)
{
printf(" %s,", colour_name(a[i]));
if (i % 10 == 9)
putchar('\n');
}
if (i %10 != 0)
putchar('\n');
printf("};\n");
}
static bool test_sequence(Test t)
{
bool rc = true;
size_t n = t.size;
Colour *a = t.data;
Colour *d = dup_sequence(n, a);
if (verbose)
dump_colours("Before", a, n);
partition3(n, d);
if (verbose)
dump_colours("After ", d, n);
if (is_invalid_sequence(n, d, false))
{
if (!verbose)
dump_colours("Before", a, n);
is_invalid_sequence(n, d, true);
if (!verbose)
dump_colours("After ", d, n);
if (wflag)
write_sequence(++seqno, n, a);
rc = false;
}
free(d);
return rc;
}
static size_t fixed_tests(char const *range, size_t *counter)
{
size_t fail = 0;
Colour seq_001[] = { WHITE, BLACK, RED };
Colour seq_002[] = { WHITE, WHITE, WHITE };
Colour seq_003[] = { RED, RED, RED };
Colour seq_004[] = { BLACK, BLACK, BLACK };
Colour seq_005[] = { RED, BLACK, WHITE };
Colour seq_006[] = { WHITE, WHITE, RED, RED, BLACK, BLACK, WHITE };
Colour seq_007[] =
{
BLACK, BLACK, WHITE, WHITE, RED, RED, BLACK, BLACK, WHITE,
BLACK, BLACK,
};
Colour seq_008[] = { WHITE, BLACK };
Colour seq_009[] = { BLACK, BLACK, RED, RED, WHITE, WHITE, RED };
Colour seq_010[] = { BLACK, BLACK, RED, WHITE, RED };
Colour seq_011[] =
{
RED, BLACK, RED, WHITE, RED, RED, BLACK, WHITE, RED, BLACK, RED,
BLACK, BLACK, RED, BLACK, WHITE, BLACK, WHITE, WHITE, WHITE,
WHITE, RED, RED, RED, RED, BLACK, WHITE
};
Colour seq_012[] =
{
WHITE, WHITE, RED, WHITE, RED, BLACK, RED, BLACK, WHITE, BLACK,
RED, RED, RED, WHITE, RED, RED, BLACK, BLACK, BLACK, RED, RED,
BLACK, BLACK, WHITE, WHITE, RED, WHITE, BLACK, RED, BLACK,
WHITE, RED, WHITE, WHITE, RED, WHITE, BLACK, RED, RED, RED,
WHITE,
};
Colour seq_013[] = { RED, WHITE, RED, };
Colour seq_014[] = { RED, WHITE, };
Colour seq_015[] = { RED, BLACK, };
Colour seq_016[] = { RED, RED, };
Colour seq_017[] = { BLACK, WHITE, };
Colour seq_018[] = { BLACK, BLACK, };
Colour seq_019[] = { BLACK, RED, };
Colour seq_020[] = { WHITE, WHITE, };
Colour seq_021[] = { WHITE, RED, };
Colour seq_022[] = { RED, WHITE, RED, WHITE, };
Colour seq_023[] =
{
RED, WHITE, RED, WHITE, RED, RED, WHITE, WHITE, WHITE,
};
Test tests[] =
{
{ seq_001, sizeof(seq_001)/sizeof(seq_001[0]) },
{ seq_002, sizeof(seq_002)/sizeof(seq_002[0]) },
{ seq_003, sizeof(seq_003)/sizeof(seq_003[0]) },
{ seq_004, sizeof(seq_004)/sizeof(seq_004[0]) },
{ seq_005, sizeof(seq_005)/sizeof(seq_005[0]) },
{ seq_006, sizeof(seq_006)/sizeof(seq_006[0]) },
{ seq_007, sizeof(seq_007)/sizeof(seq_007[0]) },
{ seq_008, sizeof(seq_008)/sizeof(seq_008[0]) },
{ seq_009, sizeof(seq_009)/sizeof(seq_009[0]) },
{ seq_010, sizeof(seq_010)/sizeof(seq_010[0]) },
{ seq_011, sizeof(seq_011)/sizeof(seq_011[0]) },
{ seq_012, sizeof(seq_012)/sizeof(seq_012[0]) },
{ seq_013, sizeof(seq_013)/sizeof(seq_013[0]) },
{ seq_014, sizeof(seq_014)/sizeof(seq_014[0]) },
{ seq_015, sizeof(seq_015)/sizeof(seq_015[0]) },
{ seq_016, sizeof(seq_016)/sizeof(seq_016[0]) },
{ seq_017, sizeof(seq_017)/sizeof(seq_017[0]) },
{ seq_018, sizeof(seq_018)/sizeof(seq_018[0]) },
{ seq_019, sizeof(seq_019)/sizeof(seq_019[0]) },
{ seq_020, sizeof(seq_020)/sizeof(seq_020[0]) },
{ seq_021, sizeof(seq_021)/sizeof(seq_021[0]) },
{ seq_022, sizeof(seq_022)/sizeof(seq_022[0]) },
{ seq_023, sizeof(seq_023)/sizeof(seq_023[0]) },
};
enum { NUM_TESTS = sizeof(tests) / sizeof(tests[0]) };
*counter = 0;
if (range != 0)
{
const char *ptr = range;
const char *nxt;
long lo;
long hi;
while ((nxt = parse_range(ptr, &lo, &hi)) != 0)
{
if (nxt == ptr)
err_error("invalid range string (%s)\n", range);
if (hi == 0)
hi = NUM_TESTS-1;
for (long i = lo; i <= hi; i++)
{
(*counter)++;
if (test_sequence(tests[i]) == false)
{
printf("Test %ld: Failed\n", i);
fail++;
}
}
ptr = nxt;
}
}
else
{
for (size_t i = 0; i < NUM_TESTS; i++)
{
(*counter)++;
if (test_sequence(tests[i]) == false)
{
printf("Test %ld: Failed\n", i);
fail++;
}
}
}
return fail;
}
static size_t random_tests(size_t seed, size_t number, size_t maxsize)
{
size_t fail = 0;
srand(seed);
printf("Seed: %zu\n", seed);
for (size_t i = 0; i < number; i++)
{
Test t;
t.size = rand() % maxsize;
t.data = malloc(t.size * sizeof(*t.data));
if (t.data == 0)
{
fprintf(stderr, "Out of memory\n");
exit(1);
}
if (verbose)
printf("Test: %zu (%zu)\n", i, t.size);
for (size_t j = 0; j < t.size; j++)
t.data[j] = rand() % 3;
if (test_sequence(t) == false)
{
fail++;
break;
}
}
return fail;
}
int main(int argc, char **argv)
{
static char const optstr[] = "dfm:n:o:rs:t:vw";
static char const usestr[] = "[-dfrvw][-m maxsize][-n number][-s seed][-t tests]";
char const *range = 0;
unsigned seed = time(0);
size_t number = 1000;
size_t maxsize = 100;
bool fixed = true;
bool random = true;
int opt;
err_setarg0(argv[0]);
while ((opt = getopt(argc, argv, optstr)) != -1)
{
switch (opt)
{
case 'd':
db_setdebug(1);
verbose = 1;
break;
case 'f':
fixed = false;
break;
case 'm':
maxsize = strtoul(optarg, 0, 0);
break;
case 'n':
number = strtoul(optarg, 0, 0);
break;
case 'r':
random = false;
break;
case 's':
seed = atoi(optarg);
break;
case 't':
range = optarg;
break;
case 'v':
verbose = true;
break;
case 'w':
wflag = true;
break;
default:
err_usage(usestr);
break;
}
}
if (optind != argc)
err_usage(usestr);
size_t fail = 0;
if (fixed)
{
size_t counter;
fail = fixed_tests(range, &counter);
printf("Failures: %zu in %zu fixed tests\n", fail, counter);
}
if (fail == 0 && random)
{
fail = random_tests(seed, number, maxsize);
printf("Failures: %zu in %zu random tests\n", fail, number);
}
return 0;
}
Sample output:
Before: (3) W B R
After : (3) W B R
Before: (3) W W W
After : (3) W W W
Before: (3) R R R
After : (3) R R R
Before: (3) B B B
After : (3) B B B
Before: (3) R B W
After : (3) W B R
Before: (7) W W R R B B W
After : (7) W W W B B R R
Before: (11) B B W W R R B B W B B
After : (11) W W W B B B B B B R R
Before: (2) W B
After : (2) W B
Before: (7) B B R R W W R
After : (7) W W B B R R R
Before: (5) B B R W R
After : (5) W B B R R
Before: (27) R B R W R R B W R B R B B R B W B W W W W R R R R B W
After : (27) W W W W W W W W B B B B B B B B R R R R R R R R R R R
Before: (41) W W R W R B R B W B R R R W R R B B B R R B B W W R W B R B W R W W R W B R R R W
After : (41) W W W W W W W W W W W W W B B B B B B B B B B B R R R R R R R R R R R R R R R R R
Before: (3) R W R
After : (3) W R R
Before: (2) R W
After : (2) W R
Before: (2) R B
After : (2) B R
Before: (2) R R
After : (2) R R
Before: (2) B W
After : (2) W B
Before: (2) B B
After : (2) B B
Before: (2) B R
After : (2) B R
Before: (2) W W
After : (2) W W
Before: (2) W R
After : (2) W R
Before: (4) R W R W
After : (4) W W R R
Before: (9) R W R W R R W W W
After : (9) W W W W W R R R R
Failures: 0 in 23 fixed tests
Seed: 1385363222
Test: 0 (0)
Before: (0)
After : (0)
Test: 1 (7)
Before: (7) W B W R W R W
After : (7) W W W W B R R
Test: 2 (1)
Before: (1) B
After : (1) B
Test: 3 (4)
Before: (4) B R R W
After : (4) W B R R
Test: 4 (3)
Before: (3) R R W
After : (3) W R R
Test: 5 (8)
Before: (8) R W R B B W W B
After : (8) W W W B B B R R
Test: 6 (3)
Before: (3) B R R
After : (3) B R R
Test: 7 (7)
Before: (7) W B W R W W W
After : (7) W W W W W B R
Test: 8 (4)
Before: (4) W B W W
After : (4) W W W B
Test: 9 (0)
Before: (0)
After : (0)
Test: 10 (6)
Before: (6) R R R W B W
After : (6) W W B R R R
Test: 11 (3)
Before: (3) R W W
After : (3) W W R
Test: 12 (5)
Before: (5) W B W R B
After : (5) W W B B R
Test: 13 (7)
Before: (7) R B R B W R B
After : (7) W B B B R R R
Test: 14 (5)
Before: (5) W W R R B
After : (5) W W B R R
Test: 15 (3)
Before: (3) W B B
After : (3) W B B
Test: 16 (5)
Before: (5) R B W W R
After : (5) W W B R R
Test: 17 (3)
Before: (3) B W B
After : (3) W B B
Test: 18 (2)
Before: (2) R B
After : (2) B R
Test: 19 (9)
Before: (9) R B R W B R B W R
After : (9) W W B B B R R R R
Failures: 0 in 20 random tests
It's been run through a few million random tests.
这篇关于排序基于分区（如在快速排序）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
