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

not getting how comparison happen can u elaborate it plz...@arvin

---

yes ofcourse, as it says its insertion sort . so before after inserting every element we have to compare its value with the previous one if its less than or not.

so, 1100..

1 inserted  : no comparison

11 inserted : 1 comparison but it is ok

110 : 2 comparison with previous values and it becomes 011

0110 : here 3 comparison with 011 and it becomes 0011.

means we have to compare until we have values in ascending order.

similarly you can go for 0011 , 1010,01010.

---

 arvin can you tell which part of insertion sort code do you think as Comparison

(where the arrays are zero-based)

i ← 1
while i < length(A)
    x ← A[i]
    j ← i - 1
    while j >= 0 and A[j] > x
        A[j+1] ← A[j]
        j ← j - 1
    end while
    A[j+1] ← x
    i ← i + 1
end while

---

@rishav  second while loop... bro. it compares every value till j>=0 and a[j]>x. means it compares each entered into loop with the previous values in the sorted list one by one and when the above conditions are satisfied it swaps the values.

---

 arvin exactly then why  

 0011 : 3 comparison

    0101 : 5 comparison

   1010 : 5 comparison

all should have 6 comparisons. Correct me if wrong

---

see in insertion sort we first input a value than we compare if its less than the previous one than we exchange values else  input the next case and compare.

here in the algo we have AND case which says it all. 

i think u are confused with how actually it works.

 

---

 arvin i am not confused with its working . Can you please show  How  0011 : 3 comparison

---

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