[Sorting Networks] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


Sorting Networks

(Click here to view the original thread with full colors/images)


Posted by: VJ Perricelli

On p. 1142 of NKS, there is a discussion of sorting networks. Included in the discussion is a list of the total numbers of minimal (sorting) sequences existing for various numbers of inputs.

For 5 inputs, the number of distinct sequences is listed as 13,866. Does anyone have a source for that number and, ideally, a list of the sequences? I've come up with a different number (11,790) and would like to determine the source of the difference.

Thanks for any assistance!


Posted by: Todd Rowland

I've checked the sequences that were generated in the making of the book, and have attached them here. Not sure what the source of the discrepancy is.

This is an interesting problem, that is to find NKS applications to finding good methods of sorting. Or to study the behavior of sorting programs.

What is known about sequences which are not individually sorted?

For instance, a minimal sequence for length 4 (not counted) is
{{1, 4}, {3, 2}, {1, 3}, {2, 4}, {2, 3}} where at the second step, if items in slots 2 and 3 are sorted, they become unsorted.


Posted by: Todd Rowland

Attached is a graphc showing the occurences of the various pairs in the minimal sorts for size 5, where the top row are those on the first step, etc..

It turns out that {2,3} and {3,4} occur in all cases, as many as 3 times in each sequence of 9. Not surprisingly, the least used are {1,5} and {1,4}. The number of pairs which do not occur in any of the minimal sequences for each time step are {0, 0, 0, 0, 0, 0, 1, 3, 6}.


Posted by: VJ Perricelli

Todd,

Many thanks for posting the sequences! I'll take a look at them this evening and see if I can determine where the discrepancy lies.

As you've indicated, these sequences have some interesting properties. It can be easily proven that there must be at least one occurrence of each of {1,2}, {2,3}, {3,4}, and {4,5} in every minimal sorting sequence for 5 inputs.

Looking at the sequences I generated, I believe it's also the case that the last comparison in each minimal sorting sequence for 5 inputs must also be one of {1,2}, {2,3}, {3,4}, or {4,5}. (I'll see if that's also the case with the full set of sequences that you've provided.) While that feels intuitively right, I haven't had any success in actually proving it.

-Vince Perricelli


Posted by: Jason Cawley

Todd's package lets you just use Mathematica patterns and built in functions to answer all sorts of questions about these.

Just put the package somewhere on your path and read it in. The variable "data" now contains all the sequences. The rest is easy -

Length[Cases[data,{___,{4,5}}]]

2568

That many sequences have {4,5} as their last element.

Length[Cases[data,{___,{3,4}}]]

6246

Length[Cases[data,{___,{2,3}}]]

4413

Length[Cases[data,{___,{1,2}}]]

639

Which sum to 13866, so yes the statement is true in this set of sequences.

It is also trivial to get frequencies of particular pairs -

Table[Count[Map[Count[#,{3,4}]&,data],i],{i,0,5}]

{0,8444,4911,504,7,0}

No sequences occur without a {3,4}. In 7 of them it occurs 4 times.

Table[Count[Map[Count[#,{2,4}]&,data],i],{i,0,5}]

{3788,8269,1748,61,0,0}

3788 sequences lack the pairing {2,4}.

Etc. FWIW...


Posted by: VJ Perricelli

Jason,

Thank you very much for your response and the examples of Mathematica function usage.

I was careless in my choice of words when I wrote: "Looking at the sequences I generated, I believe ... that the last comparison in each minimal sorting sequence for 5 inputs must also be one of {1,2}, {2,3}, {3,4}, or {4,5}. ... I haven't had any success in actually proving it."

What I meant by "proving it" was developing a logical proof--independent of an enumeration of 5-input minimal sequences--that the final comparison in a 5-input minimal sequence must be one of {1,2}, {2,3}, {3,4}, or {4,5}.

Based on the minimal sorting sequences for 8 or fewer inputs that I've seen, I'm guessing that all minimal sequences must have a final comparison of the form {i, i+1}, where i is an integer such that 0 < i < n and n is the number of inputs to the sorting network. If anyone has a counterexample or a proof for n <= 8, I'd be interested in seeing it.

The point of such a proof (and other proofs about the characteristics of minimal sorting networks) would be a reduction in the search space that has to be considered for such networks. (The search space for 5-input networks is fairly easily explored, while that for 16-input networks is not.)

- Vince Perricelli




Forum Sponsored by Wolfram Research

© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings