2
$\begingroup$

were given an array of numbers "A" of size n, any given number in the array can be one of the following: 0,1,2.

using insertion sort, what is the worst case scenario, and what is the best case scenario.

i translated this question since it was given to me in another language (not a native English speaker)

anyway what they mean by worst case is in which case would the algorithim perform the most comparisons.

the best case is for example if all numbers in the array are the same, thats easy.

but for the worst case i got to the conclusion that an array that its first third is all 2's, second third is all 1's and last third is all 0's would make it so the algorithem will perform as many comparrisons as possible given the constraints.

i got to my answer by trial and error, and not only am i not sure that im even right, just giving the answer is not enough i need to explain it formally, (university)

i havent the slightest idea of where to even start. pls help :(

the insertion sort algo were using is based on the book Introduction to Algorithms Second Edition from MIT

(sorry if my English is not good)

Improve this question
$\endgroup$

3 Answers 3

Reset to default
2
$\begingroup$

Assume a standard implementation: To insert x, you scan the array from right to left until you find the largest I with a[i] <= x, then insert at I+1.

Inserting a number 2 has zero cost itself, but increases the cost of a following insert of 0 or 1 by 1. Inserting a number 1 increases the cost of later inserting 0 by 1. So given that you have x 0’s, y 1’s and z 2’s, with x + y + z = n, the worst case is inserting every 2 before every 1 or 0, and inserting every 1 before every 0. So the worst case is an array in reverse order at a total cost of z*0 + y*z + x*(y+z).

If x is fixed, then the worst case is z=y because that maximises y*z when their sum is fixed, so y=z=(n-x)/2. Total cost is (n-x)^2/4 + x(n-x) = n^2/4 - nx/2 + x^2/4 + nx - x^2 = n^2/4 + nx/2 - 3/4 x^2. The derivative n/2 - 1.5x is 0 when x = n/3, so the worst case is x = y = z = n/3 with n^2/3 moves and compares.

Now imagine we change the algorithm so inserting k identical elements is done in one operation, so your worst case becomes almost the best. That will be quite interesting.

Improve this answer
$\endgroup$
0
$\begingroup$

Yes, in insertion sort, you would have to do the most work if the array was sorted in reverse order. Both the number of comparisons and the number of swaps would be $O(n^2)$ in that case. Restricting the range of elements to only $\{0,1,2\}$ does not change this fact (at least in asymptotic sense).

Improve this answer
$\endgroup$
2
  • $\begingroup$ thing is that both theese array are sorted in reverse but yield different amount of comparrisons: 2,1,0,0,0,0 2,2,1,1,0,0 with the first giving 12 comparisons and the second 15 edit: oh.. i get what youre saying, i will ask the proffessor to clarify if he means asymptoically or actually worst case. $\endgroup$ Commented May 9, 2024 at 13:15
  • $\begingroup$ yeah unfortunatly he does not care about the asymptoitic case since he deems it " too easy" :( $\endgroup$ Commented May 9, 2024 at 13:23
0
$\begingroup$

There is a trivial change to make it run in O(n): iterate through the array, finding elements with key = 1, insert them in front of the first item that is not 1. Then iterate, finding items equal to 2, insert them before the first item equal to 3. When done, the rest is already sorted. 2n comparisons and swaps at most.

Improve this answer
$\endgroup$

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.