Tri de crêpes

1. Algorithme de tri de crêpes
2. Exemple de tri de crêpes
3. Implémentation de l’algorithme de tri de crêpes
4. Complexité de l’algorithme de tri de crêpes

Le tri de crêpes est un algorithme de tri basé sur l’inversion. Il est basé sur le problème réel de ressembler à des crêpes sur une assiette à l’aide d’une spatule. Il tire son nom de l’opération de retournement utilisée dans l’algorithme, analogue au retournement des crêpes. Contrairement à la plupart des algorithmes de tri qui tentent de minimiser le nombre de comparaisons nécessaires pour effectuer le tri, il tente de trier le tableau en un minimum d’inversions. Tout comme [selection sort](/fr/tutorial/algorithm/selection-sort/, il place également l’élément maximum à la fin.

Algorithme de tri de crêpes

Supposons que nous ayons un tableau non trié A[] contenant n éléments.

PancakeSort()

Flip()

Exemple de tri de crêpes

Supposons que nous ayons le tableau : (3, 5, 2, 1, 7, 6, 4). Nous allons le trier en utilisant l’algorithme de tri des pancakes.

• Première itération

mi = 4, curr = 7

• Deuxième tour

mi = 1, curr = 6

• Troisième tour

mi = 2, curr = 5

• Quatrième tour

mi = 0, curr = 4

• Cinquième tour

mi = 2, curr = 3

• Sixième tour

mi = 0, curr = 2

Nous obtenons le tableau final trié comme suit : 1, 2, 3, 4, 5, 6, 7.

Implémentation de l’algorithme de tri de crêpes

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

Complexité de l’algorithme de tri de crêpes

Complexité temporelle

• Cas moyen

En moyenne, les comparaisons n-i sont faites dans le ième passage du tri de crêpes. Donc, s’il y a des itérations n, alors la complexité temporelle moyenne peut être donnée par :

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

La complexité temporelle est donc de l’ordre de [Big Theta] : O(n²). Elle peut également être calculée en comptant le nombre de boucles. Il y a un total de deux boucles de n itérations rendant la complexité : n*n = n².

• Pire cas

Le pire des cas se produit lorsque les éléments alternent entre petits et grands éléments. Un total de 2n-3 flips est nécessaire. Le nombre de flips requis est de l’ordre de O(n). Le pire cas de complexité temporelle est [Big O] : O(n²).

• Meilleur cas

Dans le meilleur des cas, le tableau est déjà trié et aucun retournement n’est nécessaire. Le meilleur cas de complexité temporelle est [Big Omega] : O(n).

Complexité spatiale

La complexité spatiale de cet algorithme est O(n) car aucune mémoire supplémentaire autre qu’une variable temporaire n’est nécessaire.