Cinco pessoas, vestidas com camisas numeradas de 1 a 5, formavam uma fila de maneira que a pessoa com a camisa número 3 estava no início da fila, a com a camisa número 4 no fim da fila, e a representação dessas pessoas, nessa fila, era 3 – 2 – 5 – 1 – 4, ou seja, 3 representa a pessoa com a camisa número 3, 2 representa a pessoa com a camisa número 2 e assim sucessivamente.

As seguintes regras foram usadas para ordenar essa fila:

1. A pessoa que está no início da fila troca de lugar com quem está atrás dela, caso seu número seja maior do que o número de quem está atrás, retrocedendo uma posição na fila. Essa mesma pessoa continua retrocedendo na fila enquanto seu número for maior do que o número da pessoa de trás ou se ela chegar ao fim da fila. Na fila dada, a pessoa 3 troca com a pessoa 2, e a fila fica 2 – 3 – 5 – 1 – 4, mas não troca de lugar com a pessoa 5, pois 3 < 5.

2. Se a pessoa que retrocedia não chegou ao fim da fila, quem estava atrás dela passa a retroceder, a partir da posição em que se encontrava, seguindo as mesmas regras de troca de lugar explicitadas pela regra (1). No caso, a pessoa 5 passa a retroceder e troca de lugar com a pessoa 1 e depois troca de lugar com a pessoa 4, e a fila fica 2 – 3 – 1 – 4 – 5.

3. Se quem retrocede chegou ao fim da fila, o processo se repete a partir da regra (1), mas se não chegou ao fim da fila, o processo continua de acordo com a regra (2). No caso, como a pessoa 5 chegou ao fim da fila, o processo recomeça com a pessoa 2, que não retrocede, pois 2 < 3, portanto a pessoa 3 passa a retroceder e troca de lugar com a pessoa 1, e a fila fica 2 – 1 – 3 – 4 – 5. Como a pessoa 3 não pode mais retroceder, pois 3 < 4, a pessoa 4 também não, pois 4 < 5 e a pessoa 5 já está no fim da fila, repete-se o processo a partir da regra (1), a pessoa 2 troca de lugar com a pessoa 1 e a fila fica 1 – 2 – 3 – 4 – 5.

4. Se ninguém trocar de lugar ao se aplicar as regras (1), (2) e (3) a todas as pessoas, a fila está ordenada e o processo terminado.

Observando que no exemplo dado houve 5 trocas de lugares, se tivermos 9 pessoas em fila, vestidas com camisas numeradas de 1 até 9 e seguindo as mesmas regras, o número de trocas de lugares para ordenar a fila 5 – 7 – 3 – 4 – 1 – 9 – 8 – 6 – 2 será