Eine Frage zur Pfannkuchenbestellung?

Hier sehen wir ein weiteres Sortierproblem namens Pfannkuchensortierung. Die Frage ist einfach. Wir haben ein Array. Wir müssen das klären. Wir können jedoch nur eine Operation namens rev(arr, i) verwenden. Dadurch wird das Element von arr von 0 auf die i-te Position umgedreht.

Die Idee ist wie eine Auswahlsortierung. Wir haben das größte Element immer wieder ans Ende gesetzt, um die Größe des Arrays zu reduzieren. Schauen wir uns den Algorithmus an, um diese Idee zu verstehen.

Algorithmus

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

Beispiel

#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] << " ";
}

Ausgabe

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

Das obige ist der detaillierte Inhalt vonEine Frage zur Pfannkuchenbestellung?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!