Programación Búsqueda Binaria y Método Burbuja

PROGRAMACIÓN

Evelyn Michelle Ordóñez

MÉTODO BÚSQUEDA

Algoritmo y programa para realizar la ordenación de

un arreglo mediante el método "burbuja".

Qué es el método ‘‘Búsqueda’’

Consiste en acomodar el vector moviendo el mayor hasta la última casilla comenzando desde la casilla cero del vector hasta haber acomodado el número más grande el la última posición, una vez acomodado el más grande, prosigue a encontrar  y acomodar el siguiente más grande comparando de nuevo los números desde el inicio del vector, y así sigue hasta ordenar todo los elementos el arreglo. Este algoritmo es muy deficiente ya que al ir comparando las casillas para buscar el siguiente más grande, éste vuelve a comparar las ya ordenadas. A pesar de ser el algoritmo de ordenamiento más deficiente que hay, éste es el más usado en todos los lenguajes de programación.

Es recorrer todo el arreglo la misma cantidad de veces como elementos tenga el arreglo menos uno, comparando los valores de dos elementos del arreglo y ordenándolos dependiendo si se desea descendente o ascendentemente.

Algoritmo

algoritmo burbuja( A : array de n elementos indizados de 1 a n) para i desde 1 hasta n-1 hacer: //las n-1 pasadas para j desde 1 hasta n-i hacer: //el recorrido si A[j] > A[j+1] entonces //Si no están en orden intercambiar A[j] y A[j+1] //Se intercambian fin para fin parafin algoritmo

public class Burbuja { public static void main(String arg[]) throws IOException { /*creacion del objeto para leer por teclado*/ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); /*ingreso del tamaño de arreglos*/ System.out.print("\n Ingrese Numero de Datos a Ingresar : "); int tam = Integer.parseInt(in.readLine()); /*creacion del arreglo*/ int arr[] = new int[tam]; System.out.println(); /*lectura del arreglo*/ int j = 0; for (int i = 0; i < arr.length; i++) { j += 1; System.out.print("Elemento " + j + " : "); arr[i] = Integer.parseInt(in.readLine()); } burbuja(arr); } static void burbuja(int arreglo[]) { for (int i = 0; i < arreglo.length - 1; i++) { for (int j = 0; j < arreglo.length - 1; j++) { if (arreglo[j] < arreglo[j + 1]) { int tmp = arreglo[j + 1]; arreglo[j + 1] = arreglo[j]; arreglo[j] = tmp; } } } for (int i = 0; i < arreglo.length; i++) { System.out.print(arreglo[i] + "\n"); } }}

Programa

BÚSQUEDA BINARIA

Algoritmo y programa para realizar una

"Búsqueda binaria"

De qué se trata la ‘‘Búsqueda Binaria’’

Se denomina así porque el algoritmo divide en dos el arreglo, aludiendo al concepto de bit, el cual puede tener dos estados.

La condición para usar este algoritmo es que los datos dentro del arreglo estén ordenados de menor a mayor.

Está recomendado para buscar en arreglos de gran tamaño

Sirve para buscar elementos en un arreglo ordenado.

En un arreglo ordenado de 1 048 576 elementos, la cantidad máxima de comparaciones será de 20. Mientras que en una búsqueda lineal se compararía los 1 048 576 elementos.

Ventaja: Es mucho más eficiente que la búsqueda

lineal.Requisito:

El arreglo debe estar ordenado

Algoritmo

inf = 0sup = tam–1 Mientras inf <= sup:centro = ((sup + inf) / 2) /* división entera: se trunca la parte decimal */Si vec[centro] == dato devolver verdadero y/o pos, de lo contrario:Si dato < vec[centro] entonces:sup=centro–1En caso contrario:inf=centro+1 Fin (Mientras)Devolver FalsoFIN

Programapublic class BusquedaBinaria {

public static int busquedaBinaria(int vector[], int dato) { int n = vector.length; int centro, inf = 0, sup = n - 1; while (inf <= sup) { centro = (sup + inf) / 2; if (vector[centro] == dato) { return centro; } else if (dato < vector[centro]) { sup = centro - 1; } else { inf = centro + 1; } } return -1; } public static void main(String[] args) { int[] vector = {1, 4, 7, 8, 9, 14, 23, 47, 56, 60, 61, 63, 65, 66, 68, 69, 70, 73, 76, 77, 79, 80, 82}; int valorBuscado = 60; System.out.println(busquedaBinaria(vector, valorBuscado)); }}

Búsqueda binariaEj: Buscar 0 (cero)

10

-3 -1 0 5 8 100 150

[3]

1

[6][0] [1]

2

[2]

3

GRACIAS