Bubble Baseball

Putz, nós adaptamos o insertion sort por que o selection sort precisava de muitos movimentos para colocar os jogadores selecionados em suas posições, mas o insertion sort necessita de uma quantidade estúpida de mudanças para alcançar os elementos de fronteira para suas posições dentro da área ordenada sem bagunçar os elementos já ordenados. No final, nossa variante "selection" era mais eficiente com pelo menos 3*amountOfBase movimentos para ordenar um elemento (1 para alcançar o espaço vazio ao lado do jogador, e 2 para colocar o espaço vazio e o jogador em posição) enquanto nossa variante "insertion" precisa de no máximo 3*amountOfPlayers para ordenar um elemento (2 para descer o espaço vazio e o jogador na posição, 1 para trazer o espaço vazio de volta para sua posição). Isto é duas vezes pior que ter dois jogadores por base. Pode ser possível melhorar o insertion sort movendo mais de um elemento enquanto desce, mas parece difícil (pelo menos, fazendo sem misturar os elementos já ordenados) e provavelmente isto apenas vai garantir que nossa variante "insertion" se torne tão eficiente quanto nossa variante "selection", não dramaticamente melhor.

Se não pudermos tornar o ordenamento mais rápido, podemos torná-lo mais fácil. Se pensar a respeito, parece natural adaptar a ordenção bolha para este problema: o buraco se torna a bolha que se move para cima e para baixo, ordenando um pouco o array a cada passagem. As linhas grandes são simples: "enquanto (while) não estiver ordenado, mova o buraco para baixo até a base 0 (movendo o maior jogador de cada base em cada passo) e então de volta à base maximal (movendo o menor jogador de cada base)". depois de um tempo, estáOrdenado() vai retornar verdadeiro e seu algoritmo vai parar.

Isto é tão fácil que vamos introduzir outra variante do problema, com mais de dois jogadores por base. Mas isto não vai te segurar por muito tempo, né?

Surpreendentemente, a variante bubble sort precisa de menos movimentos que as outras variantes. Isto é fantástico, por que normalmente, o bubble sort é muito pior que os outros algoritmos, mas isto é graças à boa combinação entre suas linhas grandes e o universo do basebal. E na verdade acontece bastante de um algoritmo escrito de forma agradável rodar de forma bem decente. Mas isto não é uma regra universal, como foi demontrado pelo algoritmo simplório do primeiro exercício, que era legal, simples e errado ;)