Упражнения на Java: Алгоритм сортировки блинчиков

Алгоритм сортировки Java: упражнение 14 с решением

Напишите программу на Java для сортировки массива заданных целых чисел, используя алгоритм сортировки по Блину.

Сортировка блинов - разговорный термин для математической задачи сортировки неупорядоченной стопки блинов в порядке их размера, когда шпатель может быть вставлен в любую точку стопки и использован для переворачивания всех блинов над ней. Число блинов - это минимальное количество бросков, необходимое для данного количества блинов. Впервые эту проблему обсудил американский геометр Джейкоб Э. Гудман. Это разновидность проблемы сортировки, в которой единственной допустимой операцией является обращение элементов некоторого префикса последовательности в обратном порядке.

Пример решения:

Java-код:

import java.util.Arrays;  
public class PancakeSort
{
   int[] heap;
 
   public String toString() {
      String info = "";
      for (int x: heap)
         info += x + " ";
      return info;
   }
 
   public void flip(int n) {
      for (int i = 0; i < (n+1) / 2; ++i) {
         int tmp = heap[i];
         heap[i] = heap[n-i];
         heap[n-i] = tmp;
      }      
     // System.out.println("flip(0.." + n + "): " + toString());
   }
 
   public int[] minmax(int n) {
      int xm, xM;
      xm = xM = heap[0];
      int posm = 0, posM = 0;
 
      for (int i = 1; i < n; ++i) {
         if (heap[i] < xm) {
            xm = heap[i];
            posm = i;
         }
         else if (heap[i] > xM) {
            xM = heap[i];
            posM = i;
         }
      }
      return new int[] {posm, posM};
   }
 
   public void sort(int n, int dir) {
      if (n == 0) return;
 
      int[] mM = minmax(n);
      int bestXPos = mM[dir];
      int altXPos = mM[1-dir];
      boolean flipped = false;
 
      if (bestXPos == n-1) {
         --n;
      }
      else if (bestXPos == 0) {
         flip(n-1);
         --n;
      }
      else if (altXPos == n-1) {
         dir = 1-dir;
         --n;
         flipped = true;
      }
      else {
         flip(bestXPos);      }
      sort(n, dir);
 
      if (flipped) {
         flip(n);
      }
   }
 
   PancakeSort(int[] numbers) {
      heap = numbers;
      sort(numbers.length, 1);
   } 
 
   public static void main(String[] args) {
      int numbers[] = {7, -5, 3, 2, 1, 0, 45};
      System.out.println("Original Array:");
      System.out.println(Arrays.toString(numbers));
      PancakeSort pancakes = new PancakeSort(numbers);
      System.out.println("Sorted Array:");
      System.out.println(Arrays.toString(numbers));
   }
}

Пример вывода:

 Оригинальный массив:
[7, -5, 3, 2, 1, 0, 45]
Сортированный массив:
[-5, 0, 1, 2, 3, 7, 45]]

Блок - схема:

Редактор кода Java:

Внесите свой код и комментарии через Disqus.

Предыдущий: Напишите Java-программу для сортировки массива заданных целых чисел, используя алгоритм сортировки Gnome.
Далее: Напишите программу на Java для сортировки массива заданных целых чисел с помощью алгоритма сортировки перестановок.