From b1632a807fc2166da35bb6b59d60738d4db24627 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Tue, 22 Feb 2011 09:03:59 +0100 Subject: [PATCH] src/sn_network.c: Fix the Pairwise Sorting network for arbitrary n. Powers of two worked fine before. With this change the function generates valid sorting networks for arbitrary number of lines. For arbitrary n, PS(n) is not as efficient nor as fast as OES(n). --- src/sn_network.c | 18 +++++++++++++----- 1 file changed, 13 insertions(+), 5 deletions(-) diff --git a/src/sn_network.c b/src/sn_network.c index 98b89fa..90a86cf 100644 --- a/src/sn_network.c +++ b/src/sn_network.c @@ -223,17 +223,25 @@ static int sn_network_create_pairwise_internal (sn_network_t *n, /* {{{ */ inputs_copy[(int) (i / 2)] = inputs[i]; /* Recursive call #2 with second set of lines */ sn_network_create_pairwise_internal (n, inputs_copy, - (int) (inputs_num/ 2)); + (int) (inputs_num / 2)); /* m is the "amplitude" of the sorted pairs. This is a bit tricky to read due * to different indices being used in the paper, unfortunately. */ - m = inputs_num / 2; + m = (inputs_num + 1) / 2; while (m > 1) { - for (i = 1; (i + (m - 1)) < inputs_num; i += 2) + int len; + + /* len = ((int) ((m + 1) / 2)) * 2 - 1; */ + if ((m % 2) == 0) + len = m - 1; + else + len = m; + + for (i = 1; (i + len) < inputs_num; i += 2) { int left = i; - int right = i + (m - 1); + int right = i + len; sn_comparator_t *c; assert (left < right); @@ -242,7 +250,7 @@ static int sn_network_create_pairwise_internal (sn_network_t *n, /* {{{ */ sn_comparator_destroy (c); } - m = m / 2; + m = (m + 1) / 2; } /* while (m > 1) */ return (0); -- 2.11.0