Sorting algorithms

Sorting networks

 German version  up

Basics

Definition:  Let J  = {0, ..., n-1} be an index set and let A be a set with an order relation <=. A data sequence is a mapping a : J arrow A, i.e. a sequence of length n of data. The set of all data sequences of length n over A is denoted by An.

Definition:  The sorting problem consists of reordering an arbitrary data sequence a0, ..., an-1,  ai element A to a data sequence aφ(0), ..., aφ(n-1) such that

aφ(i) <= aφ(j)   for   i < j

where φ is a permutation of the index set J  = {0, ..., n-1}.

This definition deals only with the simplest case of sorting a data sequence in ascending order. Later, when dealing with two-dimensional processor arrays, this definition has to be generalized by introducing an index set J = {0, ..., n-1}times{0, ..., n-1} and a sorting direction  ρ : J arrow {0, ..., |J|-1}.

 

Comparator networks

Comparator networks have been introduced informally in [Knu 73] for the case J = {0, ..., n-1}. A comparator [i:j] sorts the ith and the jth element of a data sequence into nondecreasing order. Formally, a comparator is a mapping applied to the data sequence:

Definition:  A comparator is a mapping [i:j] : An arrow An,  i, j element {0, ..., n-1} with

[i:j](a)i  =  min(ai, aj)

[i:j](a)j  =  max(ai, aj)

[i:j](a)k  =  ak  for all k  with  knot equaliknot equalj

for all a element An.

Figure 1 shows the graphical representation of a comparator network with comparators [1:3] and [2:1], applied to the data sequence 6 8  5 1.

Graphical representation of comparators
Figure 1:  Graphical representation of comparators

Definition:  A comparator stage S is a composition of comparators

S = [i1:j1]· ...· [ik:jk] ,   k element natural numbers

such that all ir and js are distinct (even the ir and js among each other).

Comparators within a comparator stage can be executed in parallel.

Definition:  A comparator network is a composition of comparator stages.

As an example, Figure 2 shows a comparator network with two stages.

A comparator network with two stages
Figure 2:  A comparator network with two stages

 

Sorting networks

Definition:  A sorting network is a comparator network that sorts all input sequences.

The comparator network of the example above is not a sorting network, since it does not sort the sequence 3 1 4 2.

The problem whether an arbitrary comparator network is a sorting network or not is not easy to solve in general. It is an NP-complete problem. Besides that, sorting networks can of course be constructed systematically and proved to be correct.

Sorting networks are special cases of general sorting algorithms, since all comparisons are data-independent.

An example of a sorting network is bubblesort:

Sorting network bubblesort
Figure 3:  Sorting network bubblesort

The sorting network bubblesort consists of a first diagonal of n-1 comparators that move the greatest element to the last position. The remaining n-1 elements are sorted recursively by applying the same procedure. Bubblesort consists of n·(n-1)/2 comparators, arranged in 2n – 3 stages.

A similar sorting network is odd-even transposition sort. For sorting n input elements, n·(n-1)/2 comparators but only n comparator stages are required. Each stage consists of comparators [ii+1] where i is odd or where i is even, in alternating order.

The main advantages of bubblesort and odd-even transposition sort are their simplicity and, important for hardware implementation, their locality and scalability. Locality means that comparators exist only between adjacent elements, scalability means that the structure does not change with size.

However, with an asymptotic complexitiy of Θ(n2) comparators bubblesort and odd-even transposition sort are rather inefficient.

The lower bound for the sorting problem is Ω(n log(n)). This bound is tight even for sorting networks, as shown in [AKS 83]. However, due to its large constant, the AKS-network is impractical. But there are practical sorting networks with a complexity of O(n·log(n)2) comparators: bitonic sort, odd-even mergesort and shellsort.

The following table summarizes the complexities of some sorting networks:

 

 comparator stages comparators
Odd-even transposition sort O(n) O(n2)
Bubblesort O(n) O(n2)
Bitonic sort O(log(n)2) O(n·log(n)2)
Odd-even mergesort O(log(n)2) O(n·log(n)2)
Shellsort O(log(n)2) O(n·log(n)2)

 

 

The 0-1-principle

Whether an arbitrary comparator network N is a sorting network or not is independent of the input set A. It just depends on the structure of N. The 0-1-principle essentially states this fact.

Theorem:  (0-1-principle)

A comparator network with n inputs that sorts all 2n sequences of zeroes and ones is a sorting network (i.e. it sorts all sequences of arbitrary values, too).

Proof of the 0-1-principle

The 0-1-principle is extremely useful for the proof of sorting networks.

 

References

[AKS 83]M. Ajtai, J. Komlos, E. Szemeredi: An O(n log n) Sorting Network. Proceedings of the 25th ACM Symposium on Theory of Computing, 1-9 (1983)
[Knu 73]D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)

 

 

Next:   [0-1-principle]   or   up del.icio.us digg.com Google Ma.gnolia Mister Wong StumbleUpon YahooMyWeb LinkARENA

 

homeH.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 05.03.1997   Updated: 18.05.2010
Valid HTML 4.01 Transitional