Codifique uma rotina de ordenação para colocar em ordem
crescente um vetor de inteiros de 8 bits com sinal,
utilizando o método de Bubble Sort, conforme exposto
em Knuth, The Art of Computer Programming, Vol 3, pg 107 e cujo código
em "pseudo Pascal" aparece abaixo.
(i) Codifique primeiramente a rotina em C e teste-a usando a
função rand8() apresentada abaixo, e que gera um vetor
de números aleatórios com sinal e 8 bits de precisão.
Esta função também grava o vetor num arquivo
ASCII num formato que V. pode cortar e colar diretamente no seu programa
em Assembler (escrevendo o vetor em ascii-hexadecimal facilitará
a depuração, veja a seguir ).
(ii) A fim de verificar a correção do seu programa, após a ordenação em C, grave no mesmo arquivo o vetor ordenado em linhas de comentário no formato ascii-hexadecimal conforme mostra um exemplo abaixo, de forma que ficará simples conferir o resultado da ordenação usando o Turbo Debugger.
(iii) Uma vez testado o seu programa com o Turbo Debugger acrescente rotinas (já desenvolvidas nas atividades 1 e 2 ) para apresentar no vídeo o vetor ordenado no formato ascii-hexadecimal (ou opcionalmente em ascii-decimal), usando a função de saída de string do DOS (int 21h, ah=09) .
Obs: (i) apresente os seus testes com um vetor de 32 entradas,
mas suponha que o tamanho máximo do vetor é <= 2**16 (isto
é, use índices de 16 bits).
(ii) Coloque comentários no seu programa em assembler associando
as linhas em assembler com o pseudo código abaixo.
(iii) Submeta uma listagem do programa em C, da sua saída, do
programa em Assembler (.lst), junto com a apresentação
no laboratório.
; Algoritmo de ordenação "Bubble Sort", adaptado
sem modificação de Knuth, Vol 3, pg 107:
; dados os registros K1,...,Kn ordená-los ("in place")
em odem crescente.
;
; BOUND:= n
; loop
; t:=0
; for j=1 to BOUND-1 do
; begin
; if Kj > Kj+1 then
; begin Kj <=> Kj+1 (troca Kj com Kj+1)
; t:=j
; end
; end
; if t=0 then break
; BOUND:= t
; endloop
Exemplo de rotina para gerar números aleatórios com sinal e precisão de 8 bits:
#include <stdlib.h>
#include<stdio.h>
#define TMAX 32
#define RANGE 128
FILE * fp;
void rand8(char tab[], unsigned int size)
/* generate random integers between -RANGE,+RANGE */
{ unsigned int i;
int sum;
fp = fopen("test.txt","w");
/* file to use later in assembler code */
srand(time());
/*comment this line to always get the same sequence */
printf("\nGenerating %d random signed integers:\n",size);
fprintf(fp,"tab: db ");
for (i=0; i<size; i++){
sum= rand()%(2*RANGE);
tab[i]= (sum <RANGE)?sum:RANGE-sum;
printf("%4d,",tab[i]);
fprintf(fp, "0x%-3x,", tab[i]);
}
printf("\n");
}
Exemplo de arquivo (test.txt) gerado pelo programa em C:
tab: db 0xffc4,0x7c ,0x1d ,0x29 ,0xffd0,0x22 ,0xffef,0x2e ,0xfff4,0xffb4,0x5b ,0x29 ,0x77 ,0x55 ,0xe ,0x17 ,0xff90,0x27 ,0xffe5,0xffbe,0xffd7,0xffb6,0x4b ,0xff8f,0xffdf,0xffd5,0xff82,0xffb1,0xfffc,0x2f ,0xffde,0xffe7,
;Sorted Array:
;0xff82,0xff8f,0xff90,0xffb1,0xffb4,0xffb6,0xffbe,0xffc4,0xffd0,0xffd5,0xffd7,0xffde,0xffdf,0xffe5,0xffe7,0xffef,0xfff4,0xfffc,0xe
,0x17 ,0x1d ,0x22 ,0x27 ,0x29 ,0x29 ,0x2e ,0x2f ,0x4b ,0x55 ,0x5b ,0x77
,0x7c ,