Archivo
Posts Tagged ‘Timer’
Métodos de Ordenamiento
5 enero, 2008
Deja un comentario
Por medio del siguiente ejemplo se ordena un vector de una determinada cantidad de elementos por los siguientes metodos y se compara el tiempo de implementacion. Por ultimo se ordenan los tiempos y se muestra los metodos ordenados por velocidad.
Metodos Involucrados:
Pivote
Burbuja
Cocktail sort(sarandeo o shaking)
Insercion
Selección
Shell
QuickSort
[spoiler]
Descripcion:
Ordenamiento de un vector(de menor a mayor), utilizando todos los metodos
Para determinar el tiempo que dura el ordenamiento, se emplea el timer
Se comparan los tiempos de ordenamiento de cada metodo.
NOTA: el compilador debe tener el modelo de memoria en HUGE
*/
#include
#include
#include
#include
#define BaseTmr 0x40
#define N 10000
//***************************************************************************
//Prototipo de Funciones
void InitHw(void);
void RestoreHw(void);
//Funciones de ordenamiento
void pivote(void);
void burbuja(void);
void shaking(void);
void seleccion(void);
void insercion(void);
void shell(void);
void quicksort(void);
void qs(int,int);
void (*ordenar[7]) (void)={pivote,burbuja,shaking,seleccion,insercion,shell,quicksort};
//Interrupcion
void interrupt far IsrTmr(void);
void interrupt far (*OldTmr) (void);
//***************************************************************************
//Variables Globales
struct t{
unsigned long int mseg;
unsigned char activar;
unsigned char tmr;
}tiempo;
//Vectores a Ordenar
//------------------
int vector[N];
int original[N];
int resultado[N];
int aux;
//***************************************************************************
void main(void){
unsigned long int i,j,k,pos;
char flag,mal;
unsigned long int reg[7];
char metodo;
/*
0 = PIVOTE
1 = BURBUJA
2 = SHAKING
3 = SELECCION
4 = INSERCION
5 = SHELL
6 = QSORT
*/
//Inicializacion de Variables
tiempo.activar=0;
tiempo.mseg=0;
tiempo.tmr=0;
InitHw();
clrscr();
printf("ORDENAMIENTO DE UN VECTOR de %u ELEMENTOS POR DIVERSOS METODOS",N);
//Cargar el vector con elementos aleatorios
printf("\nPresione una tecla para comenzar...");
getch();
randomize();
for (i=0;i
original[i]=vector[i]=random(65530);
}
//Ordenamiento
for(metodo=0;metodo<7;metodo++){
//Ejecutar el ordenamiento
tiempo.activar=1;
ordenar[metodo]();
tiempo.activar=0;
reg[metodo]=tiempo.mseg;
tiempo.mseg=0;
//Comprobar resultado
mal=0;
printf("\nComprobando...");
if(metodo==0) {
//Uso de referencia el pivote
for(k=0;k }else{
for(k=0;k
if(vector[k]!=resultado[k]){
mal=1;
}
}
}
if (mal) {
printf("ERROR");
}else{
printf("Ok");
}
//Reestablecer el Vector
for(k=0;k
}
printf("\n\nTiempos de ordenamiento:");
printf("\nPIVOTE: %u",reg[0]);
printf("\nBURBUJA: %u",reg[1]);
printf("\nSHAKING: %u",reg[2]);
printf("\nSELECCION: %u",reg[3]);
printf("\nINSERCION: %u",reg[4]);
printf("\nSHELL: %u",reg[5]);
printf("\nQSORT: %u",reg[6]);
getch();
RestoreHw();
}
//***************************************************************************
void InitHw(void){
//Configuracion del Timer
outportb(BaseTmr+3/*REG*/,(unsigned char)0x34); //0 0 1 1 0 1 0 0 (Cont 0 - LsbYMsb - Modo 2 - Sin BCD)
outportb(BaseTmr,(unsigned char)0xA9); //LSB
outportb(BaseTmr,(unsigned char)0x04); //MSB
//El timer ya se encuentra habilitado desde el pic
//Vector de Interrupciones
disable();
OldTmr=getvect(0x08);
setvect(0x08,IsrTmr);
enable();
}
//**************************************************************************
void RestoreHw(void){
//Vector de Interrupciones
disable();
setvect(0x08,OldTmr);
enable();
}
//**************************************************************************
void interrupt far IsrTmr(void){
tiempo.tmr++;
if(tiempo.activar) tiempo.mseg++;
if(tiempo.tmr==55){
tiempo.tmr=0;
OldTmr();
}else{
outportb(0x20,0x20); //EOI
}
}
//**************************************************************************
void pivote(void){
int i,j;
printf("\n\nPivote...");
for(i=0;i
for(j=i+1;j
if(vector[i]>vector[j]){
aux=vector[j];
vector[j]=vector[i];
vector[i]=aux;
}
}
}
}
//**************************************************************************
void burbuja(void){
int i;
char flag;
printf("\n\nBurbuja...");
do{
flag=0;
for(i=0;i
if(vector[i]>vector[i+1]){
aux=vector[i];
vector[i]=vector[i+1];
vector[i+1]=aux;
flag=1;
}
}
}while(flag);
}
//**************************************************************************
void shaking(void){
int i,j,k=0;
char flag;
printf("\n\nShaking...");
k=0;
do{
flag=0;
for(i=k;i
if(vector[i]>vector[i+1]){
aux=vector[i];
vector[i]=vector[i+1];
vector[i+1]=aux;
flag=1;
}
}
for(j=N-k-1;j>k;j--){
if(vector[j-1]>vector[j]){
aux=vector[j];
vector[j]=vector[j-1];
vector[j-1]=aux;
flag=1;
}
}
k++;
}while(flag);
}
//**************************************************************************
void seleccion(void){
int i,j;
int pos=0;
printf("\n\nSeleccion");
for(j=0;j
pos=j;
for(i=j+1;i
if(vector[pos]>vector[i])
pos=i;
if(pos!=j){
aux=vector[pos];
vector[pos]=vector[j];
vector[j]=aux;
}
}
}
//**************************************************************************
void insercion (void){
int i,k;
printf("\n\nInsercion...");
for(i=1;i
for(k=i-1,aux=vector[i];vector[k]>aux && k>=0;k--){
vector[k+1]=vector[k];
}
vector[k+1]=aux;
}
}
//**************************************************************************
void shell(void){
int L,m,i,j,k;
printf("\n\nShell...");
L=(int)floor(log(N)/log(2)); //Calculo del coeficiente
//logb(a)=logc(a)/logc(b)
for(m=L; m>=0; m--){
k=pow(2,m)-1; //Secuencia recomendada por Knuth
for(i=k; i
aux=vector[i];
j=i-k;
while(aux=0){
vector[j+k]=vector[j];
j-=k;
}
vector[j+k]=aux;
}
}
}
//**************************************************************************
void quicksort(void){
printf("\n\nQuickSort...");
qs(0,N-1);
}
//**************************************************************************
void qs(int izq, int der){
int F=1, i, k, x, aux;
if(izq
{
i=izq+1;
k=der;
x=vector[izq];
while(F)
{
while(vector[i]<=x)
i++;
while(vector[k]>x)
k--;
if(i
{
aux=vector[i];
vector[i]=vector[k];
vector[k]=aux;
}
else
F=0;
}
aux=vector[izq];
vector[izq]=vector[k];
vector[k]=aux;
qs(izq, k-1);
qs(k+1, der);
}
return;
}
//**************************************************************************
[/spoiler]
Download: orden.zip
Categorías: Codigo - C/C++
Algoritmos, C, Interrupciones, Ordenamiento, Programacion, Timer
Cronometro(con interrupciones)
30 diciembre, 2007
Deja un comentario
Cronometro con interrupciones
[spoiler]
/*Descripcion: Cronometro*/
#include
#include
#include
#define BaseTmr 0x0040
//Posicion del cronometro fijo
#define posx 30
#define posy 10
#define MAX 100 //Cantidad maxima de registros a guardar
//***************************************************************************
typedef struct state{
unsigned int reg;
unsigned int lsb;
unsigned int msb;
unsigned long int cuenta;
unsigned long int tiempo;
}estado;
typedef struct T{
char mili;
char seg;
char min;
}tiempo;
struct control{
char mseg; //Cada vez que mseg pasa a 1, es porque transcurrio 1mseg
char pausa; //pausa=0 ==> el cronometro corre; =1 ==> detenido
char guardar;//Cuando guardar=1, se debe imprimir el tiempo en un costado
char salir; //Cuando salir=1 ==> fin del programa
}flag;
//***************************************************************************
//Interrupcion
void interrupt far (*OldTmr) (void);
void interrupt far (*OldKey) (void);
void interrupt far IsrTmr (void);
void interrupt far IsrKey (void);
//***************************************************************************
//Prototipo de Funciones
estado InitHw(estado original);
void RestoreHw(estado original);
tiempo IncTime(tiempo t);
void Mostrar(tiempo t, char columna, char fila, char color);
void Guardar(tiempo datos[MAX],unsigned int cantidad);
//Variables Globales
unsigned long int tmr=0;
char onetime=0;
//**************************************************************************
void main (void){
//Declaracion de variables locales
estado original;
tiempo t;
tiempo datos[MAX];
char renglon=0;
unsigned int contador=0;
//Inicializacion de las variables
t.mili=0;t.seg=0;t.min=0;
flag.mseg=0;
flag.pausa=0;
flag.guardar=0;
flag.salir=0;
for (contador=0;contador contador=0;
//Incializa el Hardware y devuelve una estructura con el estado
//original del timer
original=InitHw(original);
//Loop Principal
clrscr();
do{
//Transcurre 1 mseg
if (flag.mseg) {
if (!flag.pausa){
t=IncTime(t); //Actualiza la estructura de Tiempo
Mostrar(t,posx,posy,5); //Imprime el tiempo en pantalla
}
flag.mseg=0;
}
//Se presiono guardar
if (flag.guardar){
if (renglon<25){
renglon++;
}else{
clrscr();
renglon=0;
}
Mostrar(t,0,renglon,10);
if (contador
datos[contador]=t;
contador++;
}
flag.guardar=0;
}
}while(!flag.salir);
RestoreHw(original);
Guardar(datos,contador);
}
//***************************************************************************
estado InitHw(estado original){
disable();
//Guardar la configuracion original del Timer
original.reg=inportb(BaseTmr+3);
outportb(BaseTmr+3,0xD8); //Reedback: 1 1 0 1 1 0 0 0
original.lsb=inportb(BaseTmr);
original.msb=inportb(BaseTmr);
original.cuenta=(unsigned long int)original.lsb+256*(unsigned long int)original.msb;
//Configurar el Timer para que interrumpa cada 1 mseg(0x04A9)
outportb(BaseTmr+3,0x34); //Reg: 0 0 1 1 0 1 0 0 (timer0, lsb y msb, modo 2, sin bcd)
outportb(BaseTmr,0xA9); //LSB
outportb(BaseTmr,0x04); //MSB
//Tanto la interrupcion del teclado como la del timer ya se encuentran
//habilitadas desde el PIC.
//Vector de Interrupcion
OldTmr=getvect(0x08);
OldKey=getvect(0x09);
setvect(0x08,IsrTmr);
setvect(0x09,IsrKey);
enable();
return (original);
}
//***************************************************************************
void RestoreHw(estado original){
disable();
//Restaurar el Timer
outportb(BaseTmr+3,original.reg);
outportb(BaseTmr,original.lsb);
outportb(BaseTmr,original.msb);
//Restaurar el vector de interrupciones
setvect(0x08,OldTmr);
setvect(0x09,OldKey);
enable();
}
//***************************************************************************
void interrupt far IsrTmr(void){
if (!flag.mseg) flag.mseg=1; //Por si la interrupcion llega antes de que se limpie el reg
tmr++;
if (tmr==55) {
tmr=0;
OldTmr(); //Interrupcion Original del Timer
}
outportb(0x20,0x20); //EOI
}
//**************************************************************************
void interrupt far IsrKey(void){
char tecla;
if (onetime==0){
if (kbhit()){
tecla=getch();
tecla=toupper(tecla);
if (tecla=='S') flag.salir=1;
if (tecla=='P') flag.pausa=~flag.pausa;
if (tecla=='G') flag.guardar=1;
onetime=1;
}
}else{
onetime=0;
}
OldKey(); //Isr Original
}
//***************************************************************************
void Mostrar(tiempo t, char columna, char fila, char color){
//Declaraciones de variables locales a Mostrar
char far *video=(char far*)0xB8000000l;
char cadena[20];
char CadMili[5];
char CadSeg[5];
char CadMin[5];
char i;
//Convertir la estructura t en un string
itoa(t.mili,CadMili,10);
itoa(t.seg,CadSeg,10);
itoa(t.min,CadMin,10);
strcpy(cadena,"Tiempo: ");
strcat(cadena,CadMin);
strcat(cadena,":");
if (t.seg<10) strcat(cadena,"0");
strcat(cadena,CadSeg);
strcat(cadena,".");
if (t.mili<10) strcat(cadena,"0");
strcat(cadena,CadMili);
//Imprimir la cadena
video=video+(columna*2)+80*(fila*2);
for (i=0;cadena[i];i++){
*video=cadena[i];
video++;
*video=color;
video++;
}
}
//***************************************************************************
tiempo IncTime(tiempo t){
if (t.mili<100){
t.mili++;
}else{
t.mili=0;
if(t.seg<60){
t.seg++;
}else{
t.seg=0;
if (t.min<60){
t.min++;
}else{
t.min=0;
}
}
}
return (t);
}
//***************************************************************************
void Guardar(tiempo datos[MAX],unsigned int cantidad){
FILE *file;
unsigned int i;
char resultado;
clrscr();
file=fopen("reg.txt","w");
if (file==NULL) {
printf("Error al guardar el archivo");
exit();
}
for (i=0;i
printf("%d",i);
fprintf(file,"Tiempo: %d:%d.%d\n",datos[i].min,datos[i].seg,datos[i].mili);
}
fprintf(file,"Fin del Registro");
fclose(file);
getch();
}
[/spoiler]
Download: cron.c
Categorías: Codigo - C/C++
C, Interrupciones, IRQ, Programacion, Timer, Turbo C
Mi código QR:
German's Blog 