раздел на основе сортировки (как в быстрой сортировке)
Это вопрос интервью:
Для массива с тремя типами объектов: белым, красным и черным — следует реализовать сортировку массива так, чтобы он выглядел так:
{Белый} * {черный} * {красный} *.
Интервьюер сказал: «Вы не можете использовать сортировку подсчета». Его подсказка состояла в том, чтобы подумать о некоторой технике быстрой сортировки. Поэтому я предложил использовать патцию, которая похожа на раздел быстрой сортировки. Он просто должен был использовать swap только один раз. для каждого элемента массива. Я не знаю, как это сделать …. Любые советы? (Я не уверен, если это вообще возможно)
Мое решение:
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++;
}
}
Решение
Вы начинаете с массива с пустым разделом значений, «известных как белые», изначально большим разделом с «неизвестными» значениями и пустым разделом из «известных как красные» значений.
Первый:
- Определите размер «известного как белого» раздела, посчитав количество ведущих значений белого.
- Определите размер «известного как красного» раздела, посчитав количество концевых значений красного.
Хорошо, если любой размер равен нулю; вам просто нужно знать, какой размер.
Вы можете пройти по «неизвестному» разделу по одному значению за раз:
- Если следующее значение — красное, поменяйте его на значение перед последним значением «известно, что оно красное», расширяя этот раздел.
- Если следующее значение — белое, замените его на значение после последнего значения, известного как «белое», расширяя этот раздел.
- В противном случае, оставьте это там, где оно есть.
- Пересмотрите разделы «известно, что белые» и «известные как красные».
Когда цикл заканчивается, все белые объекты находятся в начале, все красные объекты находятся в конце, а черные объекты должны быть посередине.
Обратите внимание, что порядок тестов важен (и обратный от оригинальной версии этого кода). Как Яков указывает на его комментарий, в сценарии, где текущее значение красного цвета, а значение перед разделом «известно, что он красный» является белым, первый тест перемещает красный цвет в раздел «известно, что он красный», но перемещает белый цвет в текущую позицию. Затем вы должны проверить, является ли текущая позиция белым и переместить ее.
Если это слишком много свопов, получайте удовольствие, решая, как это сделать по-другому.
Этот код, кажется, работает. Имеет достаточно обширную самоконтроль и тестирование. Полный код отладки доступен по запросу (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;
}
Образец вывода:
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
Он прошел несколько миллионов случайных тестов.
Другие решения
Других решений пока нет …