Estructuras de Datos II: Ejercicios Prácticos de Métodos de Búsqueda y Ordenamiento en C/C++

 

Dado un vector numérico entero de 22 elementos introducidos de forma aleatoria con valores positivos y ordenados de forma ascendente. Pedir por teclado el valor a buscar en el vector y realizar una búsqueda dicotómica. Antes de finalizar se visualizará el vector y si el elemento se encontró la posición que ocupa y en caso contrario se visualizará mediante un mensaje adecuado que el elemento no se encontró en el vector.

Para la resolución de este ejercicio, hemos utilizado la búsqueda dicotómica, dado que podemos acceder a un array ordenado y buscar un dato concreto, de una forma muy sencilla. Además, éste método reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de iteraciones necesarias.

#include <stdio.h>

#include<conio.h>

int main (){

//crear vector con 22 elementos

int a[22]= {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43};

//crear variables

int dato; //valor ingresado a buscar por el usuario

int inf; // lado izquierdo del vector

int sup; //lado derecho del vector

int mitad; //centro del vector

int posicion; //lugar del dato en el vector

char band='F'; //valor para determinar si el dato fue encontrado

//solicitar a usuario valor a buscar

printf("\n Ingrese un nro a buscar entre 0 y 45: ");

scanf("%i",&dato);

//Búsqueda Dicotómica

inf=0;

sup=22;

while (inf <=sup)

{

mitad =(inf + sup)/2;

if (a[mitad]==dato){

band='V';

break;

}

if (a[mitad]>dato){

sup=mitad;

mitad=(inf+sup)/2;

}

if (a[mitad]<dato){

inf=mitad;

mitad - (inf+sup)/2;

}

}

if (band=='F'){

printf("El valor buscado no esta dentro del vector");

}

else if (band=='V')

{

posicion=mitad + 1;

printf("El valor buscado esta en la posicion: %i",posicion);

}

getch();

return 0;

}

Dado un vector numérico entero de 20 ordenar los números enteros contenidos en el array a través del método de la burbuja.

Hemos utilizado el método burbuja dado que es uno de los procedimientos más comunes y útiles en el procesamiento de datos, es la ordenación de los mismos. Se considera ordenar al proceso de reorganizar un conjunto dado de objetos en una secuencia determinada (patrón de arreglo). El objetivo de este proceso generalmente es facilitar la búsqueda de uno o más elementos pertenecientes a un conjunto; en nuestro caso, al vector numérico.

#include “iostream.h”

#include “conio.h”

//metodo para imprimir al vector

int num[20],n;

void muestra_vector(){

for (int t; t=0; t<n; t++)

{

cout<<num[t]<<” ”;

}

}

//metodo de ordenacion burbuja

void ordenar_burbuja(){

int temp;

for (int i =0; i<n; i ++)

{

for (int k=n-1; k>0; k--)

{

if (num[k]<num[k-1]){

temp=num[k];

num[k]=num[k-1];

num[k-1]=temp;

}

}

}

//parte principal del programa

main(){

//asignacion del los elementos del vector

vector<int> num(8,10,13,4,5,6,7,9,15,20,11,2,30,31,25,26,24,28,19,17);

//impresion del vector desordenado

cout<<”Antes de ordenar: ”<<endl;

for (int j=0;j<n; j++)

{

cout <<num[j] << “ ”;

}

//llamado al metodo burbuja para que ordene el vector

ordenar_burbuja();

//impresion del vector ordenado

cout <<”Ordenamiento Metodo Burbuja: ”<<endl;

muestra_vector();

getch();

}