What sorting method to use: quicksort, bucket sort, radix, ... for tiny data pairs? (c++)

I need to optimize some code that sorts a vector<pair<int, float >>a where the pairs needs to be sorted on the float value. The vector will have an length between 0 and 5. I've been googling and reading up on sorting methods in C++ but cannot find any benchmarks on sorting tiny data sets. For the system it's important be as fast as possi开发者_如何学Goble as it's used for a real time blob tracking system.

Kind regards, Pollux

Insertion sort and Bubble sort are great for tiny data pairs.

Another option is to hard code the compare logic, with a couple if statements.
Check out What is the fastest possible way to sort an array of 7 integers? for some ideas.

It makes no sense to read about benchmarks. You can read about and compare the complexity (Big-O) of algorithms, because it only depends on the algorithms themselves, but benchmarking is something that depends on too many factors.

You need to do the benchmarking for yourself, using the tools that you use, in the environment that matters to the users of your application.

For the data you have mentioned (0-5), use STL sort methods. ( historically qsort based)

stable_sort -- if you want to maintain the order for duplicates. ( historically merge sort based)

Any particular reason why you need this code optimized? For n==5, pretty much any sort will do. Even Bogosort should have a reasonable runtime, since there are only 5! == 120 possible permutations in your data. Have you profiled your algorithm to find out whether this is a bottleneck?

First, premature optimization is the root of all evil. That is, first benchmark your code and make sure the sorting is the one that's actually taking the most time. If another part of your performance-critical code is taking 80% of the execution time, you will get drastic performance improvements optimizing that first.

Considering you have 5 elements, the point is pretty much moot. Any algorithm you use (except bogosort :D) should have a pretty much constant execution time, unless you run the algorithm a few hundred times per second, or more.

Second, provided you still want to optimize the search, if you know for sure you always will have 5 elements, the optimal method is by hard-coding the comparations (It can be proven mathematically that this method is optimal, providing a minimal number of executed operations in the worst case scenario - we had this as a laboratory application in university). The same applies if you have less than five elements, but the algorithm becomes prohibitive to write and execute if you have more than seven elements - the logic is convoluted to write and follow so your code will become difficult to maintain.

Let me know if you need help with writing the optimal hard-coded algorithm itself (though I think you should find the implementation and theory online).

If you do not always have five numbers (or for some reason want to avoid the hardcoded comparisions algorithm), use the sort provided by the library. This page concludes that the stl sort is optimal in terms of time (not only number of executed operations). I do not know what implementation was used for search.

Use a somewhat nasty set of ifs for the fastest sort of 5 items, or if you want a sort that is just a little bit slower, but much less of a headache, you can use a sorting network. Use this site with the number of inputs equal to five to get an optimized sorting network. It even shows how you can do some parts in parallel though that seems a bit excessive for only 5 inputs. It will require 9 comparisons which is quite good. You will implement the sorting network with a set of ifs as well, but the difference between the somewhat nasty set of ifs, which I mentioned at the beginning, which truly optimal and an optimal sorting network is the number of swaps: the sorting network doesn't minimize the number of swaps.

If you're really certain (that is, you have measured) that this is a bottleneck and needs to be optimized, and just any sort algorithm from STL won't be fast enough (and you've measured that too), then perhaps you know something more that you can use? Standard sorting algorithms are general, and will work (reasonably well) for any data set: different numbers of elements, different ranges of values, and so on. If you really need performance, the trick is often to use additional information to make a more specialized algorithm.

Here you have said one thing: there are 0-5 elements to sort, As Nick D said in his answer, perhaps this will make it faster to use hard-coded if statements instead of the typical loops or recursion of general sorting algorithms.

But perhaps there is more? For example, are there any restrictions on the float values that can occur?

Here is a routine for sorting 4 elements in optimal number of comparisons. I would have posted for 5 elements, but stackoverflow limits posts to 30000 characters.

Whether this is actually the fastest depends on how much pressure your CPU instruction cache can take, so benchmark within real program!

/// Generated sort function for 4 arguments.
template <class T>
void DirectSort(T& a0, T& a1, T& a2, T& a3) {
    if (a0 < a1) {
        if (a0 < a2) {
            if (a0 < a3) {
                if (a1 < a2) {
                    if (a1 < a3) {
                        if (a3 < a2) {
                            {
                                T tmp(a2);
                                a2 = a3;
                                a3 = tmp;
                            }
                        }
                    }
                    else { // a1 >= a3
                        {
                            T tmp(a1);
                            a1 = a3;
                            a3 = a2;
                            a2 = tmp;
                        }
                        // a2 >= a3
                    }
                }
                else { // a1 >= a2
                    if (a1 < a3) {
                        {
                            T tmp(a1);
                            a1 = a2;
                            a2 = tmp;
                        }
                        // a2 < a3
                    }
                    else { // a1 >= a3
                        if (a2 < a3) {
                            {
                                T tmp(a1);
                                a1 = a2;
                                a2 = a3;
                                a3 = tmp;
                            }
                        }
                        else { // a2 >= a3
                            {
                                T tmp(a1);
                                a1 = a3;
                                a3 = tmp;
                            }
                        }
                    }
                }
            }
            else { // a0 >= a3
                if (a1 < a2) {
                    {
                        T tmp(a0);
                        a0 = a3;
                        a3 = a2;
                        a2 = a1;
                        a1 = tmp;
                    }
                    // a1 >= a3
                    // a2 >= a3
                }
                else { // a1 >= a2
                    {
                        T tmp(a0);
                        a0 = a3;
                        a3 = a1;
                        a1 = tmp;
                    }
                    // a1 >= a3
                    // a2 >= a3
                }
            }
        }
        else { // a0 >= a2
            if (a0 < a3) {
                // a1 >= a2
                if (a1 < a3) {
                    {
                        T tmp(a0);
                        a0 = a2;
                        a2 = a1;
                        a1 = tmp;
                    }
                    // a2 < a3
                }
                else { // a1 >= a3
                    {
                        T tmp(a0);
                        a0 = a2;
                        a2 = a3;
                        a3 = a1;
                        a1 = tmp;
                    }
                    // a2 < a3
                }
            }
            else { // a0 >= a3
                // a1 >= a2
                // a1 >= a3
                if (a2 < a3) {
                    {
                        T tmp(a0);
                        a0 = a2;
                        a2 = tmp;
                    }
                    {
                        T tmp(a1);
                        a1 = a3;
                        a3 = tmp;
                    }
                }
                else { // a2 >= a3
                    {
                        T tmp(a0);
                        a0 = a3;
                        a3 = a1;
                        a1 = a2;
                        a2 = tmp;
                    }
                }
            }
        }
    }
    else { // a0 >= a1
        if (a0 < a2) {
            if (a0 < a3) {
                {
                    T tmp(a0);
                    a0 = a1;
                    a1 = tmp;
                }
                // a1 < a2
                // a1 < a3
                if (a3 < a2) {
                    {
                        T tmp(a2);
                        a2 = a3;
                        a3 = tmp;
                    }
                }
            }
            else { // a0 >= a3
                // a1 < a2
                if (a1 < a3) {
                    {
                        T tmp(a0);
                        a0 = a1;
                        a1 = a3;
                        a3 = a2;
                        a2 = tmp;
                    }
                    // a2 >= a3
                }
                else { // a1 >= a3
                    {
                        T tmp(a0);
                        a0 = a3;
                        a3 = a2;
                        a2 = tmp;
                    }
                    // a2 >= a3
                }
            }
        }
        else { // a0 >= a2
            if (a0 < a3) {
                if (a1 < a2) {
                    {
                        T tmp(a0);
                        a0 = a1;
                        a1 = a2;
                        a2 = tmp;
                    }
                    // a1 < a3
                    // a2 < a3
                }
                else { // a1 >= a2
                    {
                        T tmp(a0);
                        a0 = a2;
                        a2 = tmp;
                    }
                    // a1 < a3
                    // a2 < a3
                }
            }
            else { // a0 >= a3
                if (a1 < a2) {
                    if (a1 < a3) {
                        if (a2 < a3) {
                            {
                                T tmp(a0);
                                a0 = a1;
                                a1 = a2;
                                a2 = a3;
                                a3 = tmp;
                            }
                        }
                        else { // a2 >= a3
                            {
                                T tmp(a0);
                                a0 = a1;
                                a1 = a3;
                                a3 = tmp;
                            }
                        }
                    }
                    else { // a1 >= a3
                        {
                            T tmp(a0);
                            a0 = a3;
                            a3 = tmp;
                        }
                        // a2 >= a3
                    }
                }
                else { // a1 >= a2
                    if (a1 < a3) {
                        {
                            T tmp(a0);
                            a0 = a2;
                            a2 = a3;
                            a3 = tmp;
                        }
                        // a2 < a3
                    }
                    else { // a1 >= a3
                        if (a2 < a3) {
                            {
                                T tmp(a0);
                                a0 = a2;
                                a2 = a1;
                                a1 = a3;
                                a3 = tmp;
                            }
                        }
                        else { // a2 >= a3
                            {
                                T tmp(a0);
                                a0 = a3;
                                a3 = tmp;
                            }
                            {
                                T tmp(a1);
                                a1 = a2;
                                a2 = tmp;
                            }
                        }
                    }
                }
            }
        }
    }
} // DirectSort - 4 arguments.