GATE Overflow Test Series | Algorithms | Test 1 | Question: 28

Question

Consider the code given below, which runs insertion sort:

void insertionSort(int arr[], int size)
{
    int i, j, value;
    for (i = 1; i < size; i++)
    {
        value = arr[i];
        j = i;
        while (________ )
        {
            arr[j] = arr[j - 1];
            j = j - 1;
        }
        arr[j] = value;
    }
}

Which condition will correctly implement the while loop?

• A. $(j > 0) \ || \ (arr[j - 1] > value)$
• B. $(j > 0) \ \&\& \ (arr[j - 1] > value)$
• C. $(j > 0) \ \&\& \ (arr[j + 1] > value)$
• D. $(j > 0) \ \&\& \ (arr[j + 1] < value)$

 

Comments

B is the correct answer.

https://codereview.stackexchange.com/questions/62306/sorting-an-int-array-using-insertion-sort-algorithm-follow-up

---

I think answer should be (j-1>0) && (arr[j−1]>value)  which is not in option . Am I right?

Answer 1

for (j =2 to array.length)

     key = array[j];

     i =j-1;

     while(i > 0 && array[i] > key)

             array[i+1] = array[i];

             i = i-1;

array[i+1]= key;

 

above is the standard algorithm of insertion sort, from this we can easily infer that  (j>0) && (arr[j−1]>value) is the right option.

 

Hence, B is right answer.

Comments

so here i is equivalent to j-1 . SO shouldn’t answer be  (j-1>0) && (arr[j−1]>value)  ?