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?

Improve this question
$\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$ Commented Apr 6, 2019 at 19:24

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
5
  • $\begingroup$ By the way, you can use \log to denote $\log$ such as in $O(n\log n)$. $\endgroup$ Commented Apr 6, 2019 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$ Commented Apr 6, 2019 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$ Commented Apr 6, 2019 at 19:52
  • $\begingroup$ You're right. edited it. No, i didn't implement any variation of insertion sort $\endgroup$ Commented Apr 6, 2019 at 19:56
  • $\begingroup$ Upvoted, although this answer still misses some finer (or pedantic) details. $\endgroup$ Commented Apr 7, 2019 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.