Talk:Sorting network

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated C-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 

Updates[edit]

I'm doing some major updates to this article. The draft can be found at User:Oskar Sigvardsson/Sorting networks. More updates are coming. You got any questions, just ask --Oskar 00:26, 26 March 2008 (UTC)

Applications[edit]

Hello, can you tell me, if/where in practice sorting networks are used? Maybe an electrical engineer can affirm here that his company uses hardware chips in aircraft industry for sorting :) —Preceding unsigned comment added by 89.247.15.59 (talk) 15:07, 23 January 2010 (UTC)

The theory is also useful in software. Parallellism influences single-core computations, since you want to avoid dependencies between sequential computations. The static structure can allow an implementation without branches (jumps) as well. -- Sverdrup (talk) 11:08, 19 December 2011 (UTC)
I added a reference for the use in GPGPU, which means compiling a sorting net to CUDA or OpenCL code which is then executed on a GPU. QVVERTYVS (hm?) 15:48, 26 September 2014 (UTC)

Fourier / History[edit]

Isn't it true that sorting networks were invented by analyzing the steps in the FFT? Should this be in the history section? There is currently no history section. — Preceding unsigned comment added by 76.111.60.215 (talk) 23:26, 26 May 2011 (UTC)

There's a short remark in Batcher's 1968 paper that calls the reader's attention to a similarity with the FFT. QVVERTYVS (hm?) 13:32, 26 September 2014 (UTC)

Reverse comparators?[edit]

The examples all have the property that, for each comparator between wires i and j, if i < j then the smaller value goes to wire i and the greater value to j. But is this necessarily the case, either

  1. in order for it to be called a sorting network?
  2. in order for it to be optimal in size?
  3. in order for it to be optimal in depth?

Since there's no mention of this requirement I take it that this criterion isn't necessary for 1. But I can imagine that for some input sizes an optimal network might temporarily put some pairs of elements out of order. Has this been studied in depth? It would be good if we could find some information on it rather than ignoring the possibility as the article effectively does at the moment. — Smjg (talk) 15:19, 12 April 2014 (UTC)

This is not yet in the article, but sorting networks are comparison sorts. I.e. they have to order their inputs according to some total order. Networks that don't sort are called comparison networks by Cormen et al.. Non-sorting comparison networks include min/max-finding networks and median networks; there's some literature about this, but it's hard to find and poorly cited. I can dug up some references if you like.
Re: temporarily placing elements out of order, I've only just started reading up on sorting networks, but it seems like there's no requirement that a sorting net should sort its input incrementally, i.e. data should become "more sorted" over time (that notion can be made precise if needed, but I haven't encountered it in the context of sorting nets so far). QVVERTYVS (hm?) 13:38, 26 September 2014 (UTC)
The property is not actually a limitation. Any network of correctly connected comparators (i.e. a network where each signals has fan-in 1 and fan-out 1 and there are no oriented loops) can be redrawn as a network satisfying the condition, maybe with some permutation of outputs. To do the transformation, just assign already sorted values 1...n to inputs and compute all intermediate and output signals. Then if a comparator has inputs (and outputs) marked i and j, then draw it on the ith and jth wires, keeping the order of comparators. -- M. G. J. (talk) 04:19, 22 September 2015 (UTC)