Listing 2 Minimum comparison network pairs
/* 10 items - 29 comparisons; 9 - 25 */ int net10[29][2] = { {2,9},{1,5},{6,10},{3,7},{4,8},{1,4},{7,10},{3,6}, {1,2},{4,7},{9,10},{5,8},{1,3},{5,9),{2,6),{8,10}, {2,3},{4,5},{6,7},{8,9),{2,4},{7,9},{3,5},{6,8}, {3,4},{7,8},{4,6},{5,7},{5,6}}; /* 12 items - 39 comparisons; 11 - 35 */ int net12[39][2] = { {1,2},{3,4},{5,6},{7,8},{9,10},{11,12},{2,4},{6,8}, {10,12},{1,3},{5,7},{9,11},{2,3},{6,7},{10,11}, {2,6},{7,11},{6,10},{3,7},{2,6},{7,11},{1,5},{8,12}, {4,8},{5,9},{1,5},{8,12},{2,5},{8,11},{4,9},{3,4}, {9,10},{3,5},{8,10},{4,6},{7,9},{4,5},{6,7},{8,9}}; /* 16 items - 60 comparisons; 15 - 56; 14 - 51; 13 - 46 */ int net16[60][2] = { {1,2},{3,4},{5,6},{7,8},{9,10},{11,12},{13,14}, {15,16},{1,3},{5,7},{9,11},{13,15},{2,4},{6,8}, {10,12},{14,16},{1,5},{9,13},{2,6},{10,14},{3,7}, {11,15},{4,8},{12,16},{1,9},{2,10},{3,11},{4,12}, {5,13},{6,14},{7,15},{8,16},{6,11},{7,10},{4,13}, {8,12},{14,15},{2,3},{5,9},{2,5},{8,14},{3,9}, {12,15},{3,5},{6,7},{10,11},{12,14},{4,9},{8,13}, {7,9},{4,6},{8,10},{11,13},{4,5},{6,7},{8,9},{10,11}, {12,13},{7,8},{9,10}}; /* Extracts a network for n items from an array of * comparison pairs for m items when n <= m. Expects * the 2nd member of each pair to be the larger. For * example, to extract a minimum comparison network * for 9 items call * extract(9, sizeof(net10)/(2*sizeof(int)), net10); */ extract(n, m, network) int n, m; int network[][2]; { int i; for(i = 0; i < m; i += 1) { if(network[i][1] <= n) printf("swap(%d, %d);\n", network[i][0] , network[i][1]); } } /* End of File */