Converting pseudocode for array minimum into Java code, using recursion

Question

I am blanking on this exam review question, can anyone help me get started? In findMinPos, I am confused by the three parameters, how do I access the nodes in data array? Can I use a loop even though it's a recursive method?

public class ArraySwapMin
{
    public static void swapMin( int[] data, int cur )  
    {   
        int min = findMinPos( data, cur, cur );
        /////////////////////////////////////////////////////////////
        // swap the min position value with the one in the cur position
        ////////////////////////////////////////////////////////////////
    } 
    /**
     * Check the nodes in "data" from position "start" to the end of the array.
     * to see if any value in this part of the array is less than the min
     * value found so far (up to the "cur" position).
     */ 
    private static int findMinPos( int[] data, int cur, int minPosSoFar )
    {
        //////////////////////////////////////////////////////////////
        // Compare this entry's value (if it is a valid entry) with the
        // value in the entry "minPosSoFar". If this value is less, then 
        // this entry is now the "minPosSoFar". 
        // Recurse for the rest of the array.
        ///////////////////////////////////////////////////////////////


           return minPosSoFar;
    }

    /**
     * unit tester
     */
    public static void  main( String[] args )
    {
        int[] data = { 12, 3, 10, 5, 1, 8 };

        int count = 0;
        System.out.println( "++++++++++++++++ ArraySwapMin ++++++++++++++++" );
        printArray( "starting array ", data );

        for ( int i = 0; i < data.length - 1; i++ )
        {
            swapMin( data, i );
            printArray( "swap Min with " + i, data );
        }

    }
    public static void printArray( String label, int[] data )
    {
        System.out.print( label + ": [ " );
        for ( int i = 0; i < data.length - 1; i++ )
            System.out.print( data[ i ] + ", " );
        System.out.println( data[ data.length - 1 ] + " ]" );
    }
}

1) You've described a problem but have so far not asked a question (let alone a specific, answerable question). What is your question? 2) See Starting Writing a Program for great tips. — Andrew Thompson
– Andrew Thompson, Commented May 8, 2013 at 13:25

Daniel Lerps · Accepted Answer · 2013-05-08 14:15:35Z

In swapMin() you have to switch the current position with the one with the minimum.

public static void swapMin( int[] data, int cur )  
{   
    int min = findMinPos( data, cur, cur );

    int minValue = data[min];
    data[min] = data[cur];
    data[cur] = minValue;
}

The minimum will recursively determined in findMinPos(). The whole idea of recurseiv programming is to use the returnvalues of an inner method call instead of using a loop. What you need is an overall break condition (in your case the length of the array) and usually multiple return statements.

This one here will do the trick:

private static int findMinPos( int[] data, int cur, int minPosSoFar )
{
    if(cur < data.length)
    {
        if(data[cur] < data[minPosSoFar]) // set new minimum to position cur
        {
            return findMinPos(data, cur + 1, cur);
        }
        else // keep old minimum
        {
            return findMinPos(data, cur + 1, minPosSoFar);
        }
    }

    return minPosSoFar;
}

And since the multiple return statements in the if-else block makes the code long and messy you can shorten it like this

private static int findMinPos( int[] data, int cur, int minPosSoFar )
{
    if(cur < data.length)
    {
        return (data[cur] < data[minPosSoFar]) ? 
            findMinPos(data, cur + 1, cur) :
            findMinPos(data, cur + 1, minPosSoFar);
    }

    return minPosSoFar;
}

durron597 · Accepted Answer · 2013-05-08 13:49:59Z

They have given you pseudocode. Just do exactly what it says. First change the instructions to step by step.

Compare this entry's value (if it is a valid entry) with the value in the entry "minPosSoFar".
If this value is less, then this entry is now the "minPosSoFar".
Recurse for the rest of the array.

So:

private static int findMinPos( int[] data, int cur, int minPosSoFar )
{
  if (cur < data.length) { // Needed for stopping at the end of the array
    if (data[cur] < data[minPosSoFar]) { // 1.
      minPosSoFar = cur; // 2.
    }
    return findMinPos(data, cur+1, minPosSoFar); // 3.
  }
  return minPosSoFar;
}

Since this is for school, I don't want to do the whole thing for you, hopefully this will give you a good idea what to do.

Collectives™ on Stack Overflow

Converting pseudocode for array minimum into Java code, using recursion

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related