Random Sort

Origem: Desciclopédia, a enciclopédia livre de conteúdo.
Ir para: navegação, pesquisa

Esse é simplesmente o algoritmo de ordenação de dados mais rápido que foi inventado pelo homem até agora.

Origem do Algorítmo[editar]

Típico utilizador deste algoritmo.

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