Sorting with expensive comparands

Abstract

Suppose each key, of an n element list to be sorted, has a price associated with it. The cost of a comparison is the sum of the prices and the cost of a computation is the total of the comparison costs. What sorting algorithm should we use so that the worst case cost is minimized. We present two approaches to form a census of all sorting algorithms that are optimal for some set of prices. We implemented these approaches and obtained limited results for small n. We also investigated other order statistics.

Keywords:

• Sorting
• poset‐production
• comparison‐based algorithms

C.R. Categories::

• F2.2