Random Sort
Esse é simplesmente o algoritmo de ordenação de dados mais rápido que foi inventado pelo homem até agora.
Origem do Algorítmo[editar]
Depois de uma semana de diarréia após tomar vermífugos, um desprogramador viu que os vermes que ele tinha colocado no vaso sanitário se moviam caóticamente em busca de abrigo. Mas em frações de segundo, todos os vermes ficaram posicionados lado a lado em ordem de tamanho, desde o menor até o maior.
Imediatamente ele compreendeu que o fator responsável pela rápida ordenação dos vermes foi o movimento aleatório deles, e com isso ele descobriu o chamado Random Sort (aka. Monkey Sort).
Performance[editar]
A quantidade média estimada de comparações entre itens é de , e a média de trocas de itens é de . Mas em certas condições, que ocorrem com probabilidade de , o número de comparações é de e o número de trocas é menor que , algo que não é conseguido nem pelos algoritmos mais complexos como heapsort ou quicksort.
Código fonte[editar]
Segue abaixo o código fonte desse método de ordenação revolucionário:
import java.util.Random;
public final class RandomSort {
public static long swapCount;
public static long compareCount;
private static final Random RND = new Random();
// Impede que algum animal tente criar uma instancia dessa classe
private void RandomSort() {}
public static <E extends Comparable<? super E>> void sort(E[] values) {
boolean isSorted = false;
swapCount = 0;
compareCount = 0;
// Enquanto os dados nao estiverem ordenados...
while (!isSorted) {
// Inverte uma quantidade aleatoria de pares de itens aleatorios
int swaps = RND.nextInt(values.length);
swapCount += swaps;
while (swaps-- > 0) {
int i = RND.nextInt(values.length);
int j = RND.nextInt(values.length);
E aux = values[i];
values[i] = values[j];
values[j] = aux;
}
// Verifica se os dados estao ordenados
isSorted = true;
for (int index = 1; index < values.length && isSorted; index++) {
compareCount++;
if (values[index].compareTo(values[index-1]) < 0)
isSorted = false;
}
}
}
}
Teste de performance[editar]
Foi usado o seguinte código fonte para testar o método de ordenação. O conjunto de dados usado é {5, 4, 3, 2, 1}, e o resultado obtido foi {1, 2, 3, 4, 5} em todas as execuções do programa.
public static void main(String[] args) {
Integer values[] = new Integer[5];
long numberOfTests = 0;
while (RandomSort.swapCount != 2 || RandomSort.compareCount != 4) {
values[0] = 5;
values[1] = 4;
values[2] = 3;
values[3] = 2;
values[4] = 1;
RandomSort.sort(values);
System.out.println(swapCount + " swaps and " + compareCount + " comparations");
numberOfTests++;
}
System.out.println("Number of tests : " + numberOfTests);
}
Segue abaixo a quantidade de comparações e a quantidade de trocas obtidas nas simulações, que foram feitas até obter o resultado ideal (2 trocas e 4 comparações):
140 swaps and 111 comparations 613 swaps and 520 comparations 394 swaps and 323 comparations 390 swaps and 298 comparations 185 swaps and 143 comparations 538 swaps and 453 comparations 461 swaps and 387 comparations 391 swaps and 305 comparations 343 swaps and 287 comparations 497 swaps and 455 comparations 205 swaps and 206 comparations 216 swaps and 173 comparations 81 swaps and 65 comparations 97 swaps and 77 comparations 313 swaps and 286 comparations 539 swaps and 481 comparations 127 swaps and 106 comparations 160 swaps and 123 comparations 28 swaps and 27 comparations 1029 swaps and 949 comparations 93 swaps and 82 comparations 915 swaps and 760 comparations 326 swaps and 278 comparations 158 swaps and 129 comparations 117 swaps and 117 comparations 529 swaps and 410 comparations 139 swaps and 156 comparations 855 swaps and 717 comparations 204 swaps and 176 comparations 8 swaps and 11 comparations 283 swaps and 259 comparations 245 swaps and 203 comparations 178 swaps and 186 comparations 205 swaps and 179 comparations 67 swaps and 56 comparations 894 swaps and 748 comparations 346 swaps and 354 comparations 140 swaps and 86 comparations 355 swaps and 322 comparations 756 swaps and 622 comparations 462 swaps and 367 comparations 348 swaps and 301 comparations 313 swaps and 288 comparations 280 swaps and 268 comparations 287 swaps and 245 comparations 266 swaps and 228 comparations 668 swaps and 537 comparations 689 swaps and 623 comparations 99 swaps and 83 comparations 96 swaps and 74 comparations 123 swaps and 78 comparations 245 swaps and 177 comparations 96 swaps and 66 comparations 647 swaps and 587 comparations 226 swaps and 177 comparations 443 swaps and 402 comparations 45 swaps and 43 comparations 198 swaps and 152 comparations 8 swaps and 11 comparations 219 swaps and 202 comparations 374 swaps and 352 comparations 783 swaps and 603 comparations 370 swaps and 337 comparations 986 swaps and 866 comparations 164 swaps and 143 comparations 68 swaps and 63 comparations 373 swaps and 304 comparations 212 swaps and 189 comparations 15 swaps and 13 comparations 419 swaps and 333 comparations 56 swaps and 62 comparations 36 swaps and 38 comparations 249 swaps and 188 comparations 372 swaps and 354 comparations 146 swaps and 139 comparations 105 swaps and 68 comparations 174 swaps and 119 comparations 59 swaps and 44 comparations 292 swaps and 234 comparations 764 swaps and 648 comparations 183 swaps and 165 comparations 458 swaps and 375 comparations 590 swaps and 521 comparations 44 swaps and 48 comparations 119 swaps and 95 comparations 551 swaps and 427 comparations 1429 swaps and 1212 comparations 16 swaps and 15 comparations 183 swaps and 176 comparations 783 swaps and 629 comparations 1059 swaps and 825 comparations 147 swaps and 118 comparations 527 swaps and 408 comparations 256 swaps and 229 comparations 19 swaps and 14 comparations 146 swaps and 116 comparations 16 swaps and 18 comparations 1197 swaps and 1013 comparations 568 swaps and 465 comparations 291 swaps and 263 comparations 409 swaps and 317 comparations 730 swaps and 632 comparations 198 swaps and 171 comparations 479 swaps and 379 comparations 83 swaps and 88 comparations 51 swaps and 56 comparations 527 swaps and 398 comparations 28 swaps and 20 comparations 824 swaps and 663 comparations 199 swaps and 150 comparations 660 swaps and 568 comparations 448 swaps and 381 comparations <b>2 swaps and 4 comparations</b> Number of tests : 113
Realmente, um algoritmo que consegue reordenar o conjunto {5, 4, 3, 2, 1} fazendo apenas 2 trocas e 4 comparações não pode ser desconsiderado. É o algoritmo de ordenação mais rápido do mundo!
Problemas[editar]
Infelizmente, em raras condições, que ocorrem com probabilidade de , o que é bem menos que a quantidade de casos em que a quantidade de trocas/comparações é mínima (), o algoritmo nunca completa a ordenação dos dados (Veja que no exemplo acima, o algoritmo chegou a fazer 1429 trocas e 1212 comparações, o que não foi tão ruim assim levando em conta que o conjundo de dados tinha 5 elementos).
Ainda estamos trabalhando para encontrar uma solução para esse caso, mas por enquanto estamos usando um "timeout" de 1E+999 minutos para o algoritmo, sendo que depois de transcorrer esse tempo, ele vai executar o quicksort para completar a ordenação.
Referências[editar]
Na verdade, esse algoritmo existe há algum tempo e a complexidade dele já foi estudada por professores de universidades.
Se não acredita nisso, dê uma olhada nesse site: Inefficient sort algorithms