Selection on Matrices Classifying Rows and Columns
Alan A. Bertossi, Stephan Olariu, Cristina Maria Pinotti, Si Zheng · Unitn Eprints Research (Università Degli Studi di Trento) · 2002
The median problem transforms a set of $N$ numbers in such a way that none of the first $\\frac{N}{2}$ numbers exceeds any of the last $\\frac{N}{2}$ numbers. A comparator network that solves the median problem on a set of $r$ numbers is commonly called an $r$-{\\em classifier}. This paper shows how the well-known Leighton's Columnsort algorithm can be modified to solve the median problem of $N=rs$ numbers, with $1 \\le s \\le r$,using an $r$-classifier instead of an $r$-sorting network. Overall the $r$-classifier is used $O(s)$ times, namely the same number of times that Columnsort applies an $r$-sorter. A hardware implementation is proposed that runs in optimal $O(s + \\log r)$ time and uses an $O(r\\log r(s + \\log r))$ work. The implementation shows that when $N= r\\log r$ there is a classifier network solving the median problem on $N$ numbers in the same $O(\\log r)$ time and using the same $O(r\\log r)$ comparators as an $r$-classifier, thus saving a $\\log r$ factor in the number of comparators over an $(r\\log r)$-classifier.