Une question sur la commande de crêpes ?

Ici, nous verrons un autre problème de tri appelé le tri des crêpes. La question est simple. Nous avons un tableau. Il faut régler ça. Mais nous ne pouvons utiliser qu’une seule opération appelée rev(arr, i). Cela fera basculer l'élément de arr de 0 à la ième position.

L'idée est comme un tri par sélection. Nous mettons à plusieurs reprises le plus grand élément à la fin pour réduire la taille du tableau. Regardons l'algorithme pour comprendre cette idée.

Algorithme

pancakeSort(arr, n)

Begin
   size := n
   while size > 1, do
      index := index of max element in arr from [0 to size – 1]
      rev(arr, index)
      rev(arr, size - 1)
      size := size - 1
   done
End

Exemple

#include<iostream>
using namespace std;
void rev(int arr[], int i) {
   int temp, st = 0;
   while (st < i) {
      temp = arr[st];
      arr[st] = arr[i];
      arr[i] = temp;
      st++;
      i--;
   }
}
int maxIndex(int arr[], int n) {
   int index, i;
   for (index = 0, i = 0; i < n; ++i){
      if (arr[i] > arr[index]) {
         index = i;
      }
   }
   return index;
}
int pancakeSort(int arr[], int n) {
   for (int size = n; size > 1; size--) {
      int index = maxIndex(arr, size);
      if (index != size-1) {
         rev(arr, index);
         rev(arr, size-1);
      }
   }
}
int main() {
   int arr[] = {54, 85, 52, 25, 98, 75, 25, 11, 68};
   int n = sizeof(arr)/sizeof(arr[0]);
   pancakeSort(arr, n);
   cout << "Sorted array: ";
   for (int i = 0; i < n; ++i)
   cout << arr[i] << " ";
}

Sortie

Sorted array: 11 25 25 52 54 68 75 85 98

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!