Pancake sorting in java


You really might like the fact that idea of pancake sorting was given by Bill Gates.

Contents of page >
  • How Pancake sorting works ?
  • Full Program/SourceCode/Example of Pancake sorting in java>
  • Complexity of Pancake sorting in java >



How Pancake sorting works ?
Pancake sorting sorts the array using reversals(flips), rather than suing the comparisons.
We keep on placing maximum element at the end of the array and arrays size keeps on reducing by one..


Full Program/SourceCode/Example of Pancake sorting in java>
/**
*  write a program to sort array using pancake Sorting in java.
* This class holds reference of array, which has to be sorted using pancake sorting.
*/
class PancakeSorting {
   private int size;
   private int[] ar;
   private int index;
   /**
   * Constructor for initializing Array
   */
   public PancakeSorting() {
          size = 10;
          ar = new int[size];
          index = -1;
   }
   /**
   * This method inserts elements in Array.
   */
  
   public void insert(int value) {
          ar[++index] = value;
   }
   /**
   * This method Display Array
   */
   public void display() {
          for (int i = 0; i <= index; i++) {
                 System.out.print(ar[i]+" ");
          }
   }
   /**
   * This method Sort Array using pancake Sort in java
   */
   public void pancakeSortingMethod() {
          int maxIndex = 0;
          for (int n = index; n >= 0; n--) {
                 maxIndex = findMaxElementIndex(n);
                 if (maxIndex != n) {
                       // first move max to 1st pos
                       flip(maxIndex);
                       /*
                       * than reverse till specific pos i.e. we have got highest
                       * element at fist pos, move it to last Pos[i.e. not exactly at last
                       * pos, but at n'th pos]
                       */
                       flip(n);
                 }
          }
   }
  
   /**
   * Method returns index of maximum number till n'th position in array
   */
   private int findMaxElementIndex(int n) {
          int maxIndex = 0, value = ar[0];
          for (int i = 1; i <= n; i++) {
                 if (ar[i] > value) {
                       value = ar[i];
                       maxIndex = i;
                 }
          }
          return maxIndex;
   }
   /**
   * Method performs the required flip of position in arrays.
   */
   private void flip(int maxIndex) {
          int start = 0, temp = 0;
          while (start <= maxIndex) {
                 temp = ar[maxIndex];
                 ar[maxIndex] = ar[start];
                 ar[start] = temp;
                 start++;
                 maxIndex--;
          }
   }
}
/**
* Main class which calls Pancake sorting class
*/
public class PancakeSortingAlorithmExample {
   public static void main(String[] args) {
          PancakeSorting pancakeSorting = new PancakeSorting();
          pancakeSorting.insert(21);
          pancakeSorting.insert(32);
          pancakeSorting.insert(26);
          pancakeSorting.insert(24);
          pancakeSorting.insert(31);
          pancakeSorting.insert(39);
          pancakeSorting.insert(12);
          System.out.println("Display array before Pancake sorting : ");
          pancakeSorting.display();
          pancakeSorting.pancakeSortingMethod();
         
          System.out.println("\n\nDisplay array after Pancake sorting : ");
          pancakeSorting.display();
   }
}
/*OUTPUT
Display array before sorting :
21 32 24 26 31
Display array after pancake sorting :
21 24 26 31 32
*/

So, we wrote program to do Pancake sorting of array in java.


Complexity of Pancake sorting in java >
The time complexity of Pancake sorting  is  O(n2).
Total number of flips performed in pancake sorting are  O(n).


Summary >
So in this data structure tutorial we learned how Pancake sorting works. Program/Example of Pancake sorting in java, Complexity of Pancake sorting in java.

Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.



RELATED LINKS>

Sorting

Advanced Sorting

Searching







No comments:

Post a Comment