A Comparison-Based Algorithm for Hardware- and SoftwareBased Median-Finding in Signal Processing Applications
Abstract
Finding the median value in a list of numbers is an important computational task that is useful for a variety of problems in domains such as computing, networking, signal processing, and remote sensing. Algorithms with worst-case running times that vary linearly with the problem size are known. As is the case for sorting, however, algorithms with non-optimal worst-case running times but with better average performance for problem sizes of practical interest do exist. We devise one such algorithm based on comparisons, analyze its running time, and experimentally verify its performance for applications with small-to-moderate input lists.
Keywords
Algorithm, Average-Case Running Time, Computational Complexity, Median, Worst-Case Analysis
