542 views
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.

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

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

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...

by

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

1 vote