Lecture 6 Algorithm Analysis Arne Kutzner Hanyang University / Seoul Korea Sorting Networks Sorting Networks Example of Parallel Algorithms Not directly related to our classical computer models (e.g. Turing machines, von-Neumann architecture)

2016/10 Algorithm Analysis L6.3 Comparator wire Input wires Output wires

Works in O(1) time. 2016/10 Algorithm Analysis L6.4 Example of Comparison Network Input

Output Wires go straight, left to right. Each comparator has inputs/outputs on some pair of wires. 2016/10 Algorithm Analysis L6.5 Correctness of Example Network Claim that this comparison network will

sort any set of 4 input values: After leftmost comparators, minimum is on either wire 1 (from top) or 3, maximum is on either wire 2 or 4. After next 2 comparators, minimum is on wire 1, maximum on wire 4. Last comparator gets correct values onto wires 2 and 3. 2016/10 Algorithm Analysis L6.6

Definition of Depth Depth of some Wire: Input depth: dx Output depth: max (dx ,dy) + 1 Input depth: dy Input wires of the network have depth 0 Depth of a comparator := depth of its output wire Depth of a Network := maximum depth of a

an output wire of the network 2016/10 Algorithm Analysis L6.7 Depth - Example Depth 1 2016/10 Depth 2

Algorithm Analysis Depth 3 L6.8 Selection Sorter Foundation: Bouble-Sort Idea Find the maximum of 5 values: 2016/10 Algorithm Analysis

L6.9 Selection Sorter (cont.) We extend our idea: Selection Sorter for 4 elements Depth: 2016/10 Algorithm Analysis

L6.10 Zero-one principle How can we test if a comparison network sorts? We could try all n! permutations of input. But we will see that we need to test only 2n permutations. Theorem (0-1 principle) If a comparison network with n inputs sorts all 2n sequences of 0.s and 1.s, then it sorts all

sequences of arbitrary numbers. 2016/10 Algorithm Analysis L6.11 Important Lemma Lemma: If a comparison network transforms a = into b = , then for any monotonically increasing function f , it transforms

f(a) = into f(b) = . 2016/10 Algorithm Analysis L6.12 Proof of Lemma Important property: Then use induction on the depth of some wire

2016/10 Algorithm Analysis L6.13 Proof of 0-1 principle Suppose that the principle is not true, so that an n-input comparison network sorts all 0-1 sequences, but there is a sequence such that ai < aj but ai comes after aj in the output. Define the monotonically increasing function

2016/10 Algorithm Analysis L6.14 Proof 0-1 principle (cont.) By our lemma proven before: If we give the input , then in the output we will have f(ai) after f(aj)

But this results in an unsorted 0-1 sequence. A contradiction. 2016/10 Algorithm Analysis L6.15 Definition of the notion bitonic A sequence is bitonic if it monotonically increases, then monotonically decreases, or it can be circularly shifted to become so. Examples: <1, 3, 7, 4, 2>, <6, 8, 3, 1, 2, 4>,

<8, 7, 2, 1, 3, 5> For 0-1 sequences bitonic sequences have the form: 2016/10 Algorithm Analysis L6.16 Half Cleaner Comparison network of depth 1 in which input of line i is compared with line i+n/2

for i=1,2,,n/2 2016/10 Algorithm Analysis L6.17 Property of Half Cleaner Lemma: If the input to a half-cleaner is a bitonic 0-1 sequence, then for the output: both the top and bottom half are bitonic, every element in the top half is every element in

the bottom half, and at least one of the halves is clean.all 0.s or all 1.s. Proof: Simple inspection of 8 different cases. 2016/10 Algorithm Analysis L6.18 Bitonic Sorter

Recursively defined, so we have: 2016/10 Algorithm Analysis L6.19 Example for bitonic Sorter 2016/10

Algorithm Analysis L6.20 Merging Network Idea: Given 2 sorted sequences, reverse the second one, then concatenate with the first one get a bitonic sequence. Example: X = 0011 Y = 0111 YR = 1110 XYR = 00111110 (bitonic) 2016/10

Algorithm Analysis L6.21 Merging Network (cont.) How do we reverse Y? We dont! Instead, we reverse the bottom half of the connections of the first half-cleaner: X X

is equal to Y YR 2016/10 Y Algorithm Analysis L6.22 Merging Network - Example

So we get as Merging Network: 1 0 2016/10 Algorithm Analysis 0 1 L6.23

Sorting Network Construction Principle Using the MergeSort-Idea we can recursively construct a Sorting Network by combining several Merger 2016/10 Algorithm Analysis L6.24 Sorting Network - Example

Example: n = 8 Sorter Sorter 2016/10 Algorithm Analysis L6.25 Sorting Network Example (cont.) Merger

2016/10 Merger Merger Algorithm Analysis L6.26 Sorting Network Complexity Analysis

According to the construction principle for sorting networks we get: 2016/10 Algorithm Analysis L6.27