Share
Explore BrainMass

Algorithm to determine the depth of a comparison network

Mr. Johnson draws an n-input comparison network with m comparators according to the following conventions.

The lines of the network go left-to-right, and comparators are drawn vertically to connect two lines. The network is drawn on an underlying grid, so that each comparator occupies one of at most m columns. Comparators can share columns, but they do not overlap.

Mr. Johnson represents a given drawing as a list L of triples, in which each triple (x, y, c) represents a comparator connecting line x to line y in column c.

Describe an efficient algorithm to determine the depth of a comparison network, where the input is Mr. Johnson's representation of a drawing of the network. Analyze your algorithm in terms of m and n.

Please look at the attachment for an example of his drawing and representation of a 4-input sorting network.

Attachments

Solution Preview

Let us first list out observations that are key to developing an efficient algorithm to determine the depth of a comparison network.

As each comparator can go in separate column, maximum number of columns possible in the given comparison network = m

Since comparators in a column operate in parallel, it allows us to process them in any order in that column, as far as our algorithm is concerned.

Given that -
- number of input lines = n
- number of comparators = m
- (x,y,c) represents a comparator connecting line x to line y in column c.
- L = list of comparators, representing the sorting network.

Since nothing is specified about the order of comparators in L, and given example also lists them in arbitrary order, this solution considers that L is simply specifying a collection of comparators that needs to be organised in certain order before computing the depth of network.

If contents of L is ...

Solution Summary

Solution describes an O(max{m,n}) algorithm to determine the depth of an n-input comparison network with m comparators, with pseudocode interspersed with detailed explanations and performance analysis of steps in algorithm.

$2.19