Understanding Comparator Networks for Efficient Sorting Networks
Discover the intricacies of comparator networks and their role in building efficient sorting networks. Dive into concepts like standard forms, simple sorting networks, insertion sort, selection/bubble sort, and more to deepen your understanding. Explore the 0-1 principle and its implications, alongside exercises and proofs that illuminate the power and efficiency of these networks. Unveil the secrets behind comparator networks and optimize your sorting algorithms today.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Sorting Networks Uri Zwick Tel Aviv University May 2015
Comparators ? min(?,?) ? max(?,?) ? min(?,?) ? max(?,?) Can we use comparators to build efficient sorting networks?
Comparator networks A comparator network is a network composed of comparators. There are ? input wires, each feeding a single comparator. Each output of a comparator is either an output wire, or feeds a single comparator. The network must be acyclic. Number of output wires must also be ?.
Standard form Exercise: Show that any comparator network is equivalent to a network in standard form.
A simple sorting network 5 comparators 3 levels
Insertion sort ????(?)
Selection/bubble sort ????(?)
Selection/bubble Sort Size = ? ? 1 Depth = 2? 1 2
Exercise: Any sorting network that only compares adjacent lines must be of size at least ? ? 1 2 Exercise: Prove that the network on the next slide, whose depth is ?, is a sorting network
Odd-Even Transposition Sort Size = ? ? 1 Depth = ? 2
The 0-1 principle Theorem: If a network sort all 0-1 inputs, then it sort all inputs
The 0-1 principle Lemma: Let ? be a monotone non-decreasing function. Then, if a network maps ?1,?2,..,?? to ?1,?2,..,??, then it maps ?(?1),?(?2),..,?(??) to ?(?1),?(?2),..,?(??) Proof: By induction on the number of comparisons using ? min ?,? = min(? ? ,? ? ) ? max ?,? = max(? ? ,? ? )
The 0-1 principle Proof: Suppose that a network is not a sorting network. It then maps some ?1,?2,..,?? to ?1,?2,..,??, where ??> ??+1, for some 1 ? < ?. Let ? ? = 1, iff ? ??, 0 otherwise. The network maps ?(?1),?(?2),..,?(??) to ?(?1), ,?(??) = 1,? ??+1 = 0 ,...,?(??) Thus, the network does not sort all 0-1 inputs.
Sorting by merging ????(?) ?????(?,?) ????(?)
Batchers odd-even merge ? ? 2, ? 2) ?( ? 2, ? 2) ?( ?
Batchers odd-even merge ? ? 2, ? 2) ?( ? 2, ? 2) ?( ?
Batchers odd-even merge To merge ?1,?2,..,?? with ?1,?2,..,??: Split ?1,?2,..,?? into ?1,?3, and ?2,?4, Split ?1,?2,..,?? into ?1,?3, and ?2,?4, Merge odd-indexed items to create ?1,?2, Merge even-indexed items to create ?1,?2, Compare/swap (?1,?2),(?2,?3), Does it really work?
Batchers odd-even merge ?(1,1) ?(2,2)
Batchers odd-even merge Proof using the 0-1 principle. Suppose that ?1,?2,..,?? starts with ?0 0 s and that ?1,?2,..,?? starts with ?0 0 s. ?0 2 + ?0 2 0 s, 2 0 s. Then ?1,?2, starts with + ?0 2 ?0 and ?1,?2, starts The difference is either 0,1 or 2! There is a problem only if difference is 2 and last level of comparators fixes it.
Batchers odd-even merge 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 ? ? 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 ? ? 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 ? ?
Batchers odd-even merge Exercise: Justify the use of the 0-1 principle. Exercise: Prove the correctness of the odd-even merging network directly without relying on the 0-1 principle.
Batchers odd-even merge Size number of comparators ? ?,0 = ? 0,? = 0 ? 2, ? 1,1 = 1 ? + ? 1 ? 2 ? 2, ? 2 ? ?,? = ? + ? + 2 ? 2,? ? ?,? = 2? + (? 1) 2 ? 2?,2?= ?2?+ 1 ? ?,? = ?lg? +?(?) No better merging networks are known for any ?,?! Are the odd-even merge networks optimal?
Bitonic sequences A sequence is strict bitonic iff it is a concatenation of a decreasing sequence and an increasing sequence A sequence is bitonic iff it is a cyclic shift of a strict bitonic sequence 8 6 4 1 2 5 7 9 4 1 2 5 7 9 8 6 1 4 2 3
A Bitonic sorter A (strict) bitonic sorter is a network that sorts every (strict) bitonic sequence. If ?1,?2,..,?? and ?1,?2,..,?? are sorted, then ??,?? 1,..,?1,?1,?2,..,??, is bitonic. Thus, a strict bitonic sorter can serve as a merging network
Batchers bitonic sorter ? 2 ? ? ? 2 ? Is this different from odd-even merge?
Batchers bitonic sorter Simple proof using the 0-1 principle. A strict binary bitonic sequence 1?0 1? ? The odd and even subsequences are also strict binary bitonic sequences. By induction they are sorted correctly. The difference between the number of 0 s in the two sorted sequences is one of 1,0,1. Final level of comparators fixes the problem.
Batchers bitonic sorter Exercise: Show that the difference between the number of 0 s in the odd and even subsequences of 1?0 1? ? is ? + 2 2 ? + ? 2 ? 2 Note: We do not need this exact formula in the proof given in the previous slide. Seeing that the difference is 1,0,1 is immediate.
Batchers bitonic sorter for n=2? Very regular structure! When ? = 2?, there are ? levels with ? 2 comparators each. Lines ? and ? are compared at level iff they differ only in the -th most significant bit
Batchers bitonic sorter for n=2? Alternative recursive definition for ? = 2? Sorts general bitonic sequences
The AKS sorting networks [Ajtai-Koml s-Szemer di (1983)] There are sorting networks of ?(log?) depth, and hence ?(?log?) size. The construction is fairly complicated. The constant factors are very large.
