Class SortingNetwork

doc/code/tutorials/part_4/sortingnetwork.py:29–127

Sorting network class. From Wikipedia : A sorting network is an abstract mathematical model of a network of wires and comparator modules that is used to sort a sequence of numbers. Each comparator connects two wires and sort the values by outputting the smaller value to one wire, an

            yield tuple(prod)

class SortingNetwork(list):
    """Sorting network class.

    From Wikipedia : A sorting network is an abstract mathematical model
    of a network of wires and comparator modules that is used to sort a
    sequence of numbers. Each comparator connects two wires and sort the
    values by outputting the smaller value to one wire, and a larger
    value to the other.
    """
    def __init__(self, dimension, connectors = []):
        self.dimension = dimension
        for wire1, wire2 in connectors:
            self.addConnector(wire1, wire2)

    def addConnector(self, wire1, wire2):
        """Add a connector between wire1 and wire2 in the network."""
        if wire1 == wire2:
            return

        if wire1 > wire2:
            wire1, wire2 = wire2, wire1

        try:
            last_level = self[-1]
        except IndexError:
            # Empty network, create new level and connector
            self.append({wire1: wire2})
            return

        for wires in last_level.items():
            if wires[1] >= wire1 and wires[0] <= wire2:
                self.append({wire1: wire2})
                return

        last_level[wire1] = wire2

    def sort(self, values):
        """Sort the values in-place based on the connectors in the network."""
        for level in self:
            for wire1, wire2 in level.items():
                if values[wire1] > values[wire2]:
                    values[wire1], values[wire2] = values[wire2], values[wire1]

    def assess(self, cases=None):
        """Try to sort the **cases** using the network, return the number of
        misses. If **cases** is None, test all possible cases according to
        the network dimensionality.
        """
        if cases is None:
            cases = product(range(2), repeat=self.dimension)

        misses = 0
        ordered = [[0]*(self.dimension-i) + [1]*i for i in range(self.dimension+1)]
        for sequence in cases:
            sequence = list(sequence)
            self.sort(sequence)
            misses += (sequence != ordered[sum(sequence)])
        return misses