Vimos que CocktailSort melhora um pouco as coisas para as tartarugas (p.ex. pequenos valores próximos do fim da array), mas ainda é possível fazer melhor. ComboSort vem-les fornecer um atalho: ao invés de comparar valores adjacentes, comparamos valores separados por um intervalo ("gap") maior que 1. Desta forma, as tartarugas vão percorrer gap células em cada passagem. Naturalmente, temos que aplicar o algoritmo com distâncias decrescentes e terminar com gap=1 para garantir que a array está corretamente ordenada ao final. Escolher a distância correta e como diminuí-la é uma questão difícil, mas na prática, dividir por 1.3 depois de cada passagem leva a uma boa performance. Aqui está o pseudo-código correspondente:
gap = len; do if gap>1 then gap = gap / 1.3 i = O while i+gap < len do: if i and i+gap must be swapped, do it increase i by one while the gap is bigger than 1 or the last traversal swapped at least one pair[!scala]
Um detalhe perigoso é que temos que dividir o intervalo, que é um inteiro (ou do tipo Int), por 1.3, que é um Double. O sistema de tipos do scala não nos deixa fazer isto, por que tal discrepância normalmente significa um erro de programação. Como isto não é um erro neste caso, vamos ter que converter o intervalo para Double para o momento da operação e depois converter o resultado de volta para Int para armazená-lo no intervalo. Isto deve ser escrito desta forma:
gap = (gap.asInstanceOf[Double] / 1.3).asInstanceOf[Int]
Isto é meio exagerado, mas, na verdade, esta notação não é muito complexa. E lembre-se que o verificador de sintaxe é o seu amigo. Ás vezes é chato e irritante (como neste caso), mas frequentemente apanha bugs esquisitos que seriam trabalhosos para depurar se não fosse o verificador de sintaxe. E como os autores do Scala são pragmáticos, a expressão anterior pode ser simplificada:
gap = (gap.toDouble / 1.3).toInt
toDouble
e toInt
são apenas atalhos para as
expressões correspondentes asInstanceOf[Double]
e
asInstanceOf[Int]
. Não é muito genérico, mas é bem prático.
Este algoritmo foi inventado por Wlodek Dobosiewicz em 1980 e depois redescoberto e popularizado por Stephen Lacey e Richard Box, que o descreveram na Byte Magazine em Abril de 1991.