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)

$\endgroup$

3 Answers 3

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.

$\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).

$\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 at 13:15
  • $\begingroup$ yeah unfortunatly he does not care about the asymptoitic case since he deems it " too easy" :( $\endgroup$ Commented May 9 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.

$\endgroup$

Your Answer

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

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