sorting algorithms- question
Can someone tell me who is the fastest mode to sort an array?? "Fastest" means to have the lowest complexity possible, with oder words, to have the lowest number of repetitions in for, while, dowhile whatever.
In general, an asymptotically optimal comparison-based sort takes linearithmic Ω(n log n) time; this isn't difficult to prove. See, e.g.:
https://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf
Other non-comparative sort algorithms may be faster asymptotically, but those algorithms impose additional requirements on the data and the ordering relation - radix sort, for example takes O(qn) time, but in practice q may be too large or not a constant at all.
https://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf
Other non-comparative sort algorithms may be faster asymptotically, but those algorithms impose additional requirements on the data and the ordering relation - radix sort, for example takes O(qn) time, but in practice q may be too large or not a constant at all.
Last edited on
I like this youtube channel:
Nice visual representations. Chose one you like.
https://www.youtube.com/user/tbingmann/playlists Nice visual representations. Chose one you like.
fastest depends lol.
arrays of integer or compatible to integer types can be sorted in O(N) using bucket sort.
arrays of generic data that is not suitable for the above can be sorted in Nlg(N) time in a variety of ways depending on the type of data and type of container.
SMALL arrays (this depends on current hardware, currently, this is a couple million items!) are faster using shell sort, which is O(N^(z+1)/z) time (usually around 7/6).
Older professional sorts like the c++ built in sort use a mix of a recursive quick / intro/ etc sort with a shell on the back end when the subdivision gets small enough. I don't know if this is still true or not. Shell is a case of doing less work, so whiles its big O is worse than nlgn after a number of items, it still runs faster (not big O but wall clock time) due to its simple internal effort past the crossover.
If you know bucket, quick, shell, and merge sorts, (and probably bubble sort though you would never use it) you would be very well versed in the topic.
the fastest via lowest amount of loops is going to be a hybrid nlgn that drops to shell when the sub arrays get small.
arrays of integer or compatible to integer types can be sorted in O(N) using bucket sort.
arrays of generic data that is not suitable for the above can be sorted in Nlg(N) time in a variety of ways depending on the type of data and type of container.
SMALL arrays (this depends on current hardware, currently, this is a couple million items!) are faster using shell sort, which is O(N^(z+1)/z) time (usually around 7/6).
Older professional sorts like the c++ built in sort use a mix of a recursive quick / intro/ etc sort with a shell on the back end when the subdivision gets small enough. I don't know if this is still true or not. Shell is a case of doing less work, so whiles its big O is worse than nlgn after a number of items, it still runs faster (not big O but wall clock time) due to its simple internal effort past the crossover.
If you know bucket, quick, shell, and merge sorts, (and probably bubble sort though you would never use it) you would be very well versed in the topic.
the fastest via lowest amount of loops is going to be a hybrid nlgn that drops to shell when the sub arrays get small.
Last edited on
Wow, I had no idea shell sort had such complicated time complexities.
https://en.wikipedia.org/wiki/Shellsort#Gap_sequences
https://en.wikipedia.org/wiki/Shellsort#Gap_sequences
yes it is a excellent choice to use for big-O analysis practice. Some of the sequence choices can drive you nuts trying to figure it out. You can make it do N^2 for example, by just setting the sequence to "1" with no other entries. I think that makes it 'insertion' sort, but trying to remember without looking at it here. I played with it a bit before we had vectors, on a machine that couldn't handle recursion. ~10 lines of code, 10+ pages of analysis...
N^(7/6) is pretty much the generic complexity of it for most good sequences. Not that complex to express, but hair raising to prove it. Looks like they have gotten some that are significantly better than this now.
N^(7/6) is pretty much the generic complexity of it for most good sequences. Not that complex to express, but hair raising to prove it. Looks like they have gotten some that are significantly better than this now.
Last edited on
Topic archived. No new replies allowed.