Quickest sorting algorithm for sorting a low number of integers

algorithmsbig ocoptimizationsorting

I am making a program on my spare time that I want to run as quickly as possible. The program is written in C.

A large set of the procedures operate on pointers to 7 integers that are sorted by their numerical values from high to low.

Up to this point I have used the library function "qsort" to sort my integers. Now when I have finished the rest of the application I want to replace my call to qsort with something quicker.

I want a sorting algorithm to sort a fixed number of 7 integers as fast as possible. Please tell me what you would use and why you think it is best.

  • I have read about the Big O notation and from what I have found out it only measures how long the algorithm will take according to the number of elements it needs to sort. Does the Big O notation really matter when I only need to sort 7 elements? Can O(n * log n) be faster than a O(n ^ 2) in this case?

  • "radixsort" seems like a good choice to me but I want to get your opinions too.

The sorting algorithm will be used millions of times and during that time the user of the program has to wait. My program runs almost 10 times slower since I started using qsort (before that I measured it using a hard-coded array).

Best Answer

Take a look at this neat implementation of sorting six integers. According to sorting networks, 16 comparisons are required to sort 7 integers. Here is the code for seven integers:

    static int sort7(int *d){
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
    SWAP(1, 2);
    SWAP(3, 4);
    SWAP(5, 6);
    SWAP(0, 2);
    SWAP(3, 5);
    SWAP(4, 6);
    SWAP(0, 1);
    SWAP(4, 5);
    SWAP(2, 6);
    SWAP(0, 4);
    SWAP(1, 5);
    SWAP(0, 3);
    SWAP(2, 5);
    SWAP(1, 3);
    SWAP(2, 4);
    SWAP(2, 3);
#undef SWAP
}

Note that I did not test the code!

Related Topic