FUNCIONES DE ORDENACIÓN Y BÚSQUEDA.

Descripcion:

void qsort(void *base,size_t num,size_t tamaño, int(*comparar)(const *void,const *void))

La función qsort() ordena el array al cual apunta (base) utilizando el método de quicksort. Este método se considera en general como el mejor algoritmo de clasificación de propósito general. El numero de elementos que hay en el array esta especificado por (num) y el tamaño (en bytes) de cada elemento es descrito por (tamaño).

La función a la que apunta (comparar) se utiliza para comparar un elemento del array con la (clave). La forma de la función comparar debe ser:

nombre_funcion(const void *arg1,const void *arg2)

Debe proporcionar los valores siguientes:

Si arg1 es menor que arg2, debe proporcionar un valor menor que cero.

Si arg1 es igual que arg2, debe proporcionar un valor cero.

Si arg1 es mayor que arg2, debe proporcionar un valor mayor que cero.

Ejemplo:

#include <stdio.h>

#include <conio.h>

#include <search.h>

int Comparar(const void *,const void *);

int main(void)

{

const int NUMEL=100;

int Num;

int Lista[NUMEL];

clrscr();

printf("Cuantos numeros seran: ");

scanf("%d",&Num);

printf("\n");

for(i=0;i<Num;i++){

printf("Teclee el valor [%d]=> ",i+1);

scanf("%d",&Lista[i]);

}

qsort(Lista,Num,sizeof(Lista[0]),Comparar);

printf("\n Lista de valores ordenada:\n\n");

for(j=0;j<Num;j++)

printf(" %3d\n",Lista[j]);

getch();

clrscr();

return 0;

}

int Comparar(const void *Elemento1,const void *Elemento2)

{

if(*(int *)Elemento1 < *(int *)Elemento2)

return (-1);

else if(*(int *)Elemento1 > *(int *)Elemento2)

return (1);

else

return (0);

}

Descripcion:

void *lsearch(const void *clave, const void *base,

unsigned int num, unsigned int tamaño,

int(*comparar)(const void *, const void*))

La función lsearch() ejecuta una búsqueda lineal de un dato en una array y no necesariamente clasificado. Si el dato no se encuentra la función lsearch() lo añade al final de este.

clave: Es el dato a buscar.

base: Es un puntero al primer elemento del array.

num: Es el numero de elementos del array.

tamaño: Es el tamaño (longitud) en bytes de un elemento.

comparar: Es un puntero a una función definida por el usuario, que compara dos elementos.

La forma de la funcion comparar debe ser:

nombre_funcion(const void *arg1,const void *arg2)

Debe proporcionar los valores siguientes:

!= 0 Si el arg1 y el arg2, son distintos.

= 0 Si arg1 es igual que arg2.

Si la busqueda falla, la funcion lsearch() retorna un puntero al elemento añadido al final del array.

Ejemplo:

#include <stdio.h>

#include <conio.h>

#include <search.h>

#define NUMEL 20

size_t NELEMENTOS;

int MAX;

int Lista[NUMEL];

int Comparar(const int *Elemento1,const int *Elemento2)

{

return(*Elemento1 - *Elemento2);

}

int AgregarElemento(int *Dato)

{

int Temporal = NELEMENTOS;

lsearch(Dato, Lista,&NELEMENTOS, sizeof(int),

(int(*)(const void *,const void *))Comparar);

return(NELEMENTOS == Temporal);

}

int main(void)

{

int Dato;

int i;

clrscr();

printf(" Escriba cuantos elementos seran: ");

scanf("%d",&MAX);

NELEMENTOS=MAX;

for(i=0;i<MAX;i++){

printf(" Escriba el dato [%d] => ",i+1);

scanf("%d",&Lista[i]);

}

printf("\n\n Escriba el numero a buscar-> ");

scanf("%d",&Dato);

if(AgregarElemento(&Dato)){

printf("\n %d esta en la lista de valores.",Dato);

printf("\n\n Lista de valores:\n\n");

for(i=0;i<MAX;i++)

printf(" %3d\n",Lista[i]);

}

else{

Lista[MAX]=Dato;

printf("\n %d ha sido agregado a la lista de valores.",Dato);

printf("\n\n Lista de valores:\n\n");

for(i=0;i<=MAX;i++)

printf(" %3d\n",Lista[i]);

}

getch();

return 0;

}

Descripcion:

void *lfind(const void *clave,const void *base,

unsigned int num, unsigned int tamaño,

int(*comparar)(const void *, const void*))

La funcion lfind() ejecuta una búsqueda lineal de un dato en una array y no necesariamente clasificado.

clave: Es el dato a buscar.

base: Es un puntero al primer elemento del array.

num: Es el numero de elementos del array.

tamaño: Es el tamaño (longitud) en bytes de un elemento.

comparar: Es un puntero a una función definida por el usuario, que

compara dos elementos.

La forma de la función comparar debe ser:

nombre_función(const void *arg1,const void *arg2)

Debe proporcionar los valores siguientes:

!= 0 Si el arg1 y el arg2, son distintos.

= 0 Si arg1 es igual que arg2.

Si la búsqueda falla, la función lfind() retorna NULL.

Ejemplo:

#include <stdio.h>

#include <conio.h>

#include <search.h>

#define NUMEL 20

int Comparar(const int *Elemento1,const int *Elemento2)

{

return(*Elemento1 - *Elemento2);

}

int main(void)

{

int Lista[NUMEL];

int Dato;

size_t NELEMENTOS;

int MAX;

int *Encontrar,i;

clrscr();

printf(" Escriba cuantos elementos seran: ");

scanf("%d",&MAX);

NELEMENTOS=MAX;

for(i=0;i<MAX;i++){

printf(" Escriba el dato [%d] => ",i+1);

scanf("%d",&Lista[i]);

}

printf("\n\n Escriba el numero a buscar-> ");

scanf("%d",&Dato);

Encontrar=(int *)lfind(&Dato,Lista,&NELEMENTOS,sizeof(int),

(int(*)(const void *,const void *))Comparar);

if(Encontrar) printf("\n %d esta en la lista.\n",Dato);

else printf("\n %d no se encontro en la lista.\n",Dato);

getch();

return 0;

}

Descripcion:

void *bsearch(const void *clave, const void *base

unsigned num, unsigned tamaño,

int(*comparar)(const void *,const void *))

La funcion bsearch() lleva a cabo una búsqueda binaria en el array ordenado al que apunta (base), y proporciona un puntero del primer miembro que coincida con la clave a la que apunta (clave). El numero de elementos del array esta especificado en (num), y el tamaño (en bytes) de cada elemento lo describe (tamaño).

La función a la que apunta (comparar) se utiliza para comparar con la clave un elemento del array. La forma de la función comparar debe ser:

nombre_funcion(const void *arg1,const void *arg2)

Debe proporcionar los valores siguientes:

Si arg1 es menor que arg2, debe proporcionar un valor menor que cero.

Si arg1 es igual que arg2, debe proporcionar un valor cero.

Si arg1 es mayor que arg2, debe proporcionar un valor mayor que cero.

Ejemplo:

#include <stdio.h>

#include <conio.h>

#include <search.h>

#define NUMEL 20

int Comparar(const int *Elemento1,const int *Elemento2)

{

return(*Elemento1 - *Elemento2);

}

int main(void)

{

int Lista[NUMEL];

int Dato,MAX;

int *Busca,i;

clrscr();

printf(" Escriba cuantos elementos seran: ");

scanf("%d",&MAX);

for(i=0;i<MAX;i++){

printf(" Escriba el dato [%d] => ",i+1);

scanf("%d",&Lista[i]);

}

printf("\n\n Escriba el numero a buscar-> ");

scanf("%d",&Dato);

Busca=(int *)bsearch(&Dato,Lista,MAX,sizeof(int),

(int(*)(const void *,const void *))Comparar);

if(Busca) printf("\n Esta en la lista.\n");

else printf("\n No se encontro en la lista.\n");

getch();

return 0;

}

Método de la Burbuja.

Hay muchas formas de clasificar datos y una de las más conocidas es la clasificación por el método de la de burbuja.

A continuación se muestra su algoritmo correspondiente, para ordenar una lista de menor a mayor, partiendo de que los datos a ordenar están en una lista de n elementos:

1.- Comparamos el primer elemento con el segundo, el segundo con el tercero, el tercero con el cuarto, etc. Cuando el resultado de una comparación sea “mayor que”, se intercambian los valores de los elementos comparados. Con esto conseguimos llevar el valor mayor a la posición n.

2.- Repetimos el punto 1, ahora para los n-1 primeros elementos de la lista. Con esto conseguimos, llevar el valor mayor de éstos a la posición n-1.

3.- Repetimos el punto 1, ahora para los n-2 primeros elementos de la lista y así sucesivamente.

4.- El proceso termina después de repetir el punto 1, n-1 veces, o cuando al finalizar la ejecución del punto 1 no haya habido ningún cambio.

El pseudocódigo para este algoritmo puede ser el siguiente:

<función clasificar (array “a” de “n” elementos)>

[“a” es un array cuyos elementos son a₀, a₁, ….., a_n-1]

n = n-1

DO WHILE (“a” no esté ordenado y n > 0)

i = 1

DO WHILE (i < = n)

IF (a[i-1] > a[i] ) THEN

Intercambiar a[i-1] con a[i]

ENDIF

i = i + 1

ENDDO

n = n – 1

ENDDO

END < clasificar >

Ejemplo:

#include <stdio.h>

#include <conio.h>

#include <string.h>

#include <ctype.h>

#include <stdlib.h>

void BurbujaString();

void Menu();

int main(void)

{

int opcion;

system("cls");

Menu();

scanf("%d",&opcion);

while(opcion!=2){

switch(opcion){

case 1 : BurbujaString();

break;

default: printf("\n Opcion Invalida.");

getch();

Menu();

}

Menu();

scanf("%d",&opcion);

}

gotoxy(33,15);

printf("Fin de %s",__FILE__);

getch();

return 0;

}

void Menu(void)

{

system("cls");

gotoxy(35,2);

printf(" M E N U");

printf("\n\n OPCIONES:");

printf("\n\n 1) Lee, ordena y despliega cadenas en forma ascendente.");

printf("\n\n 2) Salida");

printf("\n\n Escoja una opcion: ");

}

void BurbujaString(void)

{

int n,i,j;

char Arreglo[30][25];

system("cls");

printf("\n Programa que lee, ordena y despliega cadenas");

printf("\n\n Cuantas cadenas va a leer: ");

scanf("%d",&n);

for(i=1;i<=n;i++){

printf("\n De la cadena[%d]: ",i);

scanf("%s",&Arreglo[i]);

if(!isalpha(*Arreglo[i])){

printf("\n Fatal Error. Debe ser una cadena.");

getch();

exit(1);

}

for(i=1;i<n;i++)

for(j=1;j<n;j++)

if(strcmp (Arreglo[j], Arreglo[j+1])>0){

strcpy (Arreglo[0],Arreglo[j]);

strcpy (Arreglo[j],Arreglo[j+1]);

strcpy (Arreglo[j+1],Arreglo[0]);

}

printf("\n\n Las cadenas ordenadas son: ");

for(i=1;i<=n;i++)

printf("\n\n %s",Arreglo[i]);

getch();

}

Método Quicksort

El método de ordenación Quicksort, está generalmente considerado como el mejor algoritmo de ordenación disponible actualmente.

El algoritmo correspondiente a este método, es el siguiente:

1. Se selecciona un valor del array. Este valor se puede escoger aleatoriamente o haciendo la media de un pequeño conjunto de valores tomados del array. El valor óptimo sería aquel que esté precisamente en medio del rango de valores (mediana). No obstante, incluso en el peor de los casos, Quicksort funciona correctamente.

2. Se divide el array en dos partes, una con todos los elementos menores que el valor seleccionado y otra con todos los elementos mayores o iguales.

3. Se repiten los puntos 1 y 2 para cada parte restante hasta que el array esté ordenado.

El proceso descrito es esencialmente recursivo.

El pseudocódigo para este algoritmo puede ser el siguiente:

<función Qs (array “a”) >

Se elige un valor x

DO WHILE (“a” no esté ordenado)

[Dividir “a” en dos partes: inf y sup]

inf con los elementos a_i < x

sup con los elementos a_i>= x

ENDDO

IF (existe inf) THEN

Qs(inf )

ENDIF

IF (existe sup) THEN

Qs(sup)

ENDIF

END < Qs >

Ejemplo:

#include <stdio.h>

#include <conio.h>

#include <string.h>

void OrdenaCadena(char Datos[][10],int Izq,int Der);

void QuicksortString(char Datos[][10],int Elementos);

void main(void)

{

char cadena[10][10];

int MAX,i;

clrscr();

printf("Cuantas cadenas seran: ");

scanf("%d",&MAX);

for(i=0;i<MAX;i++){

printf("Introduzca una cadena: ");

scanf("%s",cadena[i]);

}

QuicksortString(cadena,MAX);

printf("\n La cadena odenada es: ");

for(i=0;i<MAX;i++)

printf("\n %s",cadena[i]);

getch();

}

void QuicksortString(char Datos[][10],int Elementos)

{

OrdenaCadena(Datos,0,Elementos-1);

}

void OrdenaCadena(char Datos[][10],int Izq,int Der)

{

char *Mitad;

char Temporal[10];

i=Izq;

j=Der;

Mitad=Datos[(Izq+Der)/2];

do{

while((strcmp(Datos[i],Mitad)<0) && (i<Der)) i++;

while((strcmp(Datos[j],Mitad)>0) && (j>Izq)) j--;

if(i<=j){

strcpy(Temporal,Datos[i]);

strcpy(Datos[i],Datos[j]);

strcpy(Datos[j],Temporal);

i++;

j--;

}

}while(i<=j);

if(Izq < j) OrdenaCadena(Datos,Izq,j);

if(i < Der) OrdenaCadena(Datos,i,Der);

}

Búsqueda binaria

Un método eficiente de búsqueda, que puede aplicarse a los arrays clasificados, es la búsqueda binaria. Partiendo de que los elementos del array están almacenados en orden ascendente, la búsqueda binaria consiste en lo siguiente:

Se selecciona el elemento del centro o aproximadamente del centro de array. Si el valor a buscar no coincide con el elemento seleccionado y en mayor que él, se continúa la búsqueda en la segunda mitad del array. Si por el contrario, el valor a buscar es menor que el valor de elemento seleccionado, la búsqueda continúa en la primera mitad del array. En ambos casos, se halla de nuevo el elemento central, correspondiente al nuevo intervalo de búsqueda, repitiéndose el ciclo. El proceso se repite hasta que se encuentra el valor a buscar, o bien hasta que el intervalo de búsqueda sea nulo, lo que querrá decir que el elemento buscado no figura en el array.

El pseudocódigo para este algoritmo puede ser el siguiente:

< función BúsquedaBinaria (array a, valor a buscar) >

DO WHILE (exista un intervalo donde buscar y no encontrado)

x = elemento mitad del intervalo de búsqueda

IF (valor == x ) THEN

encontrado

ELSE IF (valor > x ) THEN

Buscar “x” en la segunda mitad del intervalo de búsqueda

ENDIF

IF (valor < x) THEN

Buscar “x” en la primera mitad del intervalo d búsqueda.

ENDIF

ENDDO

END <BúsquedaBinaria>

Ejemplo:

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <ctype.h>

typedef enum{FALSE,TRUE}boolean;

int main(void)

{

const int NUMEL = 50;

int Arreglo[NUMEL], i, j, Temporal, y=3, Izq, Der;

int Valor, LimiteSuperior, LimiteInferior, Pivote;

int MAX;

boolean Encontrado;

div_t division;

clrscr();

gotoxy(1,1);

printf("Escriba cuantos numeros seran: ");

scanf("%d",&MAX);

gotoxy(1,2);

printf("Escriba %d numeros.", MAX);

/*Lee los valores*/

for (i=0; i<MAX; i++) {

gotoxy(1,y++);

printf("%2d: ", i+1);

scanf("%d", &Arreglo[i]);

}

/* Ordena los valores. Método SHELL.*/

division=div(MAX,2);

Izq=division.quot;

Der=division.quot;

/*ordena los valores*/

do {

for (i=0, j=Der; i<Izq, j<MAX; i++, j++) {

if (Arreglo[i]>Arreglo[j]) {

Temporal=Arreglo[i];

Arreglo[i]=Arreglo[j];

Arreglo[j]=Temporal;

}

Izq++;

Der--;

} while(Izq<MAX);

/*Pregunta por el valor a buscar*/

/*muestra los valores*/

gotoxy(25,2);

printf("Numeros ordenados.");

y=3;

for (i=0; i<MAX; i++) {

gotoxy(30,y++);

printf("%d", Arreglo[i]);

}

gotoxy(25,24);

printf("Valor a buscar ? : ");

scanf("%d", &Valor);

/*busca si algun valor coincide con la lista*/

for (i=0; i<MAX; i++) {

if (Valor==Arreglo[i]) {

Encontrado=TRUE;

break;

}

/*si encontro algun(os) valor(es) lo(s) procesa*/

if (Encontrado) {

textcolor(YELLOW);

gotoxy(55,2);

cprintf("NUMERO ENCONTRADO");

textcolor(7);

LimiteSuperior=MAX;

LimiteInferior=0;

y=3;

for (i=0; i<MAX; i++) {

if (Valor>Arreglo[i]) { /*si es mayor avanza a la derecha.*/

Pivote=(LimiteSuperior-LimiteInferior)/2;

LimiteSuperior=Pivote;

LimiteInferior=0;

y++;

}

if (Valor<Arreglo[i]) { /*si es menor avanza a la izquierda.*/

Pivote=(LimiteSuperior-LimiteInferior)/2;

LimiteSuperior=MAX;

LimiteInferior=Pivote;

y++;

}

if (Valor==Arreglo[i]) { /*si es igual imprime la posicion.*/

gotoxy(40,y++);

printf("<------------- En la posicion [%d]", i+1);

}

else {

textcolor(YELLOW);

gotoxy(55,1);

cprintf("NUMERO NO ENCONTRADO");

}

getch();

return 0;

}

Para cualquier duda o sugerencia puedes escribirme a mi correo ajuarezoliveros@yahoo.com.mx

Nota.- Todo los programas han sido probados con los compiladores Turbo C++ versión 3.0 y con el compilador Borland C++ versión 3.1.

Si ejecutan estos programas con algún compilador más antiguo que los que mencionamos por ejemplo: como el Turbo C versión 2.01 o Turbo C++ 1.01 deberán cambiar la librería <search.h> por la librería <stdlib.h> para que les funcione correctamente el programa y no les marque algún error.