StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>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.</p> <p>First:</p> <ul> <li>Establish the size of the 'known to be white' section by counting the number of leading white values.</li> <li>Establish the size of the 'known to be red' section by counting the number of trailing red values.</li> </ul> <p>It is fine if either size is zero; you just need to know what the size is.</p> <p>You can step through the 'unknown' section one value at a time:</p> <ul> <li>If the next value is red, swap it with the value before the last 'known to be red' value, extending that section.</li> <li>If the next value is white, swap it with the value after the last 'known to be white' value, extending that section.</li> <li>Otherwise, leave it where it is.</li> <li>Restablish the 'known to be white' and 'known to be red' sections.</li> </ul> <p>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.</p> <p>Note that the order of the tests is important (and reversed from the original version of this code). As <a href="https://stackoverflow.com/users/466056/yakov">Yakov</a> points out in his <a href="https://stackoverflow.com/questions/20164204/sorting-based-partition-like-in-quick-sort/20165129#comment30059837_20165129">comment</a>, 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.</p> <p><em>If this is too many swaps, have fun working out how to do it another way.</em></p> <p>This code seems to work. It has rather extensive self-checking and testing. The full debug code is available on request (GPL v3).</p> <pre><code>/* 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; } </code></pre> <p>Sample output:</p> <pre><code>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 </code></pre> <p>It's been run through a few million random tests.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload