Una de las acciones que se puede implementar sobre los arreglos es la búsqueda de
un elemento que se encuentra dentro del arreglo. Existe un método de búsqueda que
necesita que los valores del arreglo estén ordenados, para dividirlo en dos partes y
que utiliza recursividad para mejorar el tiempo que se emplea en la tarea.
Consulte el método que cumple con esa característica e impleméntelo utilizando el
lenguaje de programación Java. ayudenme a hacer esta tarea porfavor? en lenguaje de programación
Respuestas
El algoritmo con esas características se le denomina Método de ordenación MergeSort o el algoritmo de ordenamiento por fusión.
Vamos a implementarlo en Java con un pseudocódigo:
// Primero tenemos una clase con el nombre de fusion donde vamos a crear un arreglo, puedes agregar un vector manualmente o pedirlo por teclado:
//Constructor de la clase
public static void fusion(int array[]){
int [] tmp = new int[array.length];
mergesort(array, tmp, 0, array.length-1);
}
//Código de fusión los dos arreglos
private static void fusion(int[] a, int[] tmp, int left, int right){
if(left < right){
int centre = (left + right)/2; // Dividimos el arreglo en dos
mergesort(a, tmp, left, centre); //creamos un primer arreglo
mergesort(a, tmp, centre+1, right); //creamos un segundo arreglo
merge(a, tmp, left, centre+1, right); // Ordenamos y buscamos
} }
utilizando
private static void merge(int [] a, int [] tmp, int left, int right, int rend){
int lend = right-1;
int tpos = left; int lbeg = left;
while(left <= lend && right <= rend){
if(a[left] < a[right]){
tmp[tpos++] = a[left++];
}else{
tmp[tpos++] = a[right++];
} }
while(left <= lend){
tmp[tpos++] = a[left++]; }
while(right <= rend){
tmp[tpos++] = a[right++]; }
for(tpos = lbeg; tpos <= rend; tpos++){
a[tpos] = tmp[tpos];
} }
// Luego de ordenar puedes aplicar un algoritmo de Búsqueda lineal recursiva.
Básicamente va dividiendo en mitades cada bloque, si por ejemplo el tamaño del vector es 4, este se dividirá en 2 arreglos de dos elementos, y a su vez estos se dividirán en 4 arreglos de 1 solo elementos, y que luego hacer el proceso inverso pero ordenándolos de menor a mayor, esto es lo que le otorga la característica de recursivo.
Adjunto una imagen del proceso
