So given an input of lets say 10 strings, what way can we input these so we get the best or worst case for these two given sorts?
Heap sort:
best case - nlogn
worst case - nlogn
Quick sort:
best case - nlogn
worst case - n^2
Where I get confused on these two is:
- heap- Since the best and worst case are the same does it not matter the input order? The number of comparisons and assignments will always be the same? I imagine in a heap sort it may be the same since the real work is done in the insertion, but the sorting only uses the removal of the max/min heap? Is that why?
- quick sort- This one I don't know for sure. I'm not sure what the best case and worst case situations are for this. If its a already sorted list of 10 strings for example wouldn't we always have to choose the same amount of pivots to get complete the recursive algorithm? Any help on this explanation would really help.