Pancake Sort 1

Pancake Sort

Caio César Ponte Silva
Jonathan Nascimento Madeira

História
 No ano de 1975 ,o matemático Jacob E Goodman estava em casa dobrando toalhas para ajudar sua esposa. A pilha final ficou um pouco desorganizada, então ele decidiu reempilhar as toalhas dobradas por ordem de tamanho , a menor toalha dobrada ficaria no topo e a maior no fim da pilha , de modo que ele foi forçado a virar algumas toalhas , avaliar a situação , em seguida , virar mais uma vez algumas outras toalhas , e assim por diante.
 Durante a tentativa de organizar a pilha de toalhas, um problema curioso cruzou sua mente :
“Quantos flips (viradas) precisaria, no pior caso, para organizar as toalhas?”, então Goodman enviou o problema para o American

Definição do Problema
 O Problema da Ordenação de Panquecas tem como objetivo organizar uma pilha desordenada de panquecas em ordem de tamanho, dadas panquecas de diâmetros diferentes;  Ou seja, temos que organizar uma pilha de panquecas de tamanhos variados de forma que a menor fique no topo da pilha, a segunda menor fique logo abaixo dela, e assim sucessivamente até que a maior fique na parte inferior;
 Para isso, uma espátula pode ser inserida em qualquer lugar da pilha e usada para virar todas as panquecas acima dela;
 Virada ou flip consiste em inserir a espátula entre duas panquecas e então “virar” (inverter) as panquecas da

 Ao contrário de algoritmos de ordenação tradicional, que tenta resolver com o menor número de comparações possíveis, o objetivo desse algoritmo é ordenar a sequência em poucas viradas possível.

A figura mostra a espátula se posicionando entre duas panquecas e fazendo um flip.

emplificação da quantidade de flips no Pancake S

0 FLIP

1 FLIP

2 FLIPS

3 FLIPS

figura mostra os 6 arranjos possíveis para uma pilha de 3 panquec a 3 panquecas o número máximo de flips são 3.

A tabela seguinte mostra o número de panquecas n por pilha e o número de flips que necessitam:

Algoritmo
Pancake-Sort(s)
Para i ←