Designing Sorting Networks A New Paradigm
Designing Sorting Networks: A New Paradigm provides an in-depth guide to maximizing the efficiency of sorting networks, and uses 0/1 cases, partially ordered sets and Haase diagrams to closely analyze their behavior in an easy, intuitive manner.
This bo
- PDF / 5,551,020 Bytes
- 132 Pages / 439.37 x 666.142 pts Page_size
- 86 Downloads / 288 Views
Sherenaz W. Al-Haj Baddar Kenneth E. Batcher
Designing Sorting Networks A New Paradigm
123
Sherenaz W. Al-Haj Baddar Computer Science University of Jordan Amman Jordan e-mail: [email protected]
ISBN 978-1-4614-1850-4 DOI 10.1007/978-1-4614-1851-1
Kenneth E. Batcher Emeritus Professor of Computer Science Kent State University Kent USA
e-ISBN 978-1-4614-1851-1
Springer New York Dordrecht Heidelberg London Library of Congress Control Number: 2011940821 Ó Springer Science+Business Media, LLC 2011 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Cover design: Deblik Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
Preface
What is a Sorting Network? It is simply a hardware sorter circuit. It consists of small switches, that we call comparators, each of which is equipped with two input lines and two output lines. The comparator receives two numbers on its input lines, compares them, and outputs the maximum on its higher output line and the minimum on its lower output line. Obviously, to carry out the sorting task, you’ll need several stages (columns) of these comparators. Then, your input numbers will go through all these stages so that you receive them totally sorted on the other end of the network.
How Can You Tell if a Given Sorting Network is Better than Other Sorting Networks? Each sorting network has two attributes that one may consider: the number of comparators used throughout all the sorting steps; and the number of sorting steps. Some researchers target designing sorting networks that use as few comparators as possible and these we refer to as efficient sorting networks. Others aim at designing sorting networks that sort using the smallest number of steps and those we refer to as fast sorting networks. Relatively speaking, if your sorting network is efficient then it does not need to be fast and the other way around. Since it is hardware, the inter-connections between the comparators are fixed. Thus, you cannot reconfigure the comparators interconnects based on, say, the outcome of a previous comparator. This is the core difference between sorting in hardware and sorting in software. In a software sorting program, you can easily apply the decision tree model. So, based on the outcome of a comparison in step i, you decide what comparison to do in the step i ? 1. You don’t have this fl
Data Loading...
