Sorting Networks(SN) validity


Daniel G O'Connor et al. patented in 1945 the idea of an ordering system with n-line through exchanges in electronic devices [1]. This works consisted in ordering elements that arrived through the buses, considering the same amount of input elements as the output of the device, among the advantages that were identified with the technique was the saving of operations when ordering a set of data, due to the above, the principle of a Sorting Network was born.

Also, the operations that integrate a SN are known as comparators. Comparison and interchange among two elements are the operations performed by a comparator. Thus, if a comparator that receives the elements (x0,y1) to be ordered, this means that x0 must not be larger than x1. Hence, after introducing a given size n list and go through by set of comparators, then output should be a monotonically non decreasing ordered list. The SN are called oblivious, that means that their comparisons are independent of the preceding comparators and input data [1][2].

In order to verify the Sorting Networks(SN) validity, it really sorts any input configuration, it is necessary to evaluate all the n! possible permutations. However, the Theorem Zero-One is used to verify the SN validity, reducing the number of evaluations [2]. This theorem affirms that, a SN is able to order any list of n elements not regulated, whenever it is able to order binary strings in a non-decreasing order.

In this place it is possible to validate a network using the theorem. The implementation was programmed in C language and is capable of evaluating networks up to n = 16.

Validity .....

To validate a Sorting Network, first place the data size to sort in this space


Then, in a comma separated list all comparators are placed, starting with the total number of comparators. For example, a sorting network to n = 4, this has 5 comparators, the list should be placed as follows: 5,1,3,0,2,2,3,0,1,1,2

SN to order n = 4

[1] Nelson Raymond J. O’Connor, Daniel G. Sorting system with n-line sorting switch. United States Patent number 3,029,413, 6, April 1962.
[2] Donald E. Knuth. The Art of Computer Programming, Volume 3: (2Nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998.