Busqueda y ordenamiento

BUSQUEDA Y ORDENAMIENTO
La búsqueda de datos implica la determinación de si un valor (conocido como la clave de búsqueda) se encuentra o no en dentro del conjunto de datos, y de ser así hay que encontrar su ubicación.
Existen dos algoritmos muy conocidos de búsqueda estos son:
1. Búsqueda Lineal Simple.
2. Búsqueda Binaria.
En cuanto al ordenamiento de datos es un proceso queconsiste en colocar los datos en orden ascendente o descendente, con base en una o más claves de ordenamiento.
Algoritmos de Búsqueda
Buscar un número telefónico, buscar un sitio web y comprobar la definición de una palabra en el diccionario son acciones que implican realizar una búsqueda en grandes cantidades de datos. En la siguiente parte hablaremos sobre los dos algoritmos de búsqueda yamencionados anteriormente el primero que es fácil de programar pero relativamente ineficiente, y el segundo que es relativamente eficiente pero más complejo y difícil de programar.
1. Búsqueda Lineal
Este algoritmo busca por cada elemento de un arreglo en forma secuencial. Si la clave de búsqueda no coincide con un elemento del arreglo, el algoritmo evalúa cada elemento, y cuando llega al final delarreglo informa al usuario que la clave de búsqueda no esta presente. Si la clave de búsqueda esta en el arreglo, el algoritmo de búsqueda evalúa cada elemento hasta encontrar uno que coincida con la clave de búsqueda y devuelve el índice de ese elemento.

Implementación del código

En un arreglo.

import java.util.Random;
public class ArregloLineal
{
private int datos[];
privatestatic Random generador = new Random();

public ArregloLineal(int tamaño)
{
datos = new int[tamaño];

for (int i=0; i<tamaño; i++)
datos[i] = 10 + generador.nextInt(90);
}
public int busquedaLineal(int claveBusqueda)
{
for(int indice=0; indice<datos.length; indice++)
if(datos[indice]==claveBusqueda)
return indice;
return -1;
}
public String toString()
{StringBuilder temporal = new StringBuilder();
for(int elemento: datos)
temporal.append(elemento + “ “);
temporal.append(“\n”);
return temporal.toString();
}
}
Class principal.

Import java.util.Scanner;

public class PruebaBusquedaLineal
{
public static void main(String args[])
{
Scanne r entrada = new Scanner(System.in);
int enteroBusqueda;
int posicion;ArregloLineal arregloBusqueda = new ArregloLineal(10);
System.out.println(arregloBusqueda);

System.out.print(“Escriba un valor entero (-1 para terminar): “);
enteroBusqueda = entrada.nextInt();

while(enteroBusqueda!= -1)
{
posicion = arregloBusqueda.busquedaLineal(enteroBusqueda);

if(posicion == -1)
System.out.println(“El entero” + enteroBusqueda + “no seencontro” + “\n”);
else
System.out.println(“El entero” + enteroBusqueda + “se encontró en la posicion” + posicion + “\n”);
System.out.print(“Escriba un valor entero (-1 para terminar): “);
enteroBusqueda = entrada.nextInt();
}
}
}

2. Búsqueda Binaria
El algoritmo de búsqueda binaria es más eficiente que el algoritmo de búsqueda lineal, pero requiere que se ordene el arreglo.La primera iteración de este algoritmo evalúa el elemento medio del arreglo. Si este coincide con la clave de búsqueda, el algoritmo termina.

Implementación del código

En un arreglo.

import java.util.Random;
import java.util.Arrays;

public class ArregloBinario
{
private int datos[];
private static Random generador = new Random();

public ArregloBinario(int tamaño)
{
datos= new int[tamaño];
for (int i=0; i<tamaño; i++)
datos[i] = 10 + generador.nextInt(90);
Arrays.sort(datos);
}

public int busquedaBinaria(int elementoBusqueda)
{
int inferior = 0;
int superior = datos.length – 1;
int medio = (inferior + superior + 1)/2;
int ubicacion = -1;

do
{
System.out.print(elementosRestantes(inferior, superior));
for(int i =...