algorithm
Sort de crêpes

Crêpes Trier les informations de base

Pancake Sort est un terme familier pour désigner le problème mathématique du tri d'une pile désordonnée de crêpes par ordre de taille lorsqu'une spatule peut être insérée à n'importe quel point de la pile et utilisée pour retourner toutes les crêpes au-dessus. Un numéro de crêpe est le nombre minimum de retournements requis pour un nombre donné de crêpes.

Contrairement à un algorithme de tri traditionnel, qui tente de trier avec le moins de comparaisons possibles, le but est de trier la séquence dans le moins d’inversions possible.

L'idée est de faire quelque chose de similaire à Selection Sort. Nous mettons un à un l’élément maximum à la fin et réduisons la taille du tableau actuel de un.

Dissection du problème:

1. Besoin de commander les crêpes du plus petit (haut) au plus grand (bas), la pile de départ peut être rangée dans n'importe quel ordre.
2. Je peux seulement effectuer un retournement complet de la pile.
3. Pour retourner une crêpe spécifique au fond de la pile, vous devez d'abord la retourner vers le haut (puis la retourner vers le bas).
4. Pour commander chaque crêpe, il vous faudra un rabat vers le haut et un vers le bas pour atteindre son emplacement final.

Algorithme intuitif:

1. Trouvez le plus grand pancake hors-service et retournez-le vers le bas (vous devrez peut-être le retourner en haut de la pile en premier).

2. Répétez l'étape 1 jusqu'à ce que la pile soit commandée.

3. Ça y est, un algorithme en deux étapes fonctionnera.

Exemple d'algorithme de tri Pancake:

Espace auxiliaire: O(1)
Complexité temporelle: O(n^2)

Implémentation C #

public class PancakeSort
{
    private static void SortPancake(int[] input, int n)
    {
        for (var bottom = n - 1; bottom > 0; bottom--)
        {
            var index = bottom;
            var maxIndex = input[bottom];
            int i;
            for (i = bottom - 1; i >= 0; i--)
            {
                if (input[i] > maxIndex)
                {
                    maxIndex = input[i];
                    index = i;
                }
            }
            if (index == bottom) continue;
            var temp = new int[n];
            var j = 0;
            for (i = bottom; i > index; i--,j++)
            {
                temp[j] = input[i];
            }
            for (i = 0; i < index; i++, j++)
            {
                temp[j] = input[i];
            }
            if (temp.Length > j) temp[j] = input[index];
            for (i = 0; i <= bottom; i++)
            {
                input[i] = temp[i];
            }
        }
    }

    public static int[] Main(int[] input)
    {
        SortPancake(input, input.Length);
        return input;
    }
}