ACE volume 2 divide and conquer

Question

given an array that contain only two value (0 or 1) and an insertion sort is used to sort that array,

which of the following input require maximum number of comparisons ?

a)111111000000      b)101010101010

c)000000111111      c)010101010101

here, ans is option (a) but i have a doubt that to compare all the above option it required same number of copamrison

bcz in insertion sort it compare to each element and the move that element to specified position.

then how option (a) is correct plz explain me.

Answer 1

Actually , sorting means either ascending order or descending order..... there is no rule that sorting means consider ascending order by default, but people is considering like that.

 

We all know that, Insertion sort takes Maximum no.of comparissions for worst case input.

 

1) if your insertion sort algorithm sorting the elements in ascending order.

Best Case possible on input Array :-  1,2,3,4,5,6,7 therefore ascending order

Worst Case possible on input Array :-  7,6,5,4,3,2,1 therefore descending order

 

Here you have only 1 and 0 ===> 1,1,1,1,1,0,0,0,0

 

2) if your insertion sort algorithm sorting the elements in descending order.

Best Case possible on input Array :-  7,6,5,4,3,2,1 therefore descending order

Worst Case possible on input Array :-  1,2,3,4,5,6,7 therefore ascending order

 

Here you have only 1 and 0 ===> 0,0,0,0,1,1,1,1,1

Comments

thanks got it.

---

@shaik masthan Sir, I second case, There is typing mistake please correct

2) if your insertion sort algorithm sorting the elements in descending order.

worst Case possible on input Array :-  1,2,3,4,5,6,7 therefore ascending order

best Case possible on input Array :-  7,6,5,4,3,2,1 therefore descending order
 

---

Thanks rishav, due to copy and paste that typing mistake occur, i will update it

Answer 2

take a small string say 1100, 0011, 0101,1010 than calculate the comparisons.

for 1100 : 6 comparison

    0011 : 3 comparison

    0101 : 5 comparison

   1010 : 5 comparison

and moreover 1st case is a worst case for the values because in descending order...

so the answer is A

Comments

input 0 : no comparison

input0 : 1  comparison (0<0 : false no effect)

input 1 : 1 comparison (1<0 : false no effect)

input 1 : 1 comparison (1 <0 :false .....)

did u get this now

---

Ya now I got it thanks brother

---

aree koi baat nai :) bass concept clear hona chiye ki kaise kam karra. baki sab ok hai