CODEWITHSUNDEEP
javaalgorithm
mogulba
mogulba

Reputation: 43

What is this algorithm doing?

I got a pseudocode:

Input: Array A with n (= length) >= 2
Output: x
x = 0;
for i = 1 to n do
  for j = i+1 to n do
    if x < |A[i] - A[j]| then
       x = |A[i] - A[j]|;
    end if
  end for
end for
return x;

I have converted that to a real code to see better what it does:

public class Test
{
    public static void main (String[] args)
    {
        int A[] = {1,2,3,4,5,6,7,8,9};
        int x = 0;

        for (int i = 1; i < A.length; i++)
        {
            for (int j = i + 1; j < A.length; j++)
            {
                if (x < Math.abs(A[i] - A[j]))
                {
                    x = Math.abs(A[i] - A[j]);
                }
            }
        }
        System.out.println(x);
    }
}

The output was 7 with the array in the code. I have used another array (1 to 20) and the putput was 18. Array 1-30, the output was 28. The pattern seems clear, the algorithm gives you the antepenultimate / third from last array value. Or am I wrong?

Upvotes: 0

Views: 146

Answers (4)

Denis
Denis

Reputation: 1229

I think pseudocode is trying to find the greatest difference between two numbers in an array. It should be the difference between the minimum and maximum value of the array.

I personally think this is a really poor algorithm since it is doing this task in O(n^2). You can find the min and maximum value of an array in O(n). and take the difference between those numbers and result will be the same. check the pseudocode

Input: Array A with n (= length) >= 2
min=A[0];max = A[0];
for i = 1 to n do
      if min > A[i] then
         min = A[i];
      end if
      if max < A[i] then
         max = A[i]
      end if
end for
return (max-min);

Upvotes: 4

Robert Kock
Robert Kock

Reputation: 6008

I think the pseudo code tries to find the greater of the difference between any 2 elements within an array.

Your real code however, starts from 1 instead of 0 and therefore excludes the first element within this array.

Upvotes: 5

rgettman
rgettman

Reputation: 178243

The code gives the biggest difference between any two elements in the array.

There are 2 nested loops, each running over each element of the array. The second loop starts at the element after the first loop's element, so that each possible pair is considered only once.

The variable x is the current maximum, initialized to 0. If x is less than the absolute value of the current pair's difference, then we have a new maximum and it is stored.

However, because you directly copied the pseudocode's starting index of 1, you are inadvertently skipping the first element of the array, with index 0. So your Java code is giving you the maximum difference without considering the first element.

If you have an array of values between 1 and n, you are skipping the 1 (in index 0) and the returned value is n - 2, which happens to be the third-to-last value in the array. If you had shuffled the values in the array as a different test case, then you would see that the returned value would have changed to n - 1 as now both 1 and n would be considered (as long as n itself wasn't in the first position).

In any case, you would need to set the index of the first element to 0 so that the first element is considered. Then {1,2,3,4,5,6,7,8,9} would yield 8 (or any other order of those same elements).

Upvotes: 2

LaneL
LaneL

Reputation: 778

Assuming all positive integers, the algorithm in a nutshell finds the difference between the maximum and the minimum value in the array. However, it will not work correctly unless you initialize i to 0 in the for loop.

for (int i = 0; i < A.length; i++)

Upvotes: 0

Related Questions