Ordenación y búsqueda.pdf

E.F.P. Ingeniera de Sistemas Laboratorio 9 y 10 IS 141 (Algoritmos)

Docente: Jennifer Pillaca De La cruz Pgina 1

ALGORITMOS DE ORDENACIN

1. Probar el siguiente cdigo que realiza la ordenacin de los datos de un arreglo mediante el mtodo burbuja y burbuja mejorada.

public class Burbuja { public static void main(String[] args) { int[]valores= {15,35,01,05,04,03,19,45,13,02,55,8,78,997,451,546,12,16,24,103,99,784, 4541,15};

ordenar(valores); //ordenarMejorado(valores);

for (int i = 0; i < valores.length ; i++) System.out.println ( "valores["+i+"]: "+ valores[i]);

} public static void ordenar( int [] arreglo) { int pasadas = 0; int comparaciones = 0; for (int i = 0; i < arreglo.length; i++) { ++pasadas; for (int j = 0; j < arreglo.length - 1; j++) {

++comparaciones; if (arreglo[j] > arreglo[j + 1]) {

intercambiar(arreglo, j, j+1); } } } estadisticas(pasadas, comparaciones); } public static void ordenarMejorado( int [] arreglo) { int pasadas = 0; int comparaciones = 0; boolean hayCambios = true; for (int i = 0; hayCambios ; i++) { ++pasadas; hayCambios = false; for (int j = 0; j < arreglo.length - 1; j++) {

++comparaciones; if (arreglo[j] > arreglo[j + 1]) { intercambiar(arreglo, j, j+1); hayCambios = true;

} } } estadisticas(pasadas, comparaciones); }



public static void intercambiar(int [] arreglo, int a, int b) { int tmp = arreglo[a]; arreglo[a] = arreglo[b]; arreglo[b] = tmp; }

public static void estadisticas( int pasadas, int comparaciones) { System.out.println( "Pasadas: " + pasadas ); System.out.println( "Comparaciones: " + comparaciones ); } }

2. Probar el siguiente cdigo que realiza la ordenacin de los datos de un arreglo mediante el mtodo seleccin e insercin.

public class Prueba { public static void main(String[] args) {

int [] valores = {15,35,01,05,04,03,19,45,13,02,55,8,78,997,451,546,12,16,24,103,99,784,4541,15};

for (int i = 0; i < valores.length ; i++) System.out.println ( "valores["+i+"]: "+ valores[i]);

System.out.println ( "ordenamiento por insercion");

insercion(valores); for (int i = 0; i < valores.length ; i++) System.out.println ( "valores["+i+"]: "+ valores[i]);

System.out.println ( "ordenamiento por seleccion"); int [] valor = {15,35,01,05,04,03,19,45,13,02,55,8,78,997,451,546,12,16,24,103,99,784,4541,15}; seleccion(valor); for (int i = 0; i < valor.length ; i++) System.out.println ( "valores["+i+"]: "+ valor[i]);

}



static void insercion(int A[]) { int j, i, llave; for(j=0; j=0&&A[i]>llave) { A[i+1]=A[i]; i=i-1; } A[i+1]=llave; } }

static void seleccion(int A[]) { int j, i, llave; for(i=0; ii; j--) if (A[j-1]>A[j]) { llave=A[j-1]; A[j-1]=A[j]; A[j]=llave; } } }

Ejercicio 1. En base a los ejercicios presentados, poner todos los mtodos en solo

programa y mediante un men de opciones realizar el ordenamiento de datos segn la opcin que se elija. Se debe ingresar el nmero de datos del arreglo y los datos se deben de llenar aleatoriamente.



MTODOS DE BSQUEDA

Con mucha frecuencia los programadores trabajan con grandes cantidades de datos almacenados en arreglos y registros, y por ello ser necesario determinar si un array contiene un valor que coincida con un cierto valor clave. El proceso de encontrar un elemento especfico de un array se denomina bsqueda.

A. BSQUEDA SECUENCIAL La bsqueda secuencial busca un elemento de una lista utilizando un valor clave. En una bsqueda secuencial (a veces llamado bsqueda lineal) los elementos se exploran en secuencia, uno despus de otro.

Algoritmo: 1. El algoritmo empieza con el primer elemento lista[0] o bien en una posicin

predeterminada (inicio) y 2. Recorre los restantes elementos de la lista, comparando cada elemento con la clave. 3. La exploracin continua hasta que se encuentra la llave o se termina la lista, si la

clave se encuentra devuelve el ndice del elemento encontrado en la lista, en caso contrario el valor es -1.

Ejemplo: Buscar si el elemento 6 y 2 estn en la lista{4,8,3,2,5,7}

B. BSQUEDA BINARIA Si est ordenado el arreglo, el nmero situado en la mitad para ver si es mayor o menor que el nmero buscado (o con suerte igual), sabremos si la bsqueda ha de proceder en el subarray con la mitad de tamao que est antes o despus de la mitad. Si se repite recursivamente el algoritmo al final o bien encontraremos el nmero sobre una arreglo de un slo elemento o estaremos seguros de que no se encuentra all.

Algortimo

Suponiendo que la lista esta almacena en una array ordenado donde los ndices de la lista son primero=0 y ultimo =tamao de la lista -1.

1. Calcular el ndice del punto central de la lista Central=(primero+ultimo)/2 (divisin entera

4 8 3 2 5 7Claves=6

A[0] A[1] A[5]

no existe el 6

4 8 3 2 5 7Claves=2

A[0] A[1] A[5]

Esta en ndice 3



2. Comparar el valor del ndice central con la clave

Si lista[central]



Ejemplo:

Buscar si el elemento 6 y 2 estn en la lista A={2,3,4,5,7,8}

CentralA[3] entonces se busca en la sub lista derecha

primero



clave



Ejemplo: buscar clave



Solucin Podemos implementar el algoritmo pedido apoyndonos en el hecho de que el vector est originalmente ordenado. Por tanto, podemos usar un mtodo basado en la idea de la bsqueda binaria, en donde examinamos el elemento en mitad del vector (su mediana). Si a[(n+1)2] = (n+1)2, sa es la posicin pedida. Si a[(n+1)2] fuera mayor que (n+1)2, la posicin pedida ha de encontrarse antes de la mitad, y en caso contrario detrs de ella

Pseudocodigo

Busqueda( lista, tamao,clave) primero



} static void leer(double b[], int m){ int i,j; Scanner Keyboard =new Scanner (System.in); System.out.println("Ingrese datos a matriz"); for(i=0;i



3. Realizar un programa busque un elemento mediante la bsqueda binaria.

public class B_Binaria { public static void main(String[] args) {

int n,i, e; double x []= new double[50]; double b; String resp="" ; Scanner valor =new Scanner (System.in); System.out.println("INGRESO DE LOS DATOS"); System.out.println("Cuantos datos va a ingresar?"); n=valor.nextInt(); leer (x, n); visualizar (x, n);

do { System.out.println("El dato a buscar?"); b=valor.nextDouble(); e=buscarbinario(x, n, b); if (e== -1) System.out.println("El dato no se encuentra en el arreglo"); else System.out.println("El dato se encuentra en el arreglo y en la posicin "+e);

System.out.println("Desea seguir buscando ?"); resp=valor.next();

}while (resp.equals("s"));//resp.equalsIgnoreCase } static int buscarbinario( double arreglo[], int m, double dato) { int inicio = 0; int fin = m - 1; int pos; while (inicio



}

Ejercicios

1. Realizar la bsqueda de elementos en matrices bidimensionales. 2. contar la cantidad de veces que aparece en una matriz un elemento buscado.

Ordenación y búsqueda.pdf

Documents

Transcript of Ordenación y búsqueda.pdf