Standard sorting networks for small values of n

user_379897 0
Viewed 4422

I'm looking for a sorting network implementation of a 5-element sort, but since I couldn't find a good reference on SO, I'd like to ask for sorting networks for all small values of n, at least n=3 through n=6 but higher values would be great too. A good answer should at least list them as sequences of "swap" (sort on 2 elements) operations, but it might also be nice to see the recursive decomposition in terms of lower-order sorting networks.

For my application, I actually only care about the median of 5 elements, not actually putting them in order. That is, the order of the other 4 elements may be unspecified in the result as long as the median ends up in the right place. Can a sorting-networks-related approach be used to compute the median with fewer swaps than performing a full sort? If so, such a solution to my problem (for n=5) and for other cases would make a great answer too.

(Note: I've tagged this question C because C is the language I use and I suspect people who follow the C tag have good answers, but I don't really care if an answer is actually written in C versus pseudo-code as long as it easily translates to C, which it should naturally do as long as the above-mentioned criteria are met.)

sorting-network median sorting c
3 Answers

The asker was specifically interested in a median-of-5 implementation based on sorting networks, so I will address this specific case. A brief review of the literature indicates what optimal solutions look like according to various metrics.

Michael Codish, Luís Cruz-Filipe, Thorsten Ehlers, Mike Müller, and Peter Schneider-Kamp. "Sorting networks: to the end and back again." Journal of Computer and System Sciences (2016) in table 1 shows that for n=5, the minimal number of compare-swaps is 9, and the minimal depth of the network is 5. As each compare-swap is equivalent to two min/max operations, the minimal number of min/max operations required is 18.

Lukáŝ Sekanina, "Evolutionary Design Space Exploration for Median Circuits". In: EvoWorkshops, March 2004, pp. 240-249, gives the minimal number of min / max operations required for an optimal five-input median-selection network as 10 in table 1.

William Gasarch, Wayne Kelly, and William Pugh. "Finding the i th largest of n for small i, n." ACM SIGACT News 27, no. 2 (1996): 88-96, table 1: at least 6 comparisons are needed for median-of-5.

In general, sorting networks with the minimal number of operations do not reduce to median-selection networks with the minimal number of operations simply by the elimination of redundant operations. But it is possible to find networks that do reduce in optimal fashion for at least some values of n. For n=5, a brute-force search for such networks is feasible.

The code below shows for four variants of five-input sorting networks comprising nine compare-swap operations or, alternatively, 18 min / max operations. When compiled with FULL_SORT = 0 these turn into median-selection networks with 10 min/max operations. So according to this metric, both sorting and median selection are optimal.

However, when used as a sorting network, all four variants have a depth of six instead of the minimum of five. Also, when configured as a median-selection network based on comparisons instead of min / max operations, all require seven rather than the minimum of six comparisons.

Example compilation results from Compiler Explorer (godbolt): Using 18 min / max operations for five-input sort, using 10 min / max operations for five-input median.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define VARIANT       1
#define USE_MIN_MAX   1
#define FULL_SORT     0

typedef float T;

#if USE_MIN_MAX
#define MIN(a,b) ((T)(fmin(a,b)))
#define MAX(a,b) ((T)(fmax(a,b)))
#define SWAP(i,j) do { T s = MIN(a##i,a##j); T t = MAX(a##i,a##j); a##i = s; a##j = t; } while (0)
#else // USE_MIN_MAX
#define MIN(a,b) (((a) > (b)) ? (b) : (a))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define SWAP(i,j) do { if (a##i > a##j) { T temp = a##i; a##i = a##j; a##j = temp; }} while (0)
#endif // USE_MIN_MAX

/* Use sorting/median network to fully or partially sort array of five values
   and return the median value
*/
T network5 (T *a)
{
    // copy to scalars
    T a0, a1, a2, a3, a4;
    a0=a[0];a1=a[1];a2=a[2];a3=a[3];a4=a[4];

#if VARIANT == 1
   SWAP (0, 1);  SWAP (2, 3);
   SWAP (0, 2);  SWAP (1, 3);
   SWAP (2, 1);
   SWAP (1, 4);
   SWAP (1, 2);
   SWAP (0, 1);  SWAP (3, 4);
#elif VARIANT == 2
    SWAP (3, 4);  SWAP (0, 2);
    SWAP (2, 4);  SWAP (0, 3);
    SWAP (2, 3);
    SWAP (1, 2);
    SWAP (0, 1);  SWAP (2, 3);
    SWAP (3, 4);
#elif VARIANT == 3
    SWAP (3, 2);  SWAP (0, 4);
    SWAP (2, 4);  SWAP (0, 3);
    SWAP (2, 3);
    SWAP (1, 2);
    SWAP (0, 1);  SWAP (2, 3);
    SWAP (3, 4);
#elif VARIANT == 4 
    SWAP (2, 4);  SWAP (0, 1);
    SWAP (0, 2);  SWAP (1, 4);
    SWAP (2, 3);
    SWAP (1, 2);
    SWAP (2, 3);  SWAP (0, 1);
    SWAP (3, 4);
#else
#error unsupported VARIANT
#endif

#if FULL_SORT
    // copy back sorted results
    a[0]=a0;a[1]=a1;a[2]=a2;a[3]=a3;a[4]=a4;
#endif
    // return median-of-5
    return a2;
}
user_7807170
Related