A maior parte dos algoritimos de ordenação trabalha com comparações entre valores, essas comparações tomam algum tempo de processamento e no pior caso devem ser feitas n comparações no mínimo.

Objetivos

O objetivo é implementar um circuito que faça ordenação sem utilizar nenhuma comparação, a coisa deve funcionar da seguinte forma, n dados entram no circuito e eles são pré - ordenados na hora que entram sem gastar tempo efetivo algum para ordenar.

Isso e possível construindo algo semelhante a um bucketsort usando multiplexadores e algumas portas, só complicando na hora de dar a saída, veja o esboço do funcionamento do circuito:

- Entrada: São os n bits de cada palavra de entrada a serem ordenadas.

- Saída: São os n bits de Saída com as palavras ordenadas em paralelo.

- Insere/Remove: Decide se quer inserir ou remover palavra no conjunto.

- Modo Entrada / Modo Saída: Decide se quer mudar conjunto de palavras a serem ordenadas ou se quer obter a saída, quando já acabaram as manipulações de entrada.

O tempo gasto para ordenar um amostra de elementos cujo maior

elemento seja de tamanha X gastaria tempo constante independente

do numero de entradas, no caso o circuito receberia as entradas

e já devolveria os elementos ordenados sem comparar nada gastando

apenas um tempo ínfimo de passar por um multiplexador e alterar

o estado de um FF(ou latch), na hora da saída e que o tempo gasto

e um pouco maior, se a saída for em serie teremos n(numero de

elementos) vezes o tempo de um registrador ser carregado.

Simulação na UP1 do Altera

A simulação devera ter um seletor para adicionar/remover elementos e um seletor para modos de operação(modo insere/remove(entradas), modo demonstrar dados ordenados(saída), na demonstração serão usados 8 seletores, um botão e o display de 7 segmentos só para mostrar que funciona, no caso as palavras seriam um pouco pequenas(6 bits) mas fica um projeto mais enxuto usando o display de 7 segmentos e só um conjunto de seletores.

Esboço do funcionamento do circuito na placa.

Nesse esboço os elementos entram no registrador selecionando bit a bit cada um deles e apertando o "Read Trigger" para carregar, para isso o seletor Entrada/Saída deve estar na posição de entrada e o seletor Insere/remove deve estar em Insere, nesse caso uma palavra será carregada.

Para remover o processo é o mesmo de inserção com o seletor Remove/Insere na posição Remove.

Se o seletor Entrada/Saída estiver em Saída 6 bits de Saída representarão as palavra ordenadas, a cada vez que o Botão de "Read Trigger" for apertado uma nova palavra de saída surgira.

Considerações Finais

É possível fazer a saída ser mais rápida trocando o botão por um clock, e ainda, para testes de velocidade e eficiência pode-se usar vários clocks na entrada combinando valores entre si e calculando o tempo de ordenação de varias amostras de conjuntos de palavras de 6 bits.