The information content in sorting algorithms
Authors:
- 1 July 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2746-2750
Abstract
Sorting algorithms like MergeSort or BubbleSort order items according to some criterion. Whereas the computational complexities of the various sorting algorithms are well understood, their behavior with noisy input data or unreliable algorithm operations is less known. In this work, we present an information-theoretic approach to quantifying the information content of algorithms. We exemplify the significance of this approach by comparing different algorithms w.r.t to both informativeness and stability. For the first time, the amount of order information that a sorting algorithm can extract in uncertain settings is measured quantitatively. Such measurements not only render a principled comparison of algorithms possible, but also guide the design and construction of algorithms that provide the maximum information. Results for five popular sorting algorithms are illustrated, giving new insights about the amount of ordering information achievable for them. For example, in noisy settings, BubbleSort can outperform MergeSort in the number of bits that can be effectively extracted per comparison made.Keywords
This publication has 5 references indexed in Scilit:
- Context Sensitive Information: Model Validation by Information TheoryLecture Notes in Computer Science, 2011
- Information theoretic model validation for clustering2010
- Approximate Sorting2006
- Coping with erroneous information while sortingIEEE Transactions on Computers, 1991
- Metric Methods for Analyzing Partially Ranked Data1985