• Asignatura: Informática
  • Autor: emiliadaleska
  • hace 8 años

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

Respuesta dada por: yessica93
0

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

Adjuntos:
Preguntas similares