4

I have been working on sorting algorithms for a few weeks now, but one of my question still hasn't an answer: are there optimal sequential comparison sorts for fixed-size – and random-access – collections? Most sorting algorithms adapt to the size of the collection, but knowing the size of the collection to sort allows to pick a specific sorting algorithm for this size. For example, the following algorithm should sort three values with both an optimal number of comparisons and an optimal number of swaps or assignments (it's C++, but it should be fairly easy to translate to any language):

void sort3(int& x, int& y, int& z) { if (x < y) { if (z < y) { if (z < x) { int tmp = z; z = y; y = x; x = tmp; } else { std::swap(y, z); } } } else if (z < y) { std::swap(x, z); } else if (z < x) { int tmp = x; x = y; y = z; z = tmp; } else { std::swap(x, y); } }

Whatever the input, this algorithm will sort three values with at most 3 comparisons and 4 assignments. I may be wrong, but I don't think that sorting three values can be done with less comparisons and less assignments than this algorithm. If it is indeed the case, then this would be an optimal comparison sorting algorithm to sort three values.

It seems that optimal sorting algorithms of this kind for any size could be generated thanks to some permutation algorithm, but I was unable to find such a generation algorithm and writing one does not seem to be trivial. I tried to find near-optimal sorting algorithms for some fixed sizes, but couldn't find any simple way to generate such algorithms:

  • Sorting networks seemed like a good idea but they always perform a fixed number of comparisons and swaps, which means that they do not adapt to the data. Even optimal sorting networks of size greater than 5 qickly lose the battle against a simple insertion sort for some inputs.

  • Parallel sorting algorithms and non-comparison sorts (spreadsort, radix sort...) are interesting but I am interested in sequentially sorting small collections. And these categories of algorithms tend to hide a big constant complexity, which means that they are more suitable for big collections.

  • My current method to find the most optimal sorting algorithm to sort a small fixed-size collection is to count the number of comparisons needed to sort all the possible permutations of a collection of size N:

    // Fill an array of size N std::array<int, N> collection; std::iota(std::begin(collection), std::end(collection), 0); // Count comparisons made by an insertion sort cppsort::counting_adapter< cppsort::insertion_sorter > sorter; // Total number of comparisons std::size_t count = 0; // For each possible permutation of collection do { auto to_sort = collection; // Sort collection, get the number of comparisons made count += sorter(to_sort); } while (std::next_permutation(std::begin(collection), std::end(collection)));

    This code uses my cpp-sort library. I used it because it makes it easy to count comparisons made by a sorting algorithm, but it could be implemented without it or in another language. This method has a problem though: it only takes into account the number of comparisons and can only help to find the most optimal algorithm amongst known algorithms, it doesn't allow to write a sorting algorithms generators.

That was quite the introduction, but my question is basically as follows: are there known methods to generate sequential comparison sorting algorithms for fixed-size collections that are optimal with regards to the number of assignments and/or the number of comparisons performed?

Improve this question
6
  • If your approach to superoptimization of sorting algorithms tell you that insertion sort is average O(n^2), you have won, and you have lost. As you have figured out, it doesn't create a viable sorting algorithm for you; instead it performs a measurement on the sorting algorithm supplied by you. You have also figured out that practical input data is not entirely random; it typically contains partially sorted data. Before you begin super-optimization, it might be worthwhile to empirically study the phenomenon of partially sorted data in real-world software systems.
    – rwong
    CommentedOct 5, 2015 at 20:18
  • Another thing is that optimal sorting networks exist; it is theoretically possible to generate an optimal sorting network for a given number of inputs - by brute force; it is just that algorithms for automatically generating an optimal sorting network for N ever slightly larger than 10 becomes impractically slow.
    – rwong
    CommentedOct 5, 2015 at 20:21
  • Finally there is the issue of adapting sorting algorithms to specific computer architectures (processors and execution units). Modern processors are both faster than the ideal abstract machine (superscalar, multiple ALU units, short-vector parallelism, pipelining, branch prediction), and slow (cache and memory latencies, scheduling bubbles, flushing due to branch misprediction), etc. There's also many-core parallelism (GPU and some specially-designed CPUs).
    – rwong
    CommentedOct 5, 2015 at 20:25
  • See also (not duplicate, but related to the theme): Why don't computers come with specialized hardware such as sorting networks?
    – rwong
    CommentedOct 5, 2015 at 20:36
  • @rwong Yeah, I know about partially sorted data, I've recently designed a sorting algorithms along the lines of TimSort specially for those :p My point about optimal sorting networks wasn't that optimal sorting networks didn't exist but that they do not produce optimal sorting algorithms: the three values sort that I have provided for example always does less work than an optimal sorting network of size 3.
    – Morwenn
    CommentedOct 5, 2015 at 20:36

1 Answer 1

Reset to default
2

The problem with finding the optimal algorithm is the word "optimal": A sorting algorithm may be optimal in one case, but it will be suboptimal in at least one other case. The question is, what optimum you are designing it for. Take for instance your algorithm. It is optimal for the sequences:

x < y <= z x >= y > z

(Aside: This means that you failed to optimize the cases x == y <= z and x >= y == z properly, because they could have been handled by the same code paths. But that's not my point here.)

Yet your algorithm is suboptimal for the other four possible orderings. Now, you can write algorithms like yours, that are optimal for any two of the six possible orderings (taking two comparisons), but they will all require a third comparison in the other four cases.

It is simply not possible to write an algorithm that is optimal for any input order. This is true for any count of objects larger than two. That is, you have to decide, what input orderings to optimize for, and whether you have input orderings which you don't want to optimize for.

To take my point a bit further: Consider the two algorithms quick-sort and insertion-sort. Can you say that either one is absolutely better than the other? No, you can't. Quick-sort will be much faster for random input, but it will simply be pawned by insertion-sort on almost sorted input. Only when you know what kind of input data to expect, you can choose one over the other.

It is a bit like trying to measure location and momentum of a quantum particle. If you know one, you have no idea about the other, and vice versa. You can measure both at the same time, but then both will be inexact. Nature simply does not allow you to know both precisely at the same time. Likewise, when you compare x and y first in your algorithm, you are already breaking the symetry of the problem at hand, making optimal sorting of two thirds of the possible input sequences impossible.

Improve this answer
5
  • Well, I get your point. I guess that I was going for the kind of « optimal » which gets the least work done, like checking first if the collection is sorted, and don't move anything if it is. But my premises seem to be wrong then (and my English is becoming brittle...). And you're right about equality cases. I totally failed to take those into account.
    – Morwenn
    CommentedOct 5, 2015 at 20:32
  • Oh, and I almost forgot, but amongst what I was trying to achieve, I wanted an « optimal » sort to have an optimal number of assignments, whatever the input. While the number of comparisons will depend on how we look at the input, I believe that there is an optimal number of assignments for every input, no matter how we analyze it.
    – Morwenn
    CommentedOct 5, 2015 at 22:42
  • 1
    @Morwenn When an indirect sorting algorithm (where the permutation is recorded in a separate array, without altering the input array) is used, the optimal number of assignments is worst and average case O(N), meaning that the array needs to be rewritten once, assuming the input array can be random-accessed by index in O(1) time per item.
    – rwong
    CommentedOct 6, 2015 at 2:32
  • I know I'm a bit late for the party but I just wanted to state that one could design such an optimal sorting algorithm by assigning each permutation the propablity given by the application (e.g. the same for random permutations/values) then one should be able to build an optimal huffman shaped search over the permutations.
    – Christoph
    CommentedSep 13, 2016 at 13:13
  • @Christoph Yes, and that defines yet another meaning of the word "optimal" ;-) A rather good one, by the way. Yet again, it will become suboptimal should the input distribution change. Unfortunately, it will also not be possible to capture the distributions if the expected length of the input is more than a few entries, as the number of permutations explodes so quickly (it's n! permutations for n entries). Nevertheless, an interesting idea :-)
    – cmaster - reinstate monica
    CommentedSep 13, 2016 at 20:14

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.