- Forum
- General C++ Programming
- QSort, Merge, Heap, and Shell Sort
QSort, Merge, Heap, and Shell Sort
Does anyone happen to know where I can find code examples for timing anaylsis for Qsort, Merge, Heap, and Shell Sort?
Any information would help!
Any information would help!
shell short is a massive undertaking to do analysis upon. The run time varies from N*N to a dozen other values (usually of the form n^(x+1/x) eg n^12/11) and there are many online analysis of it but they are graduate level reading. It is notable for being a very simple algorithm (its not much larger than bubble sort) but needing a small book for the analysis.
the others are pretty easy and also online ... qsort is just nlogn, etc... their analysis is sophmore level stuff.
What exactly do you want, just the best/average/worst case run time? Or the proof of that? Or just want to know when to use which one?
the others are pretty easy and also online ... qsort is just nlogn, etc... their analysis is sophmore level stuff.
What exactly do you want, just the best/average/worst case run time? Or the proof of that? Or just want to know when to use which one?
@jonnin I was hoping to find best/average/worst case run time and proof of it! Not sure how to google such and when I have, I haven't found any examples haha.
Last edited on
type 'best case for shell sort' and hit search ;)
https://en.wikipedia.org/wiki/Shellsort
and similar for the others. Just be aware that SS complexity changes based off the selected sequence, its not static for the algorithm like most others.
to explain that, imagine your sequence simply consists of the value {1}. If you do that, shell sort is exactly insertion sort -- n*n run time, etc. If you change it to like the prime numbers (and the lowest entry in all sequences must be 1) its something else, if you use Knuth's series, its another result, if you use the modern best series, its another value...
the proofs should be in the references area.
https://en.wikipedia.org/wiki/Shellsort
and similar for the others. Just be aware that SS complexity changes based off the selected sequence, its not static for the algorithm like most others.
to explain that, imagine your sequence simply consists of the value {1}. If you do that, shell sort is exactly insertion sort -- n*n run time, etc. If you change it to like the prime numbers (and the lowest entry in all sequences must be 1) its something else, if you use Knuth's series, its another result, if you use the modern best series, its another value...
the proofs should be in the references area.
Last edited on
Topic archived. No new replies allowed.