Taller : comparacion de Metodos Logaritmicos y Directos
“Comparación de métodos de ordenación Directa y Logarítmica”
La ordenación interna o de arreglo reciben este nombre ya que los elementos o componentes del arreglo se encuentran en la memoria principal de la computadora.
Los métodos de ordenación interna a su vez se clasifican en:
vMétodos directos o (N2).
vMétodos Logarítmicos o (N *log N).
a) Los métodos directos, son los más simples y fáciles de entender, son eficientes cuando se trata de una cantidad de datos pequeña.
b) Los métodos logarítmicos, son más complejos, difíciles de entender y son eficientes en grandes cantidades de datos.
Objetivo de nuestro Programa:
Teniendo en cuenta el tema elegido, nos enfocamos en la comparación de duración de Métodos Directos y Logarítmicos, calcular el tiempo real que tarda en procesar cada uno de estos métodos, ver las animaciones de ordenamiento y comparar el tiempo de ejecución con valores de tipo Real , tipo carácter, enteros.
Además incluimos Animaciones (de funcionamiento de métodos) , una demostración de ordenamiento de Cadenas / caracteres ,y comportamiento de asignación de espacio de memoria para ordenar vectores de grandes cantidades de elementos .
MetodosOrdenamiento.h
#include <stdio.h>
#include<time.h>
#include<conio.h>
int shell_sortMostrarInte(int A[], int cant) ;
void cargarVectorRand(int[],int );
void shell_sort(int[], int cant) ;
void mostrarTiempo(time_t ,time_t );
void copiarVector(int[],int[],int);
void quicksort(int[],int n);
void quicksortP(int* , int* ) ;
void mostrarVectorPos(int[],int);
void mostrarVector(int[],int);
void tituloOrde(char[20],int,char[10]);
void burbuja(int[],int);//ordenacionPorIntercambio
void cargarVector(int[],int);
void insercionDirecta(int[],int);
void seleccionDirecta(int[],int );
int insercionDirectaMostrarInte(int A[],int cant);
int burbujaMostrarInte(int A[],int cant);
void tituloOrde(char orde[20],int p_tam,char tipDat[10]){
printf("\n \n Ordenamiento %s de %d %s \n",orde,p_tam,tipDat );
}
void copiarVector(int VectorVacio[],int Vector[], int p_tam){
int i;
for(i=0;i<p_tam;i++){
VectorVacio[i]=Vector[i];
}
}
void mostrarTiempo(time_t C,time_t F){
printf(" \n Comienzo : %u ",C);
printf(" \n Final : %u ",F );
printf("\n Tiempo transcurrido Despues de Ordenamiento : %.2f Segundos \n", difftime(F,C));
}
void burbuja(int A[],int cant){
int i ,j,aux;
for (i=1;i<cant;i++) {
for (j=0;j<cant-i;j++)
{
if (A[j]>=A[j+1])
{
aux=A[j];
A[j]=A[j+1];
A[j+1]=aux;
}
}
}}
void insercionDirecta(int A[],int cant){ /*Baraja*/
int i, j;
int aux;
for (i = 1; i <cant; i++)
{
aux = A[i];
j = i - 1;
while ((j >= 0) && (A[j] > aux))
{
A[j+1] = A[j];
/*Desplazamiento de los valores mayores que pVector[i]*/
j = j-1;
}
A[j+1] = aux;
}
}
int insercionDirectaMostrarInte(int A[],int cant)
{ /*Baraja*/
int i, j,c=0,b=0;
int aux,aux1,aux2;
for (i = 1; i <cant; i++)
{
aux = A[i];
j = i - 1;
b=0;
printf("\n Elemento a Comparar %d[%d] \n ",aux,i);
while ((j >= 0) && (A[j] > aux))
{ c++;
b=1;
aux1=A[j];
aux2= aux;
A[j+1] = A[j];
printf("\n %d[%d] > %d[%d] SI A[%d] muevo a A[%d] \n",aux1,j,aux2,i,j,j+1);
/*Desplazamiento de los valores mayores que pVector[i]*/
j = j-1;
}
A[j+1] = aux;
sleep(2);
if(b==1){
printf("\n Vector Resultante Despues de Pasada : \n" );
mostrarVectorPos(A,cant);
printf("\n");
}
else{
printf("\n Pasada Sin Intercambios ");
printf("\n");
}
}
return c;
}
void cargarVector(int A[],int cant){
int i ;
for (i=0; i<cant; i++) {
printf("\n Ingrese Numero %d : ",i+1);
scanf("%d",&A[i]);
}
}
void seleccionDirecta(int A[],int cant){ /*Obtención sucesiva de menores*/
/*Efecto: se ordena v ascendentemente*/
int i, j, posMenor;
int valMenor, aux;
for (i = 0; i < cant-1; i++) /*n-1 pasadas*/
{
valMenor = A[i];
posMenor = i;
for (j = i+1; j < cant-1; j++) /*el número de comparaciones decrece*/
{
if (A[j] < valMenor)
{
/*se actualiza el nuevo valor menor y la posición donde se encuentra*/
valMenor = A[j];
posMenor = j;
}
}
if (posMenor != i)
{
/*Si el menor no es pVector[i], se intercambian los valores*/
aux = A[i];
A[i] = A[posMenor];
A[posMenor] = aux;
}
}
}
//definimos las funciones
void cargarVectorRand(int v[],int p_tam){
int i;
srand(time(NULL));
for(i=0;i<p_tam;i++){
v[i]=rand();
}
}
void mostrarVectorPos(int A[],int p_tam){
int i;
printf("\n");
for (i=0;i<p_tam;i++) {
printf(" %d[%d]", A[i],i);
sleep(1);
}}
void mostrarVector(int A[],int p_tam){
int i;
printf("\n");
for (i=0;i<p_tam;i++) {
printf(" %d", A[i],i);
}}
void mostrarVectorP(int* A,int p_tam){
int i;
printf("\n");
for (i=0;i<p_tam;i++) {
printf(" %d", *A);
A++;
}}
void qs(int p_lista[],int limite_izq,int limite_der)
{
int izq,der,temporal,pivote;
izq=limite_izq;
der = limite_der;
pivote = p_lista[(izq+der)/2];
do{
while(p_lista[izq]<pivote && izq<limite_der)izq++;
while(pivote<p_lista[der] && der > limite_izq)der--;
if(izq <=der)
{
temporal= p_lista[izq];
p_lista[izq]=p_lista[der];
p_lista[der]=temporal;
izq++;
der--;
}
}while(izq<=der);
if(limite_izq<der)
{
qs(p_lista,limite_izq,der);
}
if(limite_der>izq)
{
qs(p_lista,izq,limite_der);
}
//printf( " %d ",p_lista[izq]);
}
void quicksort(int lista[],int p_tam)
{
qs(lista,0,p_tam-1);
}
void cargarVectorRandP(int* v,int p_tam){
int i;
srand(time(NULL));
for(i=0;i<p_tam;i++){
*v =rand();
v++;
}
}
void intercambio(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void quicksortP(int* izq, int* der) {
if (der < izq)
return;
int pivote = *izq;
int* ult = der;
int* pri = izq;
while (izq < der) {
while (*izq <= pivote && izq < der+1)
izq++;
while (*der > pivote && der > izq-1)
der--;
if (izq < der)
intercambio(izq, der);
}
intercambio(pri, der);
quicksortP(pri, der-1);
quicksortP(der+1, ult);
}
void shell_sort(int A[], int cant) /*** código en C+ ***/
{
int j, i,temp;
int incrmnt = cant/2;
while (incrmnt > 0) {
for (i = incrmnt; i < cant; i++) {
j = i;
temp = A[i];
while ((j >= incrmnt) && (A[j-incrmnt] > temp)) {
A[j] = A[j - incrmnt];
j = j - incrmnt;
}
A[j] = temp;
}
incrmnt /= 2;
}
}
int shell_sortMostrarInte(int A[], int cant) /*** código en C+ ***/
{
int C=0,s=0;
int j, i,temp,aux1,aux2;
int incrmnt = cant/2;
printf("\n\n SALTO: %d ", incrmnt);
while (incrmnt > 0) {
for (i = incrmnt; i < cant; i++) {
j = i;
temp = A[i];
s=0;
while ((j >= incrmnt) && (A[j-incrmnt] > temp)) {
C++;
aux1=A[j-incrmnt];//para imprimir las animaciones
aux2=temp;//para imprimir las animaciones
printf("\n %d[%d] > %d[%d] : SI Intercambio A[%d] con A[%d]\n",aux1,(j-incrmnt),aux2,i,(j-incrmnt),i);
A[j] = A[j - incrmnt];
j = j - incrmnt;
s=1;
sleep(2);
mostrarVector(A,cant);
printf("\n\n");
}
A[j] = temp;
}
sleep(2);
incrmnt /= 2;
printf("\n\n SALTO: %d ", incrmnt);
}
return C;
}
int burbujaMostrarInte(int A[],int cant){
int i ,j,aux,c,aux1,aux2;
c=0;
for (i=1;i<cant;i++) {
for (j=0;j<cant-i;j++)
{
if (A[j]>=A[j+1])
{ c++;
aux1=A[j];
aux2=A[j+1];
printf("\n %d[%d] > %d[%d] : SI Intercambio A[%d] con A[%d] \n",aux1 ,j,aux2,j+1,j,j+1);
aux=A[j];
A[j]=A[j+1];
A[j+1]=aux;
sleep(2);
mostrarVector(A,cant);
printf("\n\n");
}
}
}
return c;
}
#include<time.h>
#include<conio.h>
int shell_sortMostrarInte(int A[], int cant) ;
void cargarVectorRand(int[],int );
void shell_sort(int[], int cant) ;
void mostrarTiempo(time_t ,time_t );
void copiarVector(int[],int[],int);
void quicksort(int[],int n);
void quicksortP(int* , int* ) ;
void mostrarVectorPos(int[],int);
void mostrarVector(int[],int);
void tituloOrde(char[20],int,char[10]);
void burbuja(int[],int);//ordenacionPorIntercambio
void cargarVector(int[],int);
void insercionDirecta(int[],int);
void seleccionDirecta(int[],int );
int insercionDirectaMostrarInte(int A[],int cant);
int burbujaMostrarInte(int A[],int cant);
void tituloOrde(char orde[20],int p_tam,char tipDat[10]){
printf("\n \n Ordenamiento %s de %d %s \n",orde,p_tam,tipDat );
}
void copiarVector(int VectorVacio[],int Vector[], int p_tam){
int i;
for(i=0;i<p_tam;i++){
VectorVacio[i]=Vector[i];
}
}
void mostrarTiempo(time_t C,time_t F){
printf(" \n Comienzo : %u ",C);
printf(" \n Final : %u ",F );
printf("\n Tiempo transcurrido Despues de Ordenamiento : %.2f Segundos \n", difftime(F,C));
}
void burbuja(int A[],int cant){
int i ,j,aux;
for (i=1;i<cant;i++) {
for (j=0;j<cant-i;j++)
{
if (A[j]>=A[j+1])
{
aux=A[j];
A[j]=A[j+1];
A[j+1]=aux;
}
}
}}
void insercionDirecta(int A[],int cant){ /*Baraja*/
int i, j;
int aux;
for (i = 1; i <cant; i++)
{
aux = A[i];
j = i - 1;
while ((j >= 0) && (A[j] > aux))
{
A[j+1] = A[j];
/*Desplazamiento de los valores mayores que pVector[i]*/
j = j-1;
}
A[j+1] = aux;
}
}
int insercionDirectaMostrarInte(int A[],int cant)
{ /*Baraja*/
int i, j,c=0,b=0;
int aux,aux1,aux2;
for (i = 1; i <cant; i++)
{
aux = A[i];
j = i - 1;
b=0;
printf("\n Elemento a Comparar %d[%d] \n ",aux,i);
while ((j >= 0) && (A[j] > aux))
{ c++;
b=1;
aux1=A[j];
aux2= aux;
A[j+1] = A[j];
printf("\n %d[%d] > %d[%d] SI A[%d] muevo a A[%d] \n",aux1,j,aux2,i,j,j+1);
/*Desplazamiento de los valores mayores que pVector[i]*/
j = j-1;
}
A[j+1] = aux;
sleep(2);
if(b==1){
printf("\n Vector Resultante Despues de Pasada : \n" );
mostrarVectorPos(A,cant);
printf("\n");
}
else{
printf("\n Pasada Sin Intercambios ");
printf("\n");
}
}
return c;
}
void cargarVector(int A[],int cant){
int i ;
for (i=0; i<cant; i++) {
printf("\n Ingrese Numero %d : ",i+1);
scanf("%d",&A[i]);
}
}
void seleccionDirecta(int A[],int cant){ /*Obtención sucesiva de menores*/
/*Efecto: se ordena v ascendentemente*/
int i, j, posMenor;
int valMenor, aux;
for (i = 0; i < cant-1; i++) /*n-1 pasadas*/
{
valMenor = A[i];
posMenor = i;
for (j = i+1; j < cant-1; j++) /*el número de comparaciones decrece*/
{
if (A[j] < valMenor)
{
/*se actualiza el nuevo valor menor y la posición donde se encuentra*/
valMenor = A[j];
posMenor = j;
}
}
if (posMenor != i)
{
/*Si el menor no es pVector[i], se intercambian los valores*/
aux = A[i];
A[i] = A[posMenor];
A[posMenor] = aux;
}
}
}
//definimos las funciones
void cargarVectorRand(int v[],int p_tam){
int i;
srand(time(NULL));
for(i=0;i<p_tam;i++){
v[i]=rand();
}
}
void mostrarVectorPos(int A[],int p_tam){
int i;
printf("\n");
for (i=0;i<p_tam;i++) {
printf(" %d[%d]", A[i],i);
sleep(1);
}}
void mostrarVector(int A[],int p_tam){
int i;
printf("\n");
for (i=0;i<p_tam;i++) {
printf(" %d", A[i],i);
}}
void mostrarVectorP(int* A,int p_tam){
int i;
printf("\n");
for (i=0;i<p_tam;i++) {
printf(" %d", *A);
A++;
}}
void qs(int p_lista[],int limite_izq,int limite_der)
{
int izq,der,temporal,pivote;
izq=limite_izq;
der = limite_der;
pivote = p_lista[(izq+der)/2];
do{
while(p_lista[izq]<pivote && izq<limite_der)izq++;
while(pivote<p_lista[der] && der > limite_izq)der--;
if(izq <=der)
{
temporal= p_lista[izq];
p_lista[izq]=p_lista[der];
p_lista[der]=temporal;
izq++;
der--;
}
}while(izq<=der);
if(limite_izq<der)
{
qs(p_lista,limite_izq,der);
}
if(limite_der>izq)
{
qs(p_lista,izq,limite_der);
}
//printf( " %d ",p_lista[izq]);
}
void quicksort(int lista[],int p_tam)
{
qs(lista,0,p_tam-1);
}
void cargarVectorRandP(int* v,int p_tam){
int i;
srand(time(NULL));
for(i=0;i<p_tam;i++){
*v =rand();
v++;
}
}
void intercambio(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void quicksortP(int* izq, int* der) {
if (der < izq)
return;
int pivote = *izq;
int* ult = der;
int* pri = izq;
while (izq < der) {
while (*izq <= pivote && izq < der+1)
izq++;
while (*der > pivote && der > izq-1)
der--;
if (izq < der)
intercambio(izq, der);
}
intercambio(pri, der);
quicksortP(pri, der-1);
quicksortP(der+1, ult);
}
void shell_sort(int A[], int cant) /*** código en C+ ***/
{
int j, i,temp;
int incrmnt = cant/2;
while (incrmnt > 0) {
for (i = incrmnt; i < cant; i++) {
j = i;
temp = A[i];
while ((j >= incrmnt) && (A[j-incrmnt] > temp)) {
A[j] = A[j - incrmnt];
j = j - incrmnt;
}
A[j] = temp;
}
incrmnt /= 2;
}
}
int shell_sortMostrarInte(int A[], int cant) /*** código en C+ ***/
{
int C=0,s=0;
int j, i,temp,aux1,aux2;
int incrmnt = cant/2;
printf("\n\n SALTO: %d ", incrmnt);
while (incrmnt > 0) {
for (i = incrmnt; i < cant; i++) {
j = i;
temp = A[i];
s=0;
while ((j >= incrmnt) && (A[j-incrmnt] > temp)) {
C++;
aux1=A[j-incrmnt];//para imprimir las animaciones
aux2=temp;//para imprimir las animaciones
printf("\n %d[%d] > %d[%d] : SI Intercambio A[%d] con A[%d]\n",aux1,(j-incrmnt),aux2,i,(j-incrmnt),i);
A[j] = A[j - incrmnt];
j = j - incrmnt;
s=1;
sleep(2);
mostrarVector(A,cant);
printf("\n\n");
}
A[j] = temp;
}
sleep(2);
incrmnt /= 2;
printf("\n\n SALTO: %d ", incrmnt);
}
return C;
}
int burbujaMostrarInte(int A[],int cant){
int i ,j,aux,c,aux1,aux2;
c=0;
for (i=1;i<cant;i++) {
for (j=0;j<cant-i;j++)
{
if (A[j]>=A[j+1])
{ c++;
aux1=A[j];
aux2=A[j+1];
printf("\n %d[%d] > %d[%d] : SI Intercambio A[%d] con A[%d] \n",aux1 ,j,aux2,j+1,j,j+1);
aux=A[j];
A[j]=A[j+1];
A[j+1]=aux;
sleep(2);
mostrarVector(A,cant);
printf("\n\n");
}
}
}
return c;
}
Librerias: MetodosOrdenamientoFloatChar.h
#include <stdio.h>
#include<time.h>
#include<string.h>
typedef char nombre[25];
void cargarVectorRandF(float[],int );
void quicksortF(float[] ,int );
void shell_sortF(float[], int ) ;
void cargarVectorCharRand(char[],int);
void quicksortF(float[] ,int );
void mostrarVectorF(float[],int);
void burbujaChar(char[],int);
void burbujaF(float[],int);//ordenacionPorIntercambio
void cargarVectorF(float[],int);
void insercionDirectaF(float[],int);
void seleccionDirectaF(float[],int );
void insercionDirectaChar(char[],int);
void cargarVectorString(nombre[],int);
void burbujaString(nombre[],int);
void quicksortChar(char[],int );
void seleccionDirectaChar(char[],int);
void qsChar(char[],int ,int );
void mostrarVectorChar(char[], int cant);
void mostrarVectorString(nombre A[],int cant);
void shell_sortChar(char[], int );
void copiarVectorChar(char[],char[],int cant);
void cargarVectorString(nombre A[],int cant){
int i;
nombre nom;
for(i=0;i<cant;i++){
fflush(stdin);
printf("\n Ingrese Frase 25 Caracteres Max : ");
gets(nom);
strcpy(A[i],nom);
}
}
void cargarVectorCharRand(char A[],int cant){
int i;
srand(time(NULL));
for(i = 0; i < cant; i++){
A[i] = ('a' + rand() % (('z' - 'a') + 1));
}
}
void copiarVectorChar(char VectorVacio[],char Vector[],int cant){
int i;
for(i=0;i<cant;i++){
VectorVacio[i]=Vector[i];
}
}
void mostrarVectorChar(char A[], int cant){
int i ;
printf("\n");
for (i=0;i<cant;i++){
printf( " %c ",A[i]);
}
}
void mostrarVectorString(nombre A[],int cant){
int i;
nombre nom;
for(i=0;i<cant;i++){
printf("\n %s ",A[i]);
}
}
void burbujaF(float A[],int cant){
int i ,j;
float aux;
for (i=1;i<cant;i++) {
for (j=0;j<cant-i;j++)
{
if (A[j]>=A[j+1])
{
aux=A[j];
A[j]=A[j+1];
A[j+1]=aux;
}
}
}}
void burbujaChar(char A[],int cant){
int i ,j;
char aux;
for (i=1;i<cant;i++) {
for (j=0;j<cant-i;j++)
{
if (A[j]>=A[j+1])
{
aux=A[j];
A[j]=A[j+1];
A[j+1]=aux;
}
}
}
}
void burbujaString(nombre A[],int cant){
int i ,j;
nombre aux;
for (i=1;i<cant;i++) {
for (j=0;j<cant-i;j++)
{
if (strcmp(A[j],A[j+1])>=0)
{
strcpy(aux,A[j]);
strcpy(A[j],A[j+1]);
strcpy(A[j+1],aux);
}
}
}
}
void insercionDirectaF(float A[],int cant){ /*Baraja*/
int i, j;
float aux;
for (i = 1; i <cant; i++)
{
aux = A[i];
j = i - 1;
while ((j >= 0) && (A[j] > aux))
{
A[j+1] = A[j];
/*Desplazamiento de los valores mayores que pVector[i]*/
j = j-1;
}
A[j+1] = aux;
}
}
void insercionDirectaChar(char A[],int cant){
int i, j;
char aux;
for (i = 1; i <cant; i++)
{
aux = A[i];
j = i - 1;
while ((j >= 0) && (A[j] > aux))
{
A[j+1] = A[j];
/*Desplazamiento de los valores mayores que pVector[i]*/
j = j-1;
}
A[j+1] = aux;
}
}
void cargarVectorF(float A[],int cant){
int i ;
for (i=0; i<cant; i++) {
printf("\n Ingrese Numero %d : ",i+1);
scanf("%f",&A[i]);
}
}
void seleccionDirectaF(float A[],int cant){ /*Obtención sucesiva de menores*/
/*Efecto: se ordena v ascendentemente*/
int i, j, posMenor;
float valMenor, aux;
for (i = 0; i < cant-1; i++) /*n-1 pasadas*/
{
valMenor = A[i];
posMenor = i;
for (j = i+1; j < cant-1; j++) /*el número de comparaciones decrece*/
{
if (A[j] < valMenor)
{
/*se actualiza el nuevo valor menor y la posición donde se encuentra*/
valMenor = A[j];
posMenor = j;
}
}
if (posMenor != i)
{
/*Si el menor no es pVector[i], se intercambian los valores*/
aux = A[i];
A[i] = A[posMenor];
A[posMenor] = aux;
}
}
}
void seleccionDirectaChar(char A[],int cant){ /*Obtención sucesiva de menores*/
/*Efecto: se ordena v ascendentemente*/
int i, j, posMenor;
char valMenor, aux;
for (i = 0; i < cant-1; i++) /*n-1 pasadas*/
{
valMenor = A[i];
posMenor = i;
for (j = i+1; j < cant-1; j++) /*el número de comparaciones decrece*/
{
if (A[j] < valMenor)
{
/*se actualiza el nuevo valor menor y la posición donde se encuentra*/
valMenor = A[j];
posMenor = j;
}
}
if (posMenor != i)
{
/*Si el menor no es pVector[i], se intercambian los valores*/
aux = A[i];
A[i] = A[posMenor];
A[posMenor] = aux;
}
}
}
//definimos las funciones
void cargarVectorRandF(float v[],int p_tam){
int i;
srand(time(NULL));
for(i=0;i<p_tam;i++){
if((i%2)==0){
v[i]=(rand())/3.7;
}else{
v[i]=rand();
}
}
}
void mostrarVectorF(float A[],int p_tam){
int i;
printf("\n");
for (i=0;i<p_tam;i++) {
printf(" %.4f", A[i]);
}
}
void qsF(float p_lista[],int limite_izq,int limite_der)
{
int izq,der;
float temporal,pivote;
izq=limite_izq;
der = limite_der;
pivote = p_lista[(izq+der)/2];
do{
while(p_lista[izq]<pivote && izq<limite_der)izq++;
while(pivote<p_lista[der] && der > limite_izq)der--;
if(izq <=der)
{
temporal= p_lista[izq];
p_lista[izq]=p_lista[der];
p_lista[der]=temporal;
izq++;
der--;
}
}while(izq<=der);
if(limite_izq<der)
{
qsF(p_lista,limite_izq,der);
}
if(limite_der>izq)
{
qsF(p_lista,izq,limite_der);
}
//printf( " %d ",p_lista[izq]);
}
void quicksortF(float lista[],int p_tam)
{
qsF(lista,0,p_tam-1);
}
void shell_sortF(float A[], int cant) /*** código en C++ ***/
{
int j, i;
float temp;
int incrmnt = cant/2;
while (incrmnt > 0) {
for (i = incrmnt; i < cant; i++) {
j = i;
temp = A[i];
while ((j >= incrmnt) && (A[j-incrmnt] > temp)) {
A[j] = A[j - incrmnt];
j = j - incrmnt;
}
A[j] = temp;
}
incrmnt /= 2;
}
}
void shell_sortChar(char A[], int cant) /*** código en C++ ***/
{
int j, i;
char temp;
int incrmnt = cant/2;
while (incrmnt > 0) {
for (i = incrmnt; i < cant; i++) {
j = i;
temp = A[i];
while ((j >= incrmnt) && (A[j-incrmnt] > temp)) {
A[j] = A[j - incrmnt];
j = j - incrmnt;
}
A[j] = temp;
}
incrmnt /= 2;
}
}
void qsChar(char p_lista[],int limite_izq,int limite_der)
{
int izq,der;
char temporal,pivote;
izq=limite_izq;
der = limite_der;
pivote = p_lista[(izq+der)/2];
do{
while(p_lista[izq]<pivote && izq<limite_der)izq++;
while(pivote<p_lista[der] && der > limite_izq)der--;
if(izq <=der)
{
temporal= p_lista[izq];
p_lista[izq]=p_lista[der];
p_lista[der]=temporal;
izq++;
der--;
}
}while(izq<=der);
if(limite_izq<der)
{
qsChar(p_lista,limite_izq,der);
}
if(limite_der>izq)
{
qsChar(p_lista,izq,limite_der);
}
//printf( " %d ",p_lista[izq]);
}
void quicksortChar(char lista[],int p_tam)
{
qsChar(lista,0,p_tam-1);
}
#include<time.h>
#include<string.h>
typedef char nombre[25];
void cargarVectorRandF(float[],int );
void quicksortF(float[] ,int );
void shell_sortF(float[], int ) ;
void cargarVectorCharRand(char[],int);
void quicksortF(float[] ,int );
void mostrarVectorF(float[],int);
void burbujaChar(char[],int);
void burbujaF(float[],int);//ordenacionPorIntercambio
void cargarVectorF(float[],int);
void insercionDirectaF(float[],int);
void seleccionDirectaF(float[],int );
void insercionDirectaChar(char[],int);
void cargarVectorString(nombre[],int);
void burbujaString(nombre[],int);
void quicksortChar(char[],int );
void seleccionDirectaChar(char[],int);
void qsChar(char[],int ,int );
void mostrarVectorChar(char[], int cant);
void mostrarVectorString(nombre A[],int cant);
void shell_sortChar(char[], int );
void copiarVectorChar(char[],char[],int cant);
void cargarVectorString(nombre A[],int cant){
int i;
nombre nom;
for(i=0;i<cant;i++){
fflush(stdin);
printf("\n Ingrese Frase 25 Caracteres Max : ");
gets(nom);
strcpy(A[i],nom);
}
}
void cargarVectorCharRand(char A[],int cant){
int i;
srand(time(NULL));
for(i = 0; i < cant; i++){
A[i] = ('a' + rand() % (('z' - 'a') + 1));
}
}
void copiarVectorChar(char VectorVacio[],char Vector[],int cant){
int i;
for(i=0;i<cant;i++){
VectorVacio[i]=Vector[i];
}
}
void mostrarVectorChar(char A[], int cant){
int i ;
printf("\n");
for (i=0;i<cant;i++){
printf( " %c ",A[i]);
}
}
void mostrarVectorString(nombre A[],int cant){
int i;
nombre nom;
for(i=0;i<cant;i++){
printf("\n %s ",A[i]);
}
}
void burbujaF(float A[],int cant){
int i ,j;
float aux;
for (i=1;i<cant;i++) {
for (j=0;j<cant-i;j++)
{
if (A[j]>=A[j+1])
{
aux=A[j];
A[j]=A[j+1];
A[j+1]=aux;
}
}
}}
void burbujaChar(char A[],int cant){
int i ,j;
char aux;
for (i=1;i<cant;i++) {
for (j=0;j<cant-i;j++)
{
if (A[j]>=A[j+1])
{
aux=A[j];
A[j]=A[j+1];
A[j+1]=aux;
}
}
}
}
void burbujaString(nombre A[],int cant){
int i ,j;
nombre aux;
for (i=1;i<cant;i++) {
for (j=0;j<cant-i;j++)
{
if (strcmp(A[j],A[j+1])>=0)
{
strcpy(aux,A[j]);
strcpy(A[j],A[j+1]);
strcpy(A[j+1],aux);
}
}
}
}
void insercionDirectaF(float A[],int cant){ /*Baraja*/
int i, j;
float aux;
for (i = 1; i <cant; i++)
{
aux = A[i];
j = i - 1;
while ((j >= 0) && (A[j] > aux))
{
A[j+1] = A[j];
/*Desplazamiento de los valores mayores que pVector[i]*/
j = j-1;
}
A[j+1] = aux;
}
}
void insercionDirectaChar(char A[],int cant){
int i, j;
char aux;
for (i = 1; i <cant; i++)
{
aux = A[i];
j = i - 1;
while ((j >= 0) && (A[j] > aux))
{
A[j+1] = A[j];
/*Desplazamiento de los valores mayores que pVector[i]*/
j = j-1;
}
A[j+1] = aux;
}
}
void cargarVectorF(float A[],int cant){
int i ;
for (i=0; i<cant; i++) {
printf("\n Ingrese Numero %d : ",i+1);
scanf("%f",&A[i]);
}
}
void seleccionDirectaF(float A[],int cant){ /*Obtención sucesiva de menores*/
/*Efecto: se ordena v ascendentemente*/
int i, j, posMenor;
float valMenor, aux;
for (i = 0; i < cant-1; i++) /*n-1 pasadas*/
{
valMenor = A[i];
posMenor = i;
for (j = i+1; j < cant-1; j++) /*el número de comparaciones decrece*/
{
if (A[j] < valMenor)
{
/*se actualiza el nuevo valor menor y la posición donde se encuentra*/
valMenor = A[j];
posMenor = j;
}
}
if (posMenor != i)
{
/*Si el menor no es pVector[i], se intercambian los valores*/
aux = A[i];
A[i] = A[posMenor];
A[posMenor] = aux;
}
}
}
void seleccionDirectaChar(char A[],int cant){ /*Obtención sucesiva de menores*/
/*Efecto: se ordena v ascendentemente*/
int i, j, posMenor;
char valMenor, aux;
for (i = 0; i < cant-1; i++) /*n-1 pasadas*/
{
valMenor = A[i];
posMenor = i;
for (j = i+1; j < cant-1; j++) /*el número de comparaciones decrece*/
{
if (A[j] < valMenor)
{
/*se actualiza el nuevo valor menor y la posición donde se encuentra*/
valMenor = A[j];
posMenor = j;
}
}
if (posMenor != i)
{
/*Si el menor no es pVector[i], se intercambian los valores*/
aux = A[i];
A[i] = A[posMenor];
A[posMenor] = aux;
}
}
}
//definimos las funciones
void cargarVectorRandF(float v[],int p_tam){
int i;
srand(time(NULL));
for(i=0;i<p_tam;i++){
if((i%2)==0){
v[i]=(rand())/3.7;
}else{
v[i]=rand();
}
}
}
void mostrarVectorF(float A[],int p_tam){
int i;
printf("\n");
for (i=0;i<p_tam;i++) {
printf(" %.4f", A[i]);
}
}
void qsF(float p_lista[],int limite_izq,int limite_der)
{
int izq,der;
float temporal,pivote;
izq=limite_izq;
der = limite_der;
pivote = p_lista[(izq+der)/2];
do{
while(p_lista[izq]<pivote && izq<limite_der)izq++;
while(pivote<p_lista[der] && der > limite_izq)der--;
if(izq <=der)
{
temporal= p_lista[izq];
p_lista[izq]=p_lista[der];
p_lista[der]=temporal;
izq++;
der--;
}
}while(izq<=der);
if(limite_izq<der)
{
qsF(p_lista,limite_izq,der);
}
if(limite_der>izq)
{
qsF(p_lista,izq,limite_der);
}
//printf( " %d ",p_lista[izq]);
}
void quicksortF(float lista[],int p_tam)
{
qsF(lista,0,p_tam-1);
}
void shell_sortF(float A[], int cant) /*** código en C++ ***/
{
int j, i;
float temp;
int incrmnt = cant/2;
while (incrmnt > 0) {
for (i = incrmnt; i < cant; i++) {
j = i;
temp = A[i];
while ((j >= incrmnt) && (A[j-incrmnt] > temp)) {
A[j] = A[j - incrmnt];
j = j - incrmnt;
}
A[j] = temp;
}
incrmnt /= 2;
}
}
void shell_sortChar(char A[], int cant) /*** código en C++ ***/
{
int j, i;
char temp;
int incrmnt = cant/2;
while (incrmnt > 0) {
for (i = incrmnt; i < cant; i++) {
j = i;
temp = A[i];
while ((j >= incrmnt) && (A[j-incrmnt] > temp)) {
A[j] = A[j - incrmnt];
j = j - incrmnt;
}
A[j] = temp;
}
incrmnt /= 2;
}
}
void qsChar(char p_lista[],int limite_izq,int limite_der)
{
int izq,der;
char temporal,pivote;
izq=limite_izq;
der = limite_der;
pivote = p_lista[(izq+der)/2];
do{
while(p_lista[izq]<pivote && izq<limite_der)izq++;
while(pivote<p_lista[der] && der > limite_izq)der--;
if(izq <=der)
{
temporal= p_lista[izq];
p_lista[izq]=p_lista[der];
p_lista[der]=temporal;
izq++;
der--;
}
}while(izq<=der);
if(limite_izq<der)
{
qsChar(p_lista,limite_izq,der);
}
if(limite_der>izq)
{
qsChar(p_lista,izq,limite_der);
}
//printf( " %d ",p_lista[izq]);
}
void quicksortChar(char lista[],int p_tam)
{
qsChar(lista,0,p_tam-1);
}
Programa Pricipal:
#include<stdio.h>
#include<conio.h>
#include <windows.h>
#include"MetodosOrdenamientoFloatChar.h"
#include"MetodosOrdenamiento.h"
#include<time.h>
#define tam2 15
#define max1 99000
void opcionesAnimacion(int C[],int p_tam);
typedef int vectorInt[max1];
typedef float vectorFloat[tam2];
void titulo();
void gotoxy(int x,int y);
void menuOpciones();
void menuop3();
void menuOp1();
void menuOp4();
void menuOp2();
void reservaMemoriaquick(long);
void opBurbuja(int[],float[],char[],int,int);
void opInsercion(int A[],float [],char[],int,int );
void opShell(int[],float[],char[],int,int);
void opQuick(int[],float[],char[],int,int);
void opSeleccion(int[],float[],char[],int,int );
void mostrarVectoresPrincipio(int[],float[], char[], int);
void mostrarVectoresSalida(int[],float[], char[], int);
void gotoxy(int x,int y){
HANDLE hcon;
hcon = GetStdHandle(STD_OUTPUT_HANDLE);
COORD dwPos;
dwPos.X = x;
dwPos.Y= y;
SetConsoleCursorPosition(hcon,dwPos);
}
int main()
{int op;
do{
titulo();
printf(" \n Mgtr. Vallejos, Oscar Adolfo \n\n Integrantes del Grupo : \n Ledezma Lucia del Valle \n Ortiz Julio Sebastian \n Mayol Rosa Mabel \n Barrios Cintia Elizabeth ");
gotoxy(9,9);
printf("\n SALIR 0\n CONTINUAR 1 \n ");
scanf("%d",&op);
if(op==1){
menuOpciones();
}
}while(op!=0);
return 0;
}
void titulo(){
int x,y,i,z,a;
system("cls");
gotoxy(35,10);
printf("******METODOS DE ORDENAMIENTO******");
for(i=1; i<90; i++)
{
gotoxy(i,13);
printf("%c",177);
for(x=50;x<70;x++){
for(y=1;y<70;y++){
gotoxy(y,24);
}
}
}
gotoxy(20,20);
}
void menuOp1(){
time_t comienzo, final;
vectorInt A,B,C,D,E;
titulo();
//cargarVector(A);
cargarVectorRand(A,max1);
copiarVector(B,A,max1);
copiarVector(D,A,max1);
copiarVector(E,A,max1);
copiarVector(C,A,max1);
printf("\n PRIMEROS 10 ELEMENTOS DEL VECTOR DE %d NUMEROS ENTEROS \n\n",max1);
mostrarVector(A,10);
printf("\n");
printf("\n\n COMPARACION DE TIEMPO DE DURACION DE METODOS DE ORDENAMIENTO DIRECTOS Y LOGARITMICOS \n\n");
//mostrar(A);
tituloOrde("Burbuja ",max1," Enteros ");
comienzo=time(NULL);
burbuja(A,max1);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Seleccion Directa ",max1," Enteros ");
comienzo=time(NULL);
seleccionDirecta(B,max1);
final=time(NULL);
mostrarTiempo(comienzo,final);
//mostrar(A);
tituloOrde("Insercion Directa",max1," Enteros ");
comienzo=time(NULL);
insercionDirecta(C,max1);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde(" Shell Sort",max1,"Enteros ");
comienzo=time(NULL);
shell_sort(D,max1);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde(" QuicK Sort",max1,"Enteros ");
comienzo=time(NULL);
quicksort(C,max1);
final=time(NULL);
mostrarTiempo(comienzo,final);
printf("\n\n PRIMEROS 10 ELEMENTOS DEL VECTOR ORDENADO : \n\n " );
mostrarVector(A,10);
printf("\n\n");
system("pause");
system("cls");
}
void menuOpciones(){
int op;
long cantM;
do{
titulo();
printf("\n 1- Comparacion de duracion Metodos Directos y logaritmicos en Enteros \n 2-Comparacion de tiempo de duracion de Ordenamiento en Char ,Entero y Real \n 3- Ver Ordenamiento Tipo Caracter y Cadena \n 4-Ver Animaciones de Ordenamiento \n 5-Reservar Memoria para Ordenar Enteros con Quick Sort\n 6- Volver \n Opcion :... " );
scanf("%d",&op);
switch(op){
case 1 :
menuOp1();
break;
case 2:
menuOp2();
break;
case 3://solo es una musestra de como ordena caracteres y frases
menuop3();
break;
case 4 :
menuOp4();
break;
case 5:
titulo();
printf("\n Ingrese Cantidad de Memoria A Reservar : .. ");
scanf("%o",&cantM);
reservaMemoriaquick(cantM);
break;
}
}while(op!=6);
system("pause");
system("cls");
}
void menuOp4(){
int c,i,c2,c3,op,tam;
vectorInt V,B,C;
cargarVectorRand(V,9);
do{
titulo();
printf( "\n1--INGRESAR VALOR DE VECTOR POR TECLADO \n2--FUNCION RANDOM \n3--VOLVER \n ---- : ");
scanf("%d",&op);
if(op==1){
cargarVector(C,9);
opcionesAnimacion(C,9);
}
else{
if(op==2){
cargarVectorRand(C,9);
opcionesAnimacion( C,9);
}
}
}while(op!=3);
}
void opcionesAnimacion(int C[],int p_tam){
int op,c2,c;
titulo();
printf("\n VECTOR DESORDENADO \n ");
mostrarVectorPos(C,p_tam);
printf("\n\n1--METODO BURBUJA \n2--METODO SHELL \n3--INSERCCION DIRECTA \n---- : ");
scanf("%d",&op);
switch(op){
case 1:
titulo();
printf("\n VECTOR DESORDENADO \n ");
mostrarVectorPos(C,p_tam);
printf("\n");
printf("\n\n INTERCAMBIOS METODO BURBUJA :\n");
c2=burbujaMostrarInte(C,p_tam);
printf("\n\n Cantidad de Intercambios Metodo Burbuja : %d \n",c2);
printf("\n\n VECTOR ORDENADO \n\n");
mostrarVectorPos(C,p_tam);
printf("\n\n");
break;
case 2:
titulo();
printf("\n VECTOR DESORDENADO \n ");
mostrarVectorPos(C,p_tam);
printf("\n");
c=shell_sortMostrarInte(C,p_tam);
printf("\n\nCantidad de Intercambios Metodo Shell: %d \n\n",c);
printf("\n VECTOR ORDENADO \n ");
mostrarVectorPos(C,p_tam);
printf("\n \n");
break;
case 3:
titulo();
printf("\n VECTOR DESORDENADO \n ");
mostrarVectorPos(C,p_tam);
printf("\n");
c= insercionDirectaMostrarInte(C,p_tam);
printf("\n\nCantidad de Intercambios Metodo Baraja : %d \n\n",c);
printf("\n VECTOR ORDENADO \n ");
mostrarVectorPos(C,p_tam);
printf("\n\n ");
break;
}
system("pause");
}
void menuop3(){
int op;
time_t comienzo,final;
titulo();
nombre sA[9],VS[9];
char B[9];
do{
printf("\n\n DEMOSTRACION DE ORDENAMIENTO DE CARACTERES Y FRASES :\n\n");
printf("\n1-- Ver Ordenamiento de Caracteres \n2-- Ver Ordenamiento de cadenas \n3-- Volver \n.....: " );
scanf("%d",&op);
switch (op){
case 1:
titulo();
printf("\n\n VECTOR CARACTER (Cargados Aleatoriamente):\n\n");
cargarVectorCharRand(B,9);
printf("\n\n 10 PRIMEROS ELEMENTOS DE VECTOR CARACTER \n");
mostrarVectorChar(B,9);
burbujaChar(B,9);
printf("\n\n VECTOR CARACTER ORDENADO USANDO METODO BURBUJA \n");
mostrarVectorChar(B,9);
sleep(4);
printf("\n\n");
system("pause");
break;
case 2 :
titulo();
printf("\n\n VECTOR DE CADENAS : \n");
cargarVectorString(sA,9);
system("pause");
titulo();
printf("\n\n 10 PRIMEROS ELMENTOS VECTOR STRING DESORDENADO \n");
mostrarVectorString(sA,9);
burbujaString(sA,9);
printf("\n\n VECTOR STRING ORDENADO CON METODO BURBUJA \n");
mostrarVectorString(sA,9);
sleep(2);
printf("\n\n");
system("pause");
break;
}
titulo();
}while(op!=3);
}
void menuOp2(){
vectorInt A;
float B[max1];
char C[max1];
int op;
do{
titulo();
printf("\n1-- Burbuja \n2-- Inserccion Directa \n3-- Seleccion Directa \n4-- Metodo Shell Sort \n5-- Metodo Quick Sort \n6-- Volver \n.....: ");
scanf("%d",&op);
switch (op){
case 1:
cargarVectorRand(A,max1);
cargarVectorRandF(B,max1);
cargarVectorCharRand(C,max1);
opBurbuja(A,B,C,max1,10);
break;
case 2:
cargarVectorRand(A,max1);
cargarVectorRandF(B,max1);
cargarVectorCharRand(C,max1);
opInsercion(A,B,C,max1,10);
break;
case 3:
cargarVectorRand(A,max1);
cargarVectorRandF(B,max1);
cargarVectorCharRand(C,max1);
opSeleccion(A,B,C,max1,10);
break;
case 4:
cargarVectorRand(A,max1);
cargarVectorRandF(B,max1);
cargarVectorCharRand(C,max1);
opShell(A,B,C,max1,10);
break;
case 5:
cargarVectorRand(A,max1);
cargarVectorRandF(B,max1);
cargarVectorCharRand(C,max1);
opQuick(A,B,C,max1,10);
break;
}
}while(op!=6);
sleep(3);
}
void opBurbuja(int A[],float B[],char C[],int p_tam,int p_tamMos){
time_t comienzo,final;
titulo();
printf("\n COMPARACION DEL METODO BURBUJA EN REALES , ENTEROS Y CARACTER :\n\n");
mostrarVectoresPrincipio(A,B,C,p_tamMos);
tituloOrde("Burbuja ",p_tam,"Enteros ");
comienzo=time(NULL);
burbuja(A,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Burbuja ",p_tam," Reales");
comienzo=time(NULL);
burbujaF(B,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Burbuja ",p_tam," Caracteres");
comienzo=time(NULL);
burbujaChar(C,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
mostrarVectoresSalida(A,B,C,p_tamMos);
printf("\n");
system("pause");
}
void opInsercion(int A[],float B[],char C[],int p_tam,int p_tamMos){
time_t comienzo,final;
titulo();
printf("\n COMPARACION DEL METODO INSERCION DIRECTA EN REALES , ENTEROS Y CARACTER :\n\n");
mostrarVectoresPrincipio(A,B,C,p_tamMos);
tituloOrde("Insercion Directa ",p_tam,"Enteros ");
comienzo=time(NULL);
insercionDirecta(A,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Insercion Directa ",p_tam," Reales");
comienzo=time(NULL);
insercionDirectaF(B,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Insercion Directa",p_tam," Caracteres");
comienzo=time(NULL);
insercionDirectaChar(C,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
mostrarVectoresSalida(A,B,C,p_tamMos);
printf("\n");
system("pause");
}
void opShell(int A[],float B[],char C[],int p_tam,int p_tamMos){
time_t comienzo,final;
titulo();
printf("\n COMPARACION DEL METODO BURBUJA EN REALES , ENTEROS Y CARACTER :\n\n");
mostrarVectoresPrincipio(A,B,C,p_tamMos);
tituloOrde("Shell Sort ",p_tam,"Enteros ");
comienzo=time(NULL);
shell_sort(A,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Shell Sort",p_tam," Reales");
comienzo=time(NULL);
shell_sortF(B,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Shell sort ",p_tam," Caracteres");
comienzo=time(NULL);
shell_sortChar(C,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
mostrarVectoresSalida(A,B,C,p_tamMos);
printf("\n");
system("pause");
}
void opQuick(int A[],float B[],char C[],int p_tam,int p_tamMos){
time_t comienzo,final;
titulo();
printf("\n COMPARACION DEL METODO QUICK SORT EN REALES , ENTEROS Y CARACTER :\n\n");
mostrarVectoresPrincipio(A,B,C,p_tamMos);
tituloOrde("Quick Sort ",p_tam,"Enteros ");
comienzo=time(NULL);
quicksort(A,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Quick Sort",p_tam," Reales");
comienzo=time(NULL);
quicksortF(B,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Quick Sort ",p_tam," Caracteres");
comienzo=time(NULL);
quicksortChar(C,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
mostrarVectoresSalida(A,B,C,p_tamMos);
printf("\n");
system("pause");
}
void opSeleccion(int A[],float B[],char C[],int p_tam,int p_tamMos){
time_t comienzo,final;
titulo();
printf("\n COMPARACION DEL METODO SELECCION DIRECTA EN REALES , ENTEROS Y CARACTER :\n\n");
mostrarVectoresPrincipio(A,B,C,p_tamMos);
tituloOrde("Seleccion Directa",p_tam,"Enteros ");
comienzo=time(NULL);
seleccionDirecta(A,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Seleccion Directa",p_tam," Reales");
comienzo=time(NULL);
seleccionDirectaF(B,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Selecccion Directa",p_tam," Caracteres");
comienzo=time(NULL);
quicksortChar(C,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
mostrarVectoresSalida(A,B,C,p_tamMos);
printf("\n");
system("pause");
}
void mostrarVectoresPrincipio(int A[],float B[], char C[], int p_tam){
printf(" PRIMEROS %d ELEMENTOS DEL VECTOR DESORDENADO TIPO ENTERO \n" ,p_tam);
mostrarVector(A,p_tam);
printf("\n\n\n PRIMEROS %d ELEMENTOS DEL VECTOR DESORDENADO TIPO REAL \n",p_tam);
mostrarVectorF(B,p_tam);
printf("\n\n\n PRIMEROS %d ELEMENTOS DEL VECTOR DESORDENADO TIPO CARACTER \n",p_tam);
mostrarVectorChar(C,p_tam);
printf("\n\n");
}
void mostrarVectoresSalida(int A[],float B[], char C[], int p_tam){
printf("\n\n PRIMEROS %d ELEMENTOS DEL VECTOR ORDENADO TIPO ENTERO \n", p_tam);
mostrarVector(A,p_tam);
printf("\n\n\n PRIMEROS %d ELEMENTOS DEL VECTOR ORDENADO TIPO REAL \n",p_tam);
mostrarVectorF(B,p_tam);
printf("\n\n\n PRIMEROS %d ELEMENTOS DEL VECTOR ORDENADO TIPO CARACTER \n",p_tam);
mostrarVectorChar(C,p_tam);
printf("\n\n");
system ("pause");
}
void reservaMemoriaquick(long tam){
int i;
time_t comienzo,final;
int *vector , *izq;
vector = (int*)malloc(tam*sizeof(int));
if (vector==NULL)
{
perror("Problemas reservando Memoria");
}else{
printf("\n ****Exito Al Reservar Memoria****\n\n ");
cargarVectorRandP(vector,tam);
printf("\n Primeros 20 Elementos Del Vector Desordeando \n ");
mostrarVectorP(vector,20);
for(i=0;i<tam;i++){//para conocer el puntero del ultimo elemento del -vector
if(i==(tam-1)){
izq=vector;
}
vector++;
}
for(i=(tam-1);i>=0;i--){ //muevo el puntero vector a su posicion inicial
vector--;
}
printf("\n");
comienzo=time(NULL);
quicksortP(vector,izq);
final=time(NULL);
printf("\n");
mostrarTiempo(comienzo, final);
printf("\n");
printf("\n Primeros 20 Elementos Del Vector Ordeando Con Metodo Quick Sort \n ");
mostrarVectorP(vector,20);
sleep(3);
free(vector);
}
printf("\n\n");
system("pause");
}
#include<conio.h>
#include <windows.h>
#include"MetodosOrdenamientoFloatChar.h"
#include"MetodosOrdenamiento.h"
#include<time.h>
#define tam2 15
#define max1 99000
void opcionesAnimacion(int C[],int p_tam);
typedef int vectorInt[max1];
typedef float vectorFloat[tam2];
void titulo();
void gotoxy(int x,int y);
void menuOpciones();
void menuop3();
void menuOp1();
void menuOp4();
void menuOp2();
void reservaMemoriaquick(long);
void opBurbuja(int[],float[],char[],int,int);
void opInsercion(int A[],float [],char[],int,int );
void opShell(int[],float[],char[],int,int);
void opQuick(int[],float[],char[],int,int);
void opSeleccion(int[],float[],char[],int,int );
void mostrarVectoresPrincipio(int[],float[], char[], int);
void mostrarVectoresSalida(int[],float[], char[], int);
void gotoxy(int x,int y){
HANDLE hcon;
hcon = GetStdHandle(STD_OUTPUT_HANDLE);
COORD dwPos;
dwPos.X = x;
dwPos.Y= y;
SetConsoleCursorPosition(hcon,dwPos);
}
int main()
{int op;
do{
titulo();
printf(" \n Mgtr. Vallejos, Oscar Adolfo \n\n Integrantes del Grupo : \n Ledezma Lucia del Valle \n Ortiz Julio Sebastian \n Mayol Rosa Mabel \n Barrios Cintia Elizabeth ");
gotoxy(9,9);
printf("\n SALIR 0\n CONTINUAR 1 \n ");
scanf("%d",&op);
if(op==1){
menuOpciones();
}
}while(op!=0);
return 0;
}
void titulo(){
int x,y,i,z,a;
system("cls");
gotoxy(35,10);
printf("******METODOS DE ORDENAMIENTO******");
for(i=1; i<90; i++)
{
gotoxy(i,13);
printf("%c",177);
for(x=50;x<70;x++){
for(y=1;y<70;y++){
gotoxy(y,24);
}
}
}
gotoxy(20,20);
}
void menuOp1(){
time_t comienzo, final;
vectorInt A,B,C,D,E;
titulo();
//cargarVector(A);
cargarVectorRand(A,max1);
copiarVector(B,A,max1);
copiarVector(D,A,max1);
copiarVector(E,A,max1);
copiarVector(C,A,max1);
printf("\n PRIMEROS 10 ELEMENTOS DEL VECTOR DE %d NUMEROS ENTEROS \n\n",max1);
mostrarVector(A,10);
printf("\n");
printf("\n\n COMPARACION DE TIEMPO DE DURACION DE METODOS DE ORDENAMIENTO DIRECTOS Y LOGARITMICOS \n\n");
//mostrar(A);
tituloOrde("Burbuja ",max1," Enteros ");
comienzo=time(NULL);
burbuja(A,max1);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Seleccion Directa ",max1," Enteros ");
comienzo=time(NULL);
seleccionDirecta(B,max1);
final=time(NULL);
mostrarTiempo(comienzo,final);
//mostrar(A);
tituloOrde("Insercion Directa",max1," Enteros ");
comienzo=time(NULL);
insercionDirecta(C,max1);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde(" Shell Sort",max1,"Enteros ");
comienzo=time(NULL);
shell_sort(D,max1);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde(" QuicK Sort",max1,"Enteros ");
comienzo=time(NULL);
quicksort(C,max1);
final=time(NULL);
mostrarTiempo(comienzo,final);
printf("\n\n PRIMEROS 10 ELEMENTOS DEL VECTOR ORDENADO : \n\n " );
mostrarVector(A,10);
printf("\n\n");
system("pause");
system("cls");
}
void menuOpciones(){
int op;
long cantM;
do{
titulo();
printf("\n 1- Comparacion de duracion Metodos Directos y logaritmicos en Enteros \n 2-Comparacion de tiempo de duracion de Ordenamiento en Char ,Entero y Real \n 3- Ver Ordenamiento Tipo Caracter y Cadena \n 4-Ver Animaciones de Ordenamiento \n 5-Reservar Memoria para Ordenar Enteros con Quick Sort\n 6- Volver \n Opcion :... " );
scanf("%d",&op);
switch(op){
case 1 :
menuOp1();
break;
case 2:
menuOp2();
break;
case 3://solo es una musestra de como ordena caracteres y frases
menuop3();
break;
case 4 :
menuOp4();
break;
case 5:
titulo();
printf("\n Ingrese Cantidad de Memoria A Reservar : .. ");
scanf("%o",&cantM);
reservaMemoriaquick(cantM);
break;
}
}while(op!=6);
system("pause");
system("cls");
}
void menuOp4(){
int c,i,c2,c3,op,tam;
vectorInt V,B,C;
cargarVectorRand(V,9);
do{
titulo();
printf( "\n1--INGRESAR VALOR DE VECTOR POR TECLADO \n2--FUNCION RANDOM \n3--VOLVER \n ---- : ");
scanf("%d",&op);
if(op==1){
cargarVector(C,9);
opcionesAnimacion(C,9);
}
else{
if(op==2){
cargarVectorRand(C,9);
opcionesAnimacion( C,9);
}
}
}while(op!=3);
}
void opcionesAnimacion(int C[],int p_tam){
int op,c2,c;
titulo();
printf("\n VECTOR DESORDENADO \n ");
mostrarVectorPos(C,p_tam);
printf("\n\n1--METODO BURBUJA \n2--METODO SHELL \n3--INSERCCION DIRECTA \n---- : ");
scanf("%d",&op);
switch(op){
case 1:
titulo();
printf("\n VECTOR DESORDENADO \n ");
mostrarVectorPos(C,p_tam);
printf("\n");
printf("\n\n INTERCAMBIOS METODO BURBUJA :\n");
c2=burbujaMostrarInte(C,p_tam);
printf("\n\n Cantidad de Intercambios Metodo Burbuja : %d \n",c2);
printf("\n\n VECTOR ORDENADO \n\n");
mostrarVectorPos(C,p_tam);
printf("\n\n");
break;
case 2:
titulo();
printf("\n VECTOR DESORDENADO \n ");
mostrarVectorPos(C,p_tam);
printf("\n");
c=shell_sortMostrarInte(C,p_tam);
printf("\n\nCantidad de Intercambios Metodo Shell: %d \n\n",c);
printf("\n VECTOR ORDENADO \n ");
mostrarVectorPos(C,p_tam);
printf("\n \n");
break;
case 3:
titulo();
printf("\n VECTOR DESORDENADO \n ");
mostrarVectorPos(C,p_tam);
printf("\n");
c= insercionDirectaMostrarInte(C,p_tam);
printf("\n\nCantidad de Intercambios Metodo Baraja : %d \n\n",c);
printf("\n VECTOR ORDENADO \n ");
mostrarVectorPos(C,p_tam);
printf("\n\n ");
break;
}
system("pause");
}
void menuop3(){
int op;
time_t comienzo,final;
titulo();
nombre sA[9],VS[9];
char B[9];
do{
printf("\n\n DEMOSTRACION DE ORDENAMIENTO DE CARACTERES Y FRASES :\n\n");
printf("\n1-- Ver Ordenamiento de Caracteres \n2-- Ver Ordenamiento de cadenas \n3-- Volver \n.....: " );
scanf("%d",&op);
switch (op){
case 1:
titulo();
printf("\n\n VECTOR CARACTER (Cargados Aleatoriamente):\n\n");
cargarVectorCharRand(B,9);
printf("\n\n 10 PRIMEROS ELEMENTOS DE VECTOR CARACTER \n");
mostrarVectorChar(B,9);
burbujaChar(B,9);
printf("\n\n VECTOR CARACTER ORDENADO USANDO METODO BURBUJA \n");
mostrarVectorChar(B,9);
sleep(4);
printf("\n\n");
system("pause");
break;
case 2 :
titulo();
printf("\n\n VECTOR DE CADENAS : \n");
cargarVectorString(sA,9);
system("pause");
titulo();
printf("\n\n 10 PRIMEROS ELMENTOS VECTOR STRING DESORDENADO \n");
mostrarVectorString(sA,9);
burbujaString(sA,9);
printf("\n\n VECTOR STRING ORDENADO CON METODO BURBUJA \n");
mostrarVectorString(sA,9);
sleep(2);
printf("\n\n");
system("pause");
break;
}
titulo();
}while(op!=3);
}
void menuOp2(){
vectorInt A;
float B[max1];
char C[max1];
int op;
do{
titulo();
printf("\n1-- Burbuja \n2-- Inserccion Directa \n3-- Seleccion Directa \n4-- Metodo Shell Sort \n5-- Metodo Quick Sort \n6-- Volver \n.....: ");
scanf("%d",&op);
switch (op){
case 1:
cargarVectorRand(A,max1);
cargarVectorRandF(B,max1);
cargarVectorCharRand(C,max1);
opBurbuja(A,B,C,max1,10);
break;
case 2:
cargarVectorRand(A,max1);
cargarVectorRandF(B,max1);
cargarVectorCharRand(C,max1);
opInsercion(A,B,C,max1,10);
break;
case 3:
cargarVectorRand(A,max1);
cargarVectorRandF(B,max1);
cargarVectorCharRand(C,max1);
opSeleccion(A,B,C,max1,10);
break;
case 4:
cargarVectorRand(A,max1);
cargarVectorRandF(B,max1);
cargarVectorCharRand(C,max1);
opShell(A,B,C,max1,10);
break;
case 5:
cargarVectorRand(A,max1);
cargarVectorRandF(B,max1);
cargarVectorCharRand(C,max1);
opQuick(A,B,C,max1,10);
break;
}
}while(op!=6);
sleep(3);
}
void opBurbuja(int A[],float B[],char C[],int p_tam,int p_tamMos){
time_t comienzo,final;
titulo();
printf("\n COMPARACION DEL METODO BURBUJA EN REALES , ENTEROS Y CARACTER :\n\n");
mostrarVectoresPrincipio(A,B,C,p_tamMos);
tituloOrde("Burbuja ",p_tam,"Enteros ");
comienzo=time(NULL);
burbuja(A,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Burbuja ",p_tam," Reales");
comienzo=time(NULL);
burbujaF(B,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Burbuja ",p_tam," Caracteres");
comienzo=time(NULL);
burbujaChar(C,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
mostrarVectoresSalida(A,B,C,p_tamMos);
printf("\n");
system("pause");
}
void opInsercion(int A[],float B[],char C[],int p_tam,int p_tamMos){
time_t comienzo,final;
titulo();
printf("\n COMPARACION DEL METODO INSERCION DIRECTA EN REALES , ENTEROS Y CARACTER :\n\n");
mostrarVectoresPrincipio(A,B,C,p_tamMos);
tituloOrde("Insercion Directa ",p_tam,"Enteros ");
comienzo=time(NULL);
insercionDirecta(A,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Insercion Directa ",p_tam," Reales");
comienzo=time(NULL);
insercionDirectaF(B,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Insercion Directa",p_tam," Caracteres");
comienzo=time(NULL);
insercionDirectaChar(C,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
mostrarVectoresSalida(A,B,C,p_tamMos);
printf("\n");
system("pause");
}
void opShell(int A[],float B[],char C[],int p_tam,int p_tamMos){
time_t comienzo,final;
titulo();
printf("\n COMPARACION DEL METODO BURBUJA EN REALES , ENTEROS Y CARACTER :\n\n");
mostrarVectoresPrincipio(A,B,C,p_tamMos);
tituloOrde("Shell Sort ",p_tam,"Enteros ");
comienzo=time(NULL);
shell_sort(A,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Shell Sort",p_tam," Reales");
comienzo=time(NULL);
shell_sortF(B,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Shell sort ",p_tam," Caracteres");
comienzo=time(NULL);
shell_sortChar(C,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
mostrarVectoresSalida(A,B,C,p_tamMos);
printf("\n");
system("pause");
}
void opQuick(int A[],float B[],char C[],int p_tam,int p_tamMos){
time_t comienzo,final;
titulo();
printf("\n COMPARACION DEL METODO QUICK SORT EN REALES , ENTEROS Y CARACTER :\n\n");
mostrarVectoresPrincipio(A,B,C,p_tamMos);
tituloOrde("Quick Sort ",p_tam,"Enteros ");
comienzo=time(NULL);
quicksort(A,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Quick Sort",p_tam," Reales");
comienzo=time(NULL);
quicksortF(B,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Quick Sort ",p_tam," Caracteres");
comienzo=time(NULL);
quicksortChar(C,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
mostrarVectoresSalida(A,B,C,p_tamMos);
printf("\n");
system("pause");
}
void opSeleccion(int A[],float B[],char C[],int p_tam,int p_tamMos){
time_t comienzo,final;
titulo();
printf("\n COMPARACION DEL METODO SELECCION DIRECTA EN REALES , ENTEROS Y CARACTER :\n\n");
mostrarVectoresPrincipio(A,B,C,p_tamMos);
tituloOrde("Seleccion Directa",p_tam,"Enteros ");
comienzo=time(NULL);
seleccionDirecta(A,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Seleccion Directa",p_tam," Reales");
comienzo=time(NULL);
seleccionDirectaF(B,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
tituloOrde("Selecccion Directa",p_tam," Caracteres");
comienzo=time(NULL);
quicksortChar(C,p_tam);
final=time(NULL);
mostrarTiempo(comienzo,final);
mostrarVectoresSalida(A,B,C,p_tamMos);
printf("\n");
system("pause");
}
void mostrarVectoresPrincipio(int A[],float B[], char C[], int p_tam){
printf(" PRIMEROS %d ELEMENTOS DEL VECTOR DESORDENADO TIPO ENTERO \n" ,p_tam);
mostrarVector(A,p_tam);
printf("\n\n\n PRIMEROS %d ELEMENTOS DEL VECTOR DESORDENADO TIPO REAL \n",p_tam);
mostrarVectorF(B,p_tam);
printf("\n\n\n PRIMEROS %d ELEMENTOS DEL VECTOR DESORDENADO TIPO CARACTER \n",p_tam);
mostrarVectorChar(C,p_tam);
printf("\n\n");
}
void mostrarVectoresSalida(int A[],float B[], char C[], int p_tam){
printf("\n\n PRIMEROS %d ELEMENTOS DEL VECTOR ORDENADO TIPO ENTERO \n", p_tam);
mostrarVector(A,p_tam);
printf("\n\n\n PRIMEROS %d ELEMENTOS DEL VECTOR ORDENADO TIPO REAL \n",p_tam);
mostrarVectorF(B,p_tam);
printf("\n\n\n PRIMEROS %d ELEMENTOS DEL VECTOR ORDENADO TIPO CARACTER \n",p_tam);
mostrarVectorChar(C,p_tam);
printf("\n\n");
system ("pause");
}
void reservaMemoriaquick(long tam){
int i;
time_t comienzo,final;
int *vector , *izq;
vector = (int*)malloc(tam*sizeof(int));
if (vector==NULL)
{
perror("Problemas reservando Memoria");
}else{
printf("\n ****Exito Al Reservar Memoria****\n\n ");
cargarVectorRandP(vector,tam);
printf("\n Primeros 20 Elementos Del Vector Desordeando \n ");
mostrarVectorP(vector,20);
for(i=0;i<tam;i++){//para conocer el puntero del ultimo elemento del -vector
if(i==(tam-1)){
izq=vector;
}
vector++;
}
for(i=(tam-1);i>=0;i--){ //muevo el puntero vector a su posicion inicial
vector--;
}
printf("\n");
comienzo=time(NULL);
quicksortP(vector,izq);
final=time(NULL);
printf("\n");
mostrarTiempo(comienzo, final);
printf("\n");
printf("\n Primeros 20 Elementos Del Vector Ordeando Con Metodo Quick Sort \n ");
mostrarVectorP(vector,20);
sleep(3);
free(vector);
}
printf("\n\n");
system("pause");
}
Conclusión
Luego de observar los diferentes métodos de ordenamiento Directo podemos concluir que, el métodoBurbuja es aquel con mayor tiempo de ejecución a medida que el valor N se incrementa, con lo cual se ve que es el más ineficiente de todos cuando se trata de vectores de miles de elementos, pero habría que cuestionarse por qué es el método más utilizado y la respuesta estaría en la fácil comprensión del mismo, tanto en la codificación como en su forma de ordenamiento. Con los métodos de Inserción y Selección se nota una mejora en los tiempos de ejecución.
Los métodos Logarítmicos: han demostrados ser muy eficientes a la hora de ordenar miles de elementos. Pero son menos compresibles a simple vista.
El método Shell presenta mejor rendimiento debido a que es una modificación de los métodos de Inserción al realizar saltos que permiten ordenamientos múltiples, esto queda demostrado en el tiempo de ejecución.
Lo favorable del método Quick Sort es que es muy veloz, demuestra un alto rendimiento al ordenar millones de elementos, pero en apariencia es el de más difícil comprensión.
El método que más nos Impactó y entendimos mejor fue el Shell Sort;
nos resultó muy interesante la forma de comparación usando saltos y la velocidad con la que actúa u opera.
En cambio, el método que más nos costó entender fue Quick Sort, ya que su código es complejo y esto dificulta su comprensión.
Además observamos, que no es el mismo el tiempo de ejecución para ordenar diferentes tipos de datos, ya que depende de los mismos. Ordenar números Reales es más tiempo de ejecución para la CPU, luego el tipo entero y por último El tipo Carácter es el que menos tarda.
Para los ejemplos de la vida cotidiana que dimos anteriormente, cuando se trata de ordenar cientos de miles de números, conviene utilizar los métodos Logarítmicos ya que los Directos son muy lentos. Pero cabe señalar que cuando se trata de pocos elementos es mejor utilizar los Métodos Directos.
Comentarios
Publicar un comentario