Pfannkuchen sortieren

1. Pfannkuchen-Sortieralgorithmus
2. Beispiel für Pfannkuchensortierung
3. Implementierung des Pancake-Sortieralgorithmus
4. Pancake-Sortieralgorithmus Komplexität

Pfannkuchensortierung ist ein umkehrbasierter Sortieralgorithmus. Er basiert auf dem realen Problem, Pfannkuchen auf einem Teller mit Hilfe eines Spatels zu ähneln. Seinen Namen hat er von der im Algorithmus verwendeten Flip-Operation, die dem Wenden von Pfannkuchen ähnelt. Im Gegensatz zu den meisten Sortieralgorithmen, die versuchen, die Anzahl der für die Durchführung der Sortierung erforderlichen Vergleiche zu minimieren, versucht er, das Array in möglichst wenigen Umkehrungen zu sortieren. Genau wie selection sort platziert auch er das maximale Element an das Ende.

Pfannkuchen-Sortieralgorithmus

Nehmen wir an, dass wir ein unsortiertes Array A[] mit n Elementen haben.

PancakeSort()

Flip()

Beispiel für Pfannkuchensortierung

Angenommen, wir haben das Array: (3, 5, 2, 1, 7, 6, 4). Wir werden es mit dem Pancake-Sort-Algorithmus sortieren.

• Erste Iteration

mi = 4, curr = 7

• Zweite Iteration

mi = 1, curr = 6

• Dritte Iteration

mi = 2, curr = 5

• Vierte Iteration

mi = 0, curr = 4

• Fünfte Iteration

mi = 2, curr = 3

• Sechste Iteration

mi = 0, curr = 2

Wir erhalten das endgültige sortierte Array als 1, 2, 3, 4, 5, 6, 7.

Implementierung des Pancake-Sortieralgorithmus

#include <bits/stdc++.h>
using namespace std;
void flip(int arr[], int i) {
  int temp, start = 0;
  while (start < i) {
    temp = arr[start];
    arr[start] = arr[i];
    arr[i] = temp;
    start++;
    i--;
  }
}

int findMax(int arr[], int n) {
  int mi = 0;
  for (int i = 0; i < n; ++i)
    if (arr[i] > arr[mi]) mi = i;
  return mi;
}

void pancakeSort(int arr[], int n) {
  for (int i = n; i > 1; i--) {
    int mi = findMax(arr, i);
    if (mi != i - 1) {
      flip(arr, mi);
      flip(arr, i - 1);
    }
  }
}
int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  pancakeSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Pancake-Sortieralgorithmus Komplexität

Zeitkomplexität

• Durchschnittlicher Fall

Im Durchschnitt werden n-i Vergleiche im lten Durchgang von Pancake Sort durchgeführt. Wenn es also n Iterationen gibt, dann kann die durchschnittliche Zeitkomplexität durch gegeben werden:

(n-1) + (n-2) + (n-3) + ... + 1 = n*(n-1)/2

Daher ist die Zeitkomplexität in der Größenordnung von [Big Theta]: O(n²). Sie kann auch durch Zählen der Anzahl der Schleifen berechnet werden. Es gibt insgesamt zwei Schleifen mit n Iterationen, was die Komplexität ergibt: n*n = n².

• Schlimmster Fall

Der Worst-Case tritt auf, wenn die Elemente abwechselnd klein und groß sind. Es sind insgesamt 2n-3 Flips erforderlich. Die Anzahl der erforderlichen Umdrehungen liegt in der Größenordnung von O(n). Die Zeitkomplexität im schlimmsten Fall ist [Big O] O(n²).

• Bester Fall

Der beste Fall tritt ein, wenn das Array bereits sortiert ist und keine Flips erforderlich sind. Die Zeitkomplexität im besten Fall ist [Big Omega]: O(n).

Raumkomplexität

Die Platzkomplexität für diesen Algorithmus ist O(n), da außer einer temporären Variablen kein zusätzlicher Speicher benötigt wird.