PancakeSort.java

import java.util.Arrays;

class PancakeSort {
  /* Reverses arr[0..i] */
  static void flip(int arr[], int k) {
    int tmp, start = 0, end = k;
    while (start < end) {
      tmp = arr[start];
      arr[start] = arr[end];
      arr[end] = tmp;
      start++;
      end--;
    }
  }

  // Returns index of the maximum element in arr[0..n-1]
  static int findMaxIndex(int arr[], int n) {
    int max, i;
    for (max = 0, i = 0; i < n; ++i)
      if (arr[i] > arr[max])
        max = i;
    return max;
  }

  /*
   * Start from current size equal to n and reduce current size by one while it’s greater than 1.
   * Let the current size be curr_size. Do following for every curr_size
   * a) Find index of the maximum element in arr[0..curr_size-1]. Let the index be ‘mi’
   * b) Call flip(arr, mi)
   * c) Call flip(arr, curr_size-1)
   */
  static int[] pancakeSort(int[] arr) {
    int c_size = arr.length;
    while (c_size > 1) {
      int mi = findMaxIndex(arr, c_size);
      flip(arr, mi);
      flip(arr, c_size - 1);
      --c_size;
    }
    return arr;
  }

  public static void main(String[] args) {
    int[] arr = {1, 5, 4, 3, 2};
    pancakeSort(arr);
    System.out.println(Arrays.toString(arr));
  }
}