CODEWITHSUNDEEP
algorithmprogramming-languagescode-analysis
user3691721
user3691721

Reputation:

Simple Code and Challenge on Operation (with picture)

I ran into the following pseudo code. Here A is an array of integers:

for i = 1 to n 
{   
    j = i; f = 1;

    while ((j>1) and (f==1))
    {
        if (A[j]<A[j/2]) { swap(A[i], A[j/2]); j = j/2; } 
        else             { f = 0;                       }
    }  
}

I couldn't understand why always the minimal element of A goes into A[1].

In fact I have a problem with, how this code change the A[1]? Or at least if I correctly understand the operation of this code?

Upvotes: 0

Views: 92

Answers (1)

Demplo
Demplo

Reputation: 551

Even though it is not clear how the integer division should work (3/2 == 1 or 3/2 == 2 ?) the algorithm will always move the min value to the first position of the array.

E.g. for an array composed as {4,5,6,2}, the last element will be first moved to the second position with the first swap (j==4 and i==4) leading to this situation: {4,2,6,5}. When j will be updated to j/2 --> 2 the second element of the array 2 will be compared with the the one of index j/2 --> 1 and moved to the first position. Here the problem with the division rises up.

The division 1/2 represents a risk since it is can be converted to 0 leading to a call for A[0] and resulting in an ArrayOutOfBoundException, but this is psuedocode and it could work if you round up the result of the division.

Upvotes: 1

Related Questions