5

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

Improve this question
5
  • 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
    CommentedNov 8, 2014 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
    CommentedNov 8, 2014 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
    CommentedNov 8, 2014 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
    CommentedNov 8, 2014 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
    CommentedNov 8, 2014 at 15:33

1 Answer 1

Reset to default
8

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!

Improve this answer
4
  • 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
    CommentedNov 8, 2014 at 16:05
  • 1
    @user3787875 you might enjoy reading more about sorting networks - there are some interesting bits in there.
    – user40980
    CommentedNov 8, 2014 at 16:19
  • @MichaelT Thank you. It was very fun to read and I learned alot!
    – wefwefa3
    CommentedNov 8, 2014 at 21:06
  • My brain almost exploded looking at this until I realized that SWAP does a comparison. Neat inlined code anyway!
    – user204677
    CommentedDec 9, 2017 at 17:45

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.