Algoritmos de Ordenamiento y Búsqueda en C: Implementación Práctica de Burbuja, Inserción, Selección, Secuencial y Binaria
Enviado por Comunidad Xuletas y clasificado en Informática y Telecomunicaciones
Escrito el en 
español con un tamaño de 8,96 KB
Algoritmos de Ordenamiento y Búsqueda en C
A continuación se presenta un programa en lenguaje C que implementa distintos métodos de ordenamiento y métodos de búsqueda sobre arreglos de números enteros. El programa muestra un menú interactivo que permite elegir el algoritmo a ejecutar.
Bibliotecas y declaración de funciones
El programa incluye las bibliotecas estándar necesarias y declara las funciones que componen el sistema:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>
int tam_array(void);
void mostrar_burbuja(int u);
void burbuja(int a[], int w);
void mostrar_insercion(int u);
void insercion(int a[], int w);
void mostrar_seleccion(int u);
void seleccion(int a[], int w);
void mostrar_secuencial(int u);
void secuencial(int a[], int w);
void mostrar_binaria(int u);
void binaria(int a[], int w);Función principal y menú de opciones
La función main() configura la consola, muestra el menú y, según la opción elegida por el usuario, invoca el método correspondiente. Se utiliza srand(time(NULL)) para generar valores aleatorios distintos en cada ejecución.
main()
{
system("color 2A");
char programa;
system("cls");
printf(" \n");
printf(" °°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°\n");
printf(" °° ELIJA UN PROGRAMA °°\n");
printf(" °°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°\n");
printf(" \n");
printf("\t\t\t1. METODO DE ORDENAMIENTO BURBUJA\n");
printf("\t\t\t2. METODO DE ORDENAMIENTO INSERCION\n");
printf("\t\t\t3. METODO DE ORDENAMIENTO SELECCION\n");
printf("\t\t\t4. METODO DE ORDENAMIENTO QUICKSORT\n");
printf("\t\tII BUSQUEDAS\n");
printf("\t\t\t5. BUSQUEDA SECUENCIAL\n");
printf("\t\t\t6. BUSQUEDA BINARIA\n\n");
printf("\t\t\tS. SALIR\n");
printf("\t\t**************************************************");
printf("\n\n OPCION : ");
scanf("%c", &programa);
switch(programa) {
case '1': srand(time(NULL));
mostrar_burbuja(tam_array());
break;
case '2': srand(time(NULL));
mostrar_insercion(tam_array());
break;
case '3': srand(time(NULL));
mostrar_seleccion(tam_array());
break;
case '5': srand(time(NULL));
mostrar_secuencial(tam_array());
break;
case '6': srand(time(NULL));
mostrar_binaria(tam_array());
break;
case 'S': break;
default: printf(" \n");
printf(" \t\t\t ************************************* \n");
printf(" \t\t\t * SOLO (1),(2),(3),(4),(5),(6) O (S)* \n");
printf(" \t\t\t *************************************");
break;
}
getch();
}Captura del tamaño del arreglo
int tam_array()
{
int t;
printf("TAMAÑO DEL ARRAY: ");
scanf("%d", &t);
return t;
}Método de ordenamiento burbuja
La función mostrar_burbuja genera el arreglo con valores aleatorios entre 1 y u, lo imprime y llama a burbuja, que compara elementos adyacentes e intercambia los que están desordenados. El algoritmo reduce el rango de comparación en cada pasada gracias a la variable k.
void mostrar_burbuja(int u)
{
int i, array[u], n;
int t;
printf("\n LOS ELEMENTOS DEL ARREGLO SON: \n");
for(i = 0; i < u; i++) {
array[i] = rand() % u + 1;
}
printf("\t\tARRAY: ");
for(i = 0; i < u; i++) {
printf("%d ", array[i]);
}
printf("\n\n\n");
burbuja(array, u);
return;
}
void burbuja(int a[], int w)
{
int i, t, j, k, aux;
printf("\t\tMETODO BURBUJA: ");
t = w;
i = w - 1;
while(i > 0) {
k = 0;
for(j = 0; j < i; j++)
if(a[j+1] < a[j]) {
aux = a[j];
a[j] = a[j+1];
a[j+1] = aux;
k = j;
}
i = k;
}
for(i = 0; i < w; i++)
printf("%d ", a[i]);
return;
}Método de ordenamiento por inserción
El método de inserción toma cada elemento y lo desplaza hacia la izquierda hasta encontrar su posición dentro de la porción ya ordenada del arreglo.
void mostrar_insercion(int u)
{
int i, array[u], n;
int t;
printf("\n LOS ELEMENTOS DEL ARREGLO SON: \n");
for(i = 0; i < u; i++) {
array[i] = rand() % u + 1;
}
printf("\t\tARRAY: ");
for(i = 0; i < u; i++) {
printf("%d ", array[i]);
}
printf("\n\n\n");
insercion(array, u);
return;
}
void insercion(int a[], int w)
{
int i, j, aux;
printf("\t\tMETODO INSERCION: ");
for(j = 1; j < w; j++) {
i = j;
aux = a[j];
while(i > 0 && aux < a[i-1]) {
a[i] = a[i-1];
i--;
}
a[i] = aux;
}
for(i = 0; i < w; i++)
printf("%d ", a[i]);
getch();
}Método de ordenamiento por selección
En el método de selección, en cada iteración se busca el elemento menor de la porción no ordenada y se intercambia con la posición actual.
void mostrar_seleccion(int u)
{
int i, array[u], n;
int t;
printf("\n LOS ELEMENTOS DEL ARREGLO SON: \n");
for(i = 0; i < u; i++) {
array[i] = rand() % u + 1;
}
printf("\t\tARRAY: ");
for(i = 0; i < u; i++) {
printf("%d ", array[i]);
}
printf("\n\n\n");
seleccion(array, u);
return;
}
void seleccion(int a[], int w)
{
int i = 0, j = 0, x = 0, im, aux;
printf("\t\tMETODO SELECCION: ");
for(i = 0; i < w; i++) {
x++;
im = i;
for(j = i + 1; j < w; j++) {
if(a[j] < a[im]) {
im = j;
}
}
aux = a[i];
a[i] = a[im];
a[im] = aux;
}
for(i = 0; i < w; i++)
printf("%d ", a[i]);
getch();
}Búsqueda secuencial
La búsqueda secuencial recorre el arreglo elemento por elemento comparando con el número ingresado por el usuario.
void mostrar_secuencial(int u)
{
int i, array[u], n;
int t;
printf("\n EL ARREGLO ES: ");
for(i = 0; i < u; i++) {
array[i] = rand() % u + 1;
}
printf("\t\tARRAY: ");
for(i = 0; i < u; i++) {
printf("%d ", array[i]);
}
printf("\n\n\n");
secuencial(array, u);
return;
}
void secuencial(int a[], int w)
{
int i = 0, j = 0, num = 0;
printf("INGRESE NUMERO QUE DESEA BUSCAR: ");
scanf("%d", &num);
for(i = 0; i < w; i++)
if(a[i] == num) {
printf("\nNUMERO ENCONTRADO");
printf(" EN LA POSICION: %d", i + 1);
} else {
printf("\nNO SE ENCONTRO EN LA POSICION: %d", i + 1);
}
getch();
}Búsqueda binaria
La búsqueda binaria divide repetidamente el intervalo de búsqueda a la mitad. Es importante recordar que este método requiere que el arreglo esté ordenado previamente.
void mostrar_binaria(int u)
{
int i, array[u], n;
int t;
printf("\nINGRESE LOS ELEMENTOS DEL ARREGLO: \n");
for(i = 0; i < u; i++) {
array[i] = rand() % u + 1;
}
printf("\t\tARRAY: ");
for(i = 0; i < u; i++) {
printf("%d ", array[i]);
}
printf("\n\n\n");
binaria(array, u);
return;
}
void binaria(int a[], int w)
{
int x, i, e, t, b, al, c;
printf("\tINGRESE UN NUMERO: ");
scanf("%d", &x);
b = 0;
al = w - 1;
c = (b + al) / 2;
while(b < al && x != a[c]) {
if(x > a[c])
b = c + 1;
else
al = c - 1;
c = (b + al) / 2;
}
if(x == a[c])
printf("\n%d LA POSICION ES %d", x, c + 1);
else
printf("\n%d NO VALIDO", x);
for(i = 0; i < w; i++)
printf("%d ", a[i]);
getch();
}Conclusiones
Este programa permite comparar de forma práctica el funcionamiento de los algoritmos de ordenamiento y de búsqueda más utilizados en la enseñanza de la programación. Su estructura modular, basada en funciones independientes para cada método, facilita su estudio, modificación y ampliación.