C program for pancake sorting?

This C program implements pancake sorting on an array of integers.

Pancake sort is a variant of the sorting problem in which the only allowed operation is to reverse elements of certain prefixes in the sequence.

Pancake sort is a variant of the sorting problem in which the only allowed operation is to reverse elements of certain prefixes in the sequence. p>

Pancake sorting is a colloquial term referring to the mathematical problem of sorting an unordered stack of pancakes in order of size by inserting a spatula into the pancake stack. Any point and use to flip all pancakes with pancakes on top. The number of pancakes is the minimum number of flips required for a given number of pancakes

Input:5,3,2,1,4
Output:1 2 3 4 5

Explanation

This is a variant of the sorting problem where the only allowed operation is to reverse something in the sequence The prefixed element. Unlike traditional sorting algorithms that try to sort with as few comparisons as possible, the goal is to sort a sequence with as few inversions as possible. A variation of this problem has to do with burnt pancakes, where every pancake has a burnt side, and all pancakes must end up with the burnt side on the bottom.

Example

#include <iostream>
using namespace std;
void do_flip(int *, int, int);
int pancake_sort(int *list, unsigned int length) {
   if (length < 2)
      return 0;
   int i, a, max_num_pos, moves;
   moves = 0;
   for (i = length;i > 1;i--) {
      max_num_pos = 0;
      for (a = 0;a < i;a++){
         if (list[a] > list[max_num_pos])
            max_num_pos = a;
      }
      if (max_num_pos == i - 1)
         continue;
      if (max_num_pos){
         moves++;
         do_flip(list, length, max_num_pos + 1);
      }
      do_flip(list, length, i);
   }
   return moves;
}
void do_flip(int *list, int length, int num) {
   int swap;
   int i = 0;
   for (i=0;i < --num;i++) {
      swap = list[i];
      list[i] = list[num];
      list[num] = swap;
   }
}
int main(int argc, char **argv) {
   int arr[]={5,3,2,1,4};
   int n=5;
   int moves=pancake_sort(arr, n);
   for (int i = 0;i < n;i++) {
      printf("%d ", arr[i]);
   }
   printf(" - with a total of %d moves</p><p>", moves);
}

The above is the detailed content of C program for pancake sorting?. For more information, please follow other related articles on the PHP Chinese website!