What's the most common real world sorting algorithm? Which one do you actually use when programming with C or a real language like C#/Java?
>>53243696
.sort()
>>53243696
Quicksort
I believe it sorts in O(log2(n))
>>53244048
Also, it's a general sorting algorithm. It can be implemented in any programming language.
https://en.m.wikipedia.org/wiki/Quicksort
The complexity is O(n*log2(n)) not O(log2(n)).
>>53243696
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
int main(int c, char **v)
{
while (--c > 1 && !fork());
sleep(c = atoi(v[c]));
printf("%d\n", c);
wait(0);
return 0;
}
You usually use a hybrid of some sort.
Bit it really dependa on your data.
The most common are variations on Quicksort and occasionally Mergesort. Quicksort typically outperforms most algorithms but Mergesort has the added bonus of guaranteed O(n log n). Downside is more memory use but it's ideal for sorting data on disks.
>>53245598
Forgot to ad, Python uses Mergesort, nearly every other language includes their sort() as QS
>>53245598
What about heap sort?
Bubble sort
>>53243716
\thread
>>53245631
The best.
>>53245631
>>53245741
shell tho
divide and conquer fags need not apply
>>53243696
>when programming with C
Whatever is implemented by qsort(). It's quicksort in glibc.
>>53245598
You can do mergesort in place though the CS101 version usually isn't
Common implementations of the C++ STL use Introsort, rather than Quicksort, and the result tends to be a bit faster than the C qsort routine (although this is partially to do with not having type erasure). The .NET Framework Class Library also uses Introsort.
Radix sort on bytes is pretty hard core
>>53246196
The C standard doesn't specify how qsort() is to be implemented
>>53244085
no its big O is O(n*log(n)) with a worst case of O(n^2)
you NEVER put constatnts in big O notation.
>>53246307
sure you can. O(n*log(n)) is the same set as O(n*log2(n)) is the same set as O(n*ln(n)). It's not what you usually want to do but there's no reason you can't.
>>53246623
then its not big O notation.
constants are factored out because when N gets really fucking big they become irrelevant.
the fact that it was used and that you're defending its use just proves how /g/ is full of CS dropouts
>>53246682
Have you forgotten your CLRS? The notation is flexible enough to allow for it.
>>53246682
You don't even know the definition of big oh
You seem to have memorized a few mechanical rules
People just generally use whatever built in sorting algorithm for the language. It usually some combination of quicksort or merge sort with insertion sort for sorting smaller lists.
>>53245608
Python uses Timsort.
>>53245631
Pretty slow.
Quicksort master race
>>53246307
It's implied that it is in base 2, but it really doesn't matter...
>>53245620
also good but I can't remember why quicksort is preferred
>>53247945
Because usually it's faster that heap sort.
>>53247945
iirc it was because of how simple quicksort is conceptually.
>>53247568
So does Java. C++ std also uses a hybrid between merge, insertion and quick sort
>>53247970
on larger sets of data?
>>53247971
that's what I thought too
How about block sort? According to Wikipedia it scores the best in worst, average, best case time complexity and has a O(1) space complexity.
https://en.wikipedia.org/wiki/Block_sort
>>53248001
>on larger sets of data?
In worst case it's worse, quick sort is n^2 and heap sort is n*ln(n), but usually quick sort is n*ln(n) and faster than heapsort, because the constants are smaller
>>53248118
Ahh ya learn something new every day xd
