Como corrigir esse algoritmo de classificação ímpar-par-mesclagem não-recursivo?
Eu estava procurando por um algoritmo de classificação ímpar-par-ímpar não recursivo e encontrei 2 fontes:
um livro deSedgewick R.estaPergunta SOAmbos os algoritmos são idênticos, mas falsos. A rede de classificação resultante não é uma rede de classificação de pares ímpares.
Aqui está uma imagem da rede resultante com 32 entradas. Uma linha vertical entre duas linhas horizontais significa comparar o valor a [x] com um [y], se maior, troque os valores na matriz.
Copiei o código de Java para C e substitui oexch função por umprintf para imprimir os candidatos à troca.
Quando se desenha um diagrama dos pares, pode-se ver que muitos pares são gerados.
Alguém tem uma idéia de como corrigir esse algoritmo?
Por que preciso de uma versão não recursiva?
Eu quero transformar essa rede de classificação em hardware. É fácil inserir estágios de pipeline em algoritmos não recursivos.
Também investiguei a versão recursiva, mas é muito complexo transformar o algoritmo em hardware em pipeline.
Meu código C:
#include <stdlib.h>
#include <stdio.h>
void sort(int l, int r)
{ int n = r-l+1;
for (int p=1; p<n; p+=p)
for (int k=p; k>0; k/=2)
for (int j=k%p; j+k<n; j+=(k+k))
for (int i=0; i<n-j-k; i++)
if ((j+i)/(p+p) == (j+i+k)/(p+p))
printf("%2i cmp %2i\n", l+j+i, l+j+i+k);
}
int main(char* argv, int args)
{ const int COUNT = 8;
sort(0, COUNT);
}
O resultado:
0 -o--------o-------------------------o---------------o-------------------------
| | | |
1 -o--------|-o------o----------------|-o-------------o-o-----------------------
| | | | | |
2 -o-o------o-|------o-o--------------|-|-o----o--------o-o---------------------
| | | | | | | | |
3 -o-o--------o--------o--------------|-|-|-o--|-o--------o-o-------o-----------
| | | | | | | |
4 -o-o-o----o---o----o-----o----------o-|-|-|--o-|-o--------o-o-----o-o---------
| | | | | | | | | | | | | |
5 -o-o-o----|-o-|-o--o-o---o-o---o------o-|-|----o-|-o--------o-o-----o-o---o---
| | | | | | | | | | | | | |
6 -o-o-o-o--o-|-o-|----o-o---o-o-o-o------o-|------o-|----------o-o-----o-o-o-o-
| | | | | | | | | | | | | |
7 -o-o-o-o----o---o------o-----o---o--------o--------o------------o-------o---o-
Quando conhecer os pares de trocas corretos e o algoritmo for igual à imagem, eu o traduzirei em VHDL para testes na minha plataforma de hardware.
Outras implementações de rede de classificação de hardware de código aberto:
PoC.sort.sortnet.oddevensortPoC.sort.sortnet.bitonicsortApêndice:
A combinação de pares ímpares (também conhecida como classificação de Batcher) é como classificação bitônica (para não confundir com a classificação bitônica de Batcher). Porém, no hardware, esse algoritmo tem uma complexidade de tamanho melhor que a classificação bitônica, enquanto a latência é a mesma.
Esses algoritmos podem ser implementados com um bom uso de recursos em comparação com algoritmos rápidos de software como o quicksort.
Wikipedia:ímpar-par mescla
Nota:
Como as redes de classificação são estáticas e independentes dos valores de entrada, nenhuma comparação e troca são necessárias para gerar a rede. Essa é uma das razões pelas quais ele pode ser transformado em hardware. Meu código gera os índices para as operações de comparação. No hardware, essas conexões verticais serão substituídas por circuitos de comparação e troca. Portanto, os dados não classificados percorrerão a rede e, no lado da saída, serão classificados.