C Question about sorting algorithms.

As others have already said, it all depends. However I do not agree that 'just use C qsort' is always good enough. If your application is doing intensive large searches then optimizing your sort algorithm can make a big difference. A huge amount of research effort has gone into developing search algorithms because of this. That said, I would pretty much always begin with qsort, unless I need a stable sort (see below).

C++ qsort vs C qsort is also quite interesting. C++ qsort is something of the poster child for static polymorphism aka template programming. In C the comparison function is a pointer to a function. It is very difficult for the compiler to optimize calls to this function (maybe possible with LTO). On the other hand, C++ qsort uses template functions which the compiler can easily inline. Typically this will give something like a factor of 2 speedup for C++.

One more thing that you may need to consider is whether you need a stable sort or not. Stable sorts preserve the order of equivalent elements. qsort is not a stable sort, and generally the first choice algorithm for stable sorting is heapsort.
 
blind0ne said:
How can I read all this implementations from freeBSD shell? What is the shortest way for me to look at this pice of code? I'll be really thankfull
Click to expand...
Normally, the include header files for C/C++ are in /usr/include or /usr/local/include. Look for files that end in .h :)
 
Not knowing what "_r" reentrant-safe means and declaring the implementations of the algorithms as "too complicated" kind of makes me wonder what you really want to get out of this thread. Just use the functions.
 
msplsh said:
Not knowing what "_r" reentrant-safe means and declaring the implementations of the algorithms as "too complicated" kind of makes me wonder what you really want to get out of this thread. Just use the functions.
Click to expand...
I would think that OP is trying to get started on C/C++ programming using FreeBSD specifically. FWIW, I don't even like programming very much myself, and could use a refresher on algorithm implementation myself. I never got a handle on C++ (was trained on Java in college), so concepts like namespaces, de-referenced pointers and such - they are rather foreign to me. I do, however, know enough to understand what it would take to learn a new programming language, and to learn how to implement an algorithm in it. Some ideas about learning a new programming language and algorithm implementation - they are universal: install a compiler/interpreter for a language, write a helloworld program, understand a sort algorithm to the point of being able to implement it in the bespoke language.
 
Google words in the man page you don't know. Read people's blog posts about concepts. Don't read the source about how to implement the thing you're interested in and expect to understand it, though. That's way harder than just being capable of using it.
 
Alain De Vos said:
Fyi, timsort & cubesort look the best,
Click to expand...
They look good on a simple chart of complexity best/average/worst. BUT: In real-world uses, the constant out front makes a significant difference. If one of these is consistently 2x slower than the others, the rare O(n) behavior for sorted inputs is not that important. The other real-world problem with sort implementations is: It's actually not all that common that people sort truly random inputs. More often, the input data has interesting structure, like being already partially sorted (quite commonly many short stretches, each of which is already sorted, but of random length). And different sort algorithms handle those "common but weird" cases with widely variable efficiency.

Another weirdness I heard about: Today, most "computers" have lots of memory, but is getting more and more NUMA-ish (with layers of caches and variable access time). A sort that is relatively memory friendly in its cache behavior can easily beat another sort that is theoretically faster (uses fewer swaps and comparisons) but churns the caches badly. But on the other hand, many things that use the same libraries are not really "computers", for example cell phones or Raspberry Pi. They often have much less memory (so O(n) space complexity might be disastrous), but are less NUMA-ish (less variability in cache performance).

For the extreme case of sorting done as a hobby by highly trained professionals on serious racing hardware, look up sortbenchmark.org. These are people who use supercomputers and years of coding to show off how to sort data ridiculously quickly. If people calling qsort() on a single-CPU FreeBSD machine is like teenagers tuning their Honda or Toyota a little bit, the sortbenchmark people are like formula 1 teams with giant budgets. They typically sort data files that are many TB in size, on supercomputers.
 
ralphbsz said:
If people calling qsort() on a single-CPU FreeBSD machine is like teenagers tuning their Honda or Toyota a little bit, the sortbenchmark people are like formula 1 teams with giant budgets.
Click to expand...
I wanted to upvote your post anyway but this made me want to upvote it twice.
 
Comparisons of speed and Big O complexities only make sense if you keep them fair: Same processor, same language for the implementation, same OS, same data being sorted (size and content), same amounts of L3 cache.
 
Paul Floyd said:
As others have already said, it all depends. However I do not agree that 'just use C qsort' is always good enough. If your application is doing intensive large searches then optimizing your sort algorithm can make a big difference. A huge amount of research effort has gone into developing search algorithms because of this. That said, I would pretty much always begin with qsort, unless I need a stable sort (see below).

C++ qsort vs C qsort is also quite interesting. C++ qsort is something of the poster child for static polymorphism aka template programming. In C the comparison function is a pointer to a function. It is very difficult for the compiler to optimize calls to this function (maybe possible with LTO). On the other hand, C++ qsort uses template functions which the compiler can easily inline. Typically this will give something like a factor of 2 speedup for C++.

One more thing that you may need to consider is whether you need a stable sort or not. Stable sorts preserve the order of equivalent elements. qsort is not a stable sort, and generally the first choice algorithm for stable sorting is heapsort.
Click to expand...
Can't really get the part about "preserve the order of equivalent elements", what does it actually mean? It's about sorting list with constant length? Please explain what does "preserve the order of equivalent elements" actually mean.
Thanks
 
You must log in or register to reply here.
Back
Top