thanks got it.

Dark Mode

542 views

1 vote

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.

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.

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

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

@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

0