0
$\begingroup$

I am asked to give a table of 8 elements that are to be sorted by the following algorithms and to produce their best cases. 1) Selection sort 2) Bubble sort 3) Insertion sort 4) Fusion sort

If I give an already sorted table ex: {1,2,3,4,5,6,7,8} shouldn't it already be the best case for all of them? If I can be considered a best case for each?

$\endgroup$
1
  • $\begingroup$ "If I can be considered a best case for each?" What do you mean by that sentence? Please edit your question to clarify. $\endgroup$
    – John L.
    Apr 6 '19 at 19:24
1
$\begingroup$

Bubble sort can "stop early" should the array already be sorted. Other algorithms have their own advantages or applications, but none of the algorithms mentioned in your question - other than bubble sort - can "stop early".

Therefore for any input Insertion & Selection runtime will be $\Omega (n^2) $, and Mergesort $\Omega(nlog(n))$, so the order of elements doesn't matter at all.

$\bullet $ If you perform bubble sort on an already sorted array, the algorithm can stop when not performing any swaps, and run at $O(n)$

$\bullet $ Merge sort (to which you refer as 'fusion sort' from some reason) is the only algorithm that requires $O(nlog(n))$ rather than $O(n^2)$

$\bullet $ Insertion sort is useful when receiving the array online (one element at a time) and maintaining it sorted. Its noteworthy that since you maintain a sorted array, new elements can be inserted via binary search, which make the insertion sort perform $O(nlog(n))$ comparisons, but still cost $O(n^2)$ due to moving elements.

$\bullet $ Selection sort is very easy to implement and intuitive to explain

$\endgroup$
5
  • $\begingroup$ By the way, you can use \log to denote $\log$ such as in $O(n\log n)$. $\endgroup$
    – John L.
    Apr 6 '19 at 19:37
  • $\begingroup$ It may not be a bad idea to add a linear check if the array is sorted in any step (which can make both insertion and selection also linear in best case), but not sure OP meant modified algorithms. I did not think of a binsearch insertion, that is an insteresting point and i will edit it in. Thanks. $\endgroup$
    – lox
    Apr 6 '19 at 19:44
  • $\begingroup$ An insertion algorithm that compares the last element in the result array with the new element will run $O(n)$ on $1,2,3,\cdots,n$. (Of course, binary search for insertion is a very interesting variation.) Even if "new elements can be inserted via binary search", that does not make it run in $O(n\log n)$. Binary search reduces the number of comparisons; however, the steps that are needed for the actual insertion take $\Theta(n^2)$ in average. $\endgroup$
    – John L.
    Apr 6 '19 at 19:52
  • $\begingroup$ You're right. edited it. No, i didn't implement any variation of insertion sort $\endgroup$
    – lox
    Apr 6 '19 at 19:56
  • $\begingroup$ Upvoted, although this answer still misses some finer (or pedantic) details. $\endgroup$
    – John L.
    Apr 7 '19 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.