retagged by
909 views
1 votes
1 votes
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.
retagged by

2 Answers

3 votes
3 votes
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
edited by
2 votes
2 votes

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

Related questions

1 votes
1 votes
1 answer
1
meethunjadhav asked Jul 30, 2018
406 views
suppose merge sort takes 2 sec to sort a set of 64 keys then how much time will take to sort a set of 512 keys?here, ans is 24 sec how it is plz explain me.
0 votes
0 votes
1 answer
3
Shailendra Patel asked Nov 1, 2016
362 views
Merging K sorted list each of size n/k into one sorted list of n-elements using Heap Sort will take how much time?
0 votes
0 votes
1 answer
4