Pancake Sorting in Java

In the pancake sorting method, the array must be sorted using just one operation, which is:

Flip the arrays arr at index 0 to index j by using flipArr(arr, h).

Other sorting algorithms often aim to sort an array's elements using the fewest possible element comparisons. Therefore, using pancake sorting, we concentrate on arranging the array's items in a way that causes the fewest reversals.

The assignment is to sort the supplied array from an unsorted array. Only the following array operations are permitted.

flip(arr, s): Reverse array from 0 to s

Example 1:

Input: arr[] = { 24, 9, 19, 10, 11, 5, 8 }

Output: { 5, 8, 9, 10, 11, 19, 24}

Input: arr[] = { 0, 0, 1, 0, 1 }

Output: { 0, 0, 0, 1, 1 }

Pancakes Sorting Steps

The objective is to sort the series in as few reversals as feasible, in contrast to a standard sorting algorithm, which seeks to arrange with both the fewest comparisons possible.

The stages involved in sorting pancakes are as follows.

• Start well with present size, which would be equal to s, then lower it by 1 if it is greater than 1. Let's say that the currSize is used to reflect the current size. Do the next step for every single currSize at this point.
• Lookup of the index in the array arr[0... currSize - 1] where the largest element resides Let's say the index is "idx."
• call flipArr(arr, idx)
• call flipArr (arr, currSize - 1)

The implementation

Using the methods outlined above, the following code demonstrates how to achieve pancake sorting.

public class PancakeSortingDemo  
{  
// it is used Reverse the array as arr[0 ... h]   
public void flipArr(int arr[], int h)  
{  
int c, begin = 0;  
while (begin < h)  
{  
c = arr[begin];  
arr[begin] = arr[h];  
arr[j] = c;  
begin = begin + 1;  
h = h - 1;  
}  
}  
// Returning the element's 
// maximum index, which is included in the 
// array arr[0...a- 1].
public int findMax(int arr[], int a)  
{  
int index, h;  
for (index = 0, h = 0; h < a; ++h)  
{  
if (arr[h] > arr[index])  
{  
index = h;  
}  
}  
return index;  
}  
// The primary method uses flip operations to 
// sort the supplied array.
public int pancakeSorting(int arr[], int a)  
{  
// Change the current size with 1 
// starting with the full array and going through 
// each element one by one.
for (int curSize = s; curSize > 1; --curSize)  
{  
// Find the maximum element's 
// index in the array 
// arr[0..cur size-1].
int index = findMax(arr, curSize);  
// Adding the maximum element, 
// if it is not already there, 
// towards the end of the existing array.
if (index != curSize - 1)  
{  
// We must first transfer 
// the greatest item to the beginning in order 
// to relocate the last element.
flipArr(arr, index);  
// The current array is being reversed in 
// order to move a maximum number to the end.
flipArr(arr, curSize - 1);  
}  
}  
return 0;  
}  
// a practical way for showing the array arr[]
public void displayArray(int arr[], int a)  
{  
for (int h = 0; h < a; h++)  
{  
System.out.print(arr[h] + " ");  
}  
System.out.println("");  
}  
// It is the main method   
public static void main (String argvs[])  
{  
int arr[] = {35, 99, 209, 102, 113, 65, 37, 67, 909};  
int a = arr.length;  
  
// making an object of the PancakeSortingDemo class
PancakeSortingDemo sr = new PancakeSortingDemo();  
System.out.println("The input array is: ");  
obj.displayArray(arr, a);  
obj.pancakeSorting(arr, a);  
System.out.println(" \nThe array after sorting is: ");  
obj.displayArray(arr, a);  
}  
}  

Output:

The input array is:
35  99  209  102  113  65  37  67  909


The array after sorting is: 
35  37  67  99  102  113  209  909

Let us try to understand with the explanation of it briefly.

We have carried a similar work to selection sort. The array's current size has been decreased by 1 after the maximum element was placed at the end. The current size keeps becoming smaller until the entire array is sorted.