Converting loop implementation of Pancake Sort to a recursive implementation

Question

I am learning about recursion and wanted to convert my loops into a recursive function ? What should be the correct answer for this code be (Suppose that I already wrote the flip method to reverse elements in an array) ? Thanks,

/**
 * Sorts an array of integers by repeatedly reversing 
 * subranges within the array. Prints the flip sequence. 
 */ 
public static void  sort( int[] array)
{   
    int size = array.length;
    if (!Ordered(array, size)){
        for(int i = size-1; i > 0; i--)
        {
            int j = findMax(array, 0, i );
            int flipPosition;

            if( j != i )
            {
                if( j != 0 ) {
                    flip( array, 0, j );
                    flipPosition = size-j;
                    System.out.print( flipPosition + " " );
                }

                flip( array, 0, i );
                flipPosition = size-i;
                System.out.print( flipPosition + " " );
            }   
        }
    }
    System.out.println( 0 );
}

@Logan my method used pancake sort which identify the max number in array before flip it and sorting the number in ascending order from left to right. I do not know how to modified it into a recursive function. — Magic
– Magic, Commented Mar 4, 2016 at 4:19
Well recursion is no walk in the park. What I mainly use for sorting is an algorithm called quicksort. I go through and find out what my "base case" is and work from there. — Logan
– Logan, Commented Mar 4, 2016 at 4:22
Something that helped me when I was learning recursion: Isolate your bases cases and your actions. You must have definitions as your base ("base cases"). Your definitions allow you to "exit" the recursion. In other cases, you perform an action and call yourself again to keep doing an action until you reach the base cases. — BLaZuRE
– BLaZuRE, Commented Mar 4, 2016 at 4:23

pjs · Accepted Answer · 2016-03-04 20:48:53Z

0

I didn't want to write your program if this is homework, or ruin your fun if this is personal, so I've implemented a heavily commented recursive solution in Ruby. It basically boils down to do the flips necessary to move the maximum element to the end of the array, then apply the same logic to the subarray created by excluding the max. The recursive call returns the subarray sorted, so just append the max and pass the result back up the line. Base case for the recursion is when you get down to a single element, just return it.

# Function to find the index of the max element in an array.
# In case of ties, returns the lowest index
def max_index(a)
  a.each_index.inject { |memo, i| a[i] > a[memo] ? i : memo }
end

def pancake_sort(a)
  # An array with 0 or 1 elements is sorted (trivially),
  # just return it.  This is the base case for the recursion.
  return a if a.length < 2

  # Find location of the max, express it as the n'th element
  n = max_index(a) + 1

  # Flip the stack of the first n elements (max is last)
  # to put the max at the front, concatenate it with the
  # rest of the array, then flip the entire result.  This
  # will put max at the end. However, don't bother with all
  # that flipping if max was already at the end.
  a = (a.take(n).reverse + a.drop(n)).reverse if n < a.length

  # Recursively apply the logic to the subarray that excludes
  # the last (max) element.  When you get back the sorted
  # subarray, tack the max back onto the end
  return pancake_sort(a.take(a.length - 1)) << a[-1]
end

# Create an array of 20 random numbers between 0 and 99    
ary = Array.new(20) { rand(100) }
# Display the result
p ary
# Display the result after sorting
p pancake_sort(ary)

# Sample output:
# [70, 19, 95, 47, 87, 49, 53, 8, 89, 33, 22, 85, 91, 87, 99, 56, 15, 27, 75, 70]
# [8, 15, 19, 22, 27, 33, 47, 49, 53, 56, 70, 70, 75, 85, 87, 87, 89, 91, 95, 99]

answered Mar 4, 2016 at 20:48

pjs

20k4 gold badges30 silver badges64 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Magic Over a year ago

Yes I get what you are saying, wrote my code down but it still have problem somewhere, could you take a look for me please ? pastebin.com/qyYgDBkg

pjs Over a year ago

If you want folks to help you figure out why your code isn't working, you need to include the code within your question. That means all of the code, including the little utility functions you're invoking.

Magic Over a year ago

ah sory for that. Just thinking my code is too long. Here you go: pastebin.com/uQ3KXYXv. When I tried to run the test, it got whether StackFlow error or Java IndexOutOf Bound.

pjs Over a year ago

Not trying to be snarky here, but I hope you realize you're trying to shift the question. As written above, you asked how the iterative algorithm you post could be done with recursion. Now you're asking what's wrong with an implementation which you didn't provide and is still not part of the question.

pjs Over a year ago

I went ahead and looked at your code on pastebin. You have a couple of problems. First, you lack a return statement for your base case if (i <= 0), which is why you get the stack overflow. Second, your Order() check is screwing up for the first element. Since it's not really needed, I just took that check out and your code successfully sorted test cases for me.

Collectives™ on Stack Overflow

Converting loop implementation of Pancake Sort to a recursive implementation

1 Answer 1

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related