C Question about sorting algorithms.

blind0ne

blind0ne

Please, answer me on this question, what is the fastest sorting algorithm. Just the one that will sort a list of ints from random order to sorted one. I heared a lot about algo complexity and a lot of other algorithms (but never ever finsided my course), so what algo should I use for faster performance? should it be multhithreaded somehow? Thank you
 
In college, I was taught that quicksort is the fastest sorting algorithm. Well, that was back in 2002, and Java was used for the class. I did finish it (Had a good instructor, too). I'd suggest not worrying about multithreading for now, just study up on how to properly write the sorter in a language of your choice. :)
 
astyle said:
I was taught that quicksort is the fastest sorting algorithm.
Click to expand...
Didn't get much software engineering but we were taught various different algorithms, some work better in certain situations, while other algorithms might be faster but use an exorbitant amount of memory. Had to do all this in Pascal back then.

Simple answer, there's isn't one algorithm that works best in every situation.
 
It's been a while since I studied the matter. My recollection is that Quicksort is the fastest general-purpose algorithm, but it's also hard to implement and parallelize. Merge sort's performance is very similar and it is much easier to implement and parallelize. I did the former in Java to prepare for a job interview, and hit the jackpot when I was asked that very question.
 
qsort is fastest in most cases
for special cases (very short arrays, elements are almost sorted, etc) other algos may do better
 
SirDice said:
Didn't get much software engineering but we were taught various different algorithms, some work better in certain situations, while other algorithms might be faster but use an exorbitant amount of memory. Had to do all this in Pascal back then.

Simple answer, there's isn't one algorithm that works best in every situation.
Click to expand...
Exorbitant memory usage usually happens with databases. And you know the UNIX philosophy for utilities: Do one thing, and do it well. Pipe output from one utility into another. Same with learning algorithms: Pick one, and learn how to write it in a language of your choice, and then string it into more complicated designs.
 
1. Pick literally anything that you can call via something_sort(my_datastructure). Sure, quicksort, whatever.
2. Slap a "// FIXME: Just picked this without researching anything" on it
3. Don't think about it again until you're done with the program and the app is slow
4. Control-F, "FIXME" and then you will magically have a non-theoretical question that people can give very specific suggestions about.
 
msplsh said:
1. Pick literally anything that you can call via something_sort(my_datastructure). Sure, quicksort, whatever.
2. Slap a "// FIXME: Just picked this without researching anything" on it
3. Don't think about it again until you're done with the program and the app is slow
4. Control-F, "FIXME" and then you will magically have a non-theoretical question that people can give very specific suggestions about.
Click to expand...
Perfect suggestions for corporate programmers. I get the impression that OP is not quite the basket case like that.
 
What everyone above says.
It depends is the biggest thing.
Data that is almost sorted can be quicker with one algorithm, completely random needs a different one.
memory to spare? memory constrained? extra factors.
ints? you've opened to C++, so I would say "look at the options/algorithms in the STL".
C++ STL (Standard Template Library) a lot of smart people have spent a lot of time making them correct and "fast enough". STL will save you time in the long run because you can concentrate on your code.
 
The most implemented generic algorithm (which means it's expected to perform nice without any prior knowledge about the data set, like already being partially sorted) nowadays is indeed mergesort. Its complexity is the same as quicksort, but it is stable (elements comparing equal will keep the same order as in the input) and can be parallelized, therefore take advantage of multicore processors. So you could argue it's "better" than quicksort, somehow.
 
If you are talking about only a few thousands of data points then for C it simply doesn’t matter which algorithm you choose, since the difference between the execution times might max. be a few milliseconds, if it reaches a ms at all. So already spending the time on this forum with this question in mind never ever would be payed back by any speed enhancements. That said, I suggest to go with Quicksort and here with the iterative and not the recursive version. I use this when it comes to simple sorting in my code.

If at the same time this is about storing data somewhere in a sorted fashion, and searching it quickly, then I use a hash table backed by balanced binary trees (AVL).
 
This reminds me, back in high school (pre-2000), when I took a BASIC programming class, one of my assignments actually involved showing a graphical representation of first flipping all bits from 0 to 1, then flipping every 2nd bit from 1 to 0, then every 3rd bit needs to be reversed... in the end, only bits 1, 4, 9...n^2 are zeros, the rest are ones.
 
blind0ne said:
i;m still wondering where I can read the actual body of this fucntions
Click to expand...
The C standard defines the function and how it should work, not a specific implementation. You will find an implementation in any C standard library, e.g. in FreeBSDs libc as well as in GNUs glibc, and they will differ for sure (but do the same thing).
 
blind0ne said:
I've found the example to sort argv, https://linux.die.net/man/3/qsort .
Click to expand...
Note that this is the C function, not the C++ one. You can tell by the header it includes

#include <stdlib.h> is for C
#include <cstdlib> is for C++

Here is the reference for C++: https://en.cppreference.com/w/cpp/algorithm/qsort

PS: C++ is backwards compatible, so you can use the C headers in your program, but it is "cleaner" to use the C++ headers then.

#include <string.h> vs #include <cstring>
#include <stdio.h> vs #include <cstdio>

and so on
 
Zirias said:
The C standard defines the function and how it should work, not a specific implementation. You will find an implementation in any C standard library, e.g. in FreeBSDs libc as well as in GNUs glibc, and they will differ for sure (but do the same thing).
Click to expand...
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
 
You must log in or register to reply here.
Back
Top