Insertion Baseball

O aspeto bom de adaptar o selection sort para o problema do basebol é que sabemos que isto funciona (desde que a nossa adaptação esteja correta). O que é muito melhor que o nosso primeiro e simplório algoritmo, que é incapaz de convergir à solução em algumas situações. Mas, na verdade, o selection sort também não é perfeito, pois requer muitas trocas: temos que trazer o espaço vazio para e jogador selecionado e então levar o jogador e o espaço vazio à posição e mais. Podemos fazer melhor.

Por exemplo, cada jogador pode correr por uma longa distância da posição inicial dele para o objetivo. Portanto, pode ser mais interessante dividir o campo em duas partes: uma à esquerda onde todos os jogadores estejam ordenados relativamente uns aos outros e outra à direita onde os jogadores ainda estejam nas posições iniciais deles. Então, em cada iteração, escolhemos o jogador na fronteira entre as áreas ordenada e não ordenada (ou sejam o jogador mais à esquerda da parte não ordenada) e moveremo-lo para a esquerda (dentro da parte ordenada) até que alcance a posição dele (ou seja, até a posição onde seja maior que o vizinho dele da esquerda). Isto pode, pelo menos, reduzir o trajeto dos jogadores à área ordenada já que usamos o mais perto da fronteira.

Na verdade, é exatamente isto que o insertion sort deve fazer: manter uma área ordenada na esquerda e pôr iterativamente o jogador na fronteira com esta posição dentro da área ordenada. Isto é bom, já que sabemos que nosso algoritmo não é inerentemente "flawed" pois adaptamos um algoritmo bem conhecido.

O mais fácil de adaptar o insertion sort ao problema do basebol é considerar todas as posições como adjacentes e esquecer-se das bases. Para isto, definimos os métodos getColor[!c]Insert[/!](pos), move[!c]Insert[/!](pos) e getHole[!c]Insert[/!]() que usam, todos, um único inteiro para designar uma dada posição. Estas funções simplesmente convertem a forma de especificar uma posição para em seguida chamar as funções usuais para interagir com o mundo. Se tem um index e quer convertê-lo a base,pos, para então a base=index/2 e pos=index%2. Para calcular o reverso, index=base*2+pos (isto funciona, pois getPositionsAmount() sempre retorna 2).

Para o algoritmo em si, deve primeiro mover o espaço vazio à posição 1. A posição 0 é considerada como a área ordenada (de tamanho 1 por enquanto) enquanto que a área acima de 2 é a área não-ordenada. Então fazemos uma iteração para ordenar cada elemento da área não-ordenada. Já que esta iteração é um pouco complexa, deve pensar no invariante dela do loop, ou seja, a condição que é verdadeira antes e depois do loop e que explica que o loop satisfaz o objetivo dele. Aqui, o invariante do loop é duplo: Primeiro, o espaço vazio está entre a área ordenada e a não-ordenada is between the sorted area and the unsorted area, and then, the every elements of the sorted area are ... well sorted relatively to their neighbors.

Então, o corpo do loop para ordenar um elemento deve primeiro empurrar para baixo o espaço vazio e os elementos dentro da área ordenada até que o elemento seja maior que o elemento que está depois na área ordenada (2 movimentos por posição para se mover) e então mover o espaço vazio de volta para sua posição entre as áreas ordenadas e não-ordenadas (1 movimento por posição).

Uma vez que insira o último elemento dentro da área ordenada, o seu conjunto como um todo estará ordenado e terá terminado. Vou deixar como surpresa os casos da fronteira que vão precisar de alguns pequenos ajustes no seu algoritmo para funcionar corretamente :)