Diagrama interativo de redes de ordenacao com animacao passo a passo
Uma rede de ordenacao e uma rede de comparadores com estrutura fixa que ordena qualquer sequencia de entrada usando um arranjo predeterminado de operacoes de comparacao e troca. Ao contrario de algoritmos adaptativos como quicksort, uma rede de ordenacao realiza exatamente as mesmas comparacoes independentemente dos dados de entrada.
Cada comparador conecta dois fios (posicoes i e j) e direciona o menor valor para o fio superior e o maior para o fio inferior. Se os valores ja estao ordenados, nada muda; caso contrario, sao trocados.
A profundidade de uma rede de ordenacao e o numero maximo de camadas da entrada ate a saida. Comparadores na mesma profundidade nao tem dependencias de dados e podem ser executados simultaneamente em paralelo.
Algoritmos de ordenacao tradicionais decidem a proxima comparacao com base em resultados anteriores. Redes de ordenacao predeterminam todas as comparacoes, tornando-as ideais para implementacao em hardware e computacao paralela em GPU.
Redes de ordenacao sao amplamente utilizadas em: ordenacao em GPU (bitonic sort e a base da ordenacao CUDA), design de circuitos de ordenacao em hardware, ordenacao obliqua em computacao segura, otimizacao de consultas de banco de dados e ordenacao de pacotes de rede.
Para N pequeno, as contagens otimas conhecidas sao: N=4 requer 5 comparadores, N=5 precisa de 9, N=6 precisa de 12, N=7 precisa de 16, N=8 precisa de 19, N=9 precisa de 25, N=10 precisa de 29, N=16 precisa de 60. O principio 0-1 prova que verificar todas as 2^N entradas binarias e suficiente para confirmar a corretude da rede.