4

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).

  • 2
    Big O notation does not measure performance, it measures expected changes in performance in relation to changes in the size of the data set. In your case, the Big O complexity of the algorithm is of very little importance. – Rotem Nov 8 '14 at 14:11
  • A good rule of thumb is "Given 10 elements or less, next to any algorithm performs well". Maybe Bogosort will be a bit at the slow end. So no, the Big O notation does not really matter when sorting 7 elements, except if you are going to sort 5 million times seven arbitrarily chosen elements. – JensG Nov 8 '14 at 14:20
  • What were you using before qsort()? If your program runs 10x slower after changing that one thing you should switch back to whatever it was. – kdgregory Nov 8 '14 at 15:11
  • @kdgregory Sorry for the confusion. I tested my code in a loop with a hard-coded array that already was sorted. – wefwefa3 Nov 8 '14 at 15:22
  • @Rotem. Thank you for your response. I would still like to know if there is a specific one that is better suited than others because sorting is done so frequently in this program. – wefwefa3 Nov 8 '14 at 15:33
7

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!

  • My program runs twice as fast after switching to this. What used to take the program 10.399s to do with qsort now it only takes 4.891s. :) – wefwefa3 Nov 8 '14 at 16:05
  • 1
    @user3787875 you might enjoy reading more about sorting networks - there are some interesting bits in there. – user40980 Nov 8 '14 at 16:19
  • @MichaelT Thank you. It was very fun to read and I learned alot! – wefwefa3 Nov 8 '14 at 21:06
  • My brain almost exploded looking at this until I realized that SWAP does a comparison. Neat inlined code anyway! – user204677 Dec 9 '17 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.