MÉTODO DE BÚSQUEDA

La operación  de buscar un dato dentro de un conjunto dado es una de las operaciones más frecuentes dentro del proceso de datos. 

Clasificaremos los algoritmos de búsqueda en función de si e conjunto de datos sobre lo que se extiende la búsqueda está ordenado o no.(Isabel Gallego Férnandez y Manuel Medina Llinás)

Búsqueda Secuencial 

El método de búsqueda secuencial es el mas sencillo y se debe utilizar si el conjunto de datos sobre el que se extiende la búsqueda no está ordenado siguiendo criterio alguno. Como su nombre indica, consiste en recorrer el conjunto de datos uno a uno y comparar cada rato con el valor buscado hasta encontrarlo, si es que existe, o hasta el último dato sin éxito en la búsqueda, en el caso que no exista.(Isabel Gallego Férnandez y Manuel Medina Llinás)

Búsqueda Binaria

En el caso de buscar sobre un conjunto ordenado, es posible optimizar el criterio de búsquedas gracias a esa ordenación. Estos métodos de búsqueda son muy eficientes, sobre todo para grandes cantidades de datos ; es por esta razón que se suelen utilizar incluso sobre conjuntos de datos no ordenados, sometiéndolos a un proceso de ordenación previo a la búsqueda propiamente dicha. Uno  de estos métodos, el mas popular y sencillo de diseñar, es el método de búsqueda binaria o dicotómica, que estudiaremos en este apartado. 

La búsqueda binaria se basa en aprovechar el hecho de que se trata de datos ordenados para extender la búsqueda únicamente a aquella porción de los datos donde, si el dato existe es seguro que se encuentra.(Isabel Gallego Férnandez y Manuel Medina Llinás)  

CLASE BUSQUEDAS

package practica2;

public class busqueda {

    int max = 100;
    int vector[];
    int indice = 0;

    public void llenarVector(int tamanio) {
        indice=0;
       vector= new int[max];
        while (this.indice < tamanio) {
            vector[this.indice++] = (int) (Math.random() * 20);
        }

    }

    public void Mostrar() {
        for (int i = 0; i < this.getIndice(); i++) {
            System.out.println("Vector [" + i + "] = " + vector[i]);
        }
    }

    public void busquedaSecuencial(int numero) {
        int band = 0;
        for (int i = 0; i < this.getIndice(); i++) {
            if (numero == vector[i]) {
                System.out.println("el numero esta en la posicion [" + i + "]");
                band++;
            }
        }
        if (band == 0) {
            System.out.println("no existe el numero dentro del vector ");
        }
        System.out.println("band " + band);
    }

    public int busquedaBinaria(int numero) {
        int inicio = 0;
        int fin = this.getIndice() - 1;
        int posicion;
        while (inicio <= fin) {
            posicion = (inicio + fin) / 2;
            if (vector[posicion] == numero) {
                return posicion;
            } else if (vector[posicion] < numero) {
                inicio = posicion + 1;
            } else {
                fin = posicion - 1;
            }
        }
        return -1;

    }

    public int getIndice() {
        return indice;
    }

    public int[] getVector() {
        return vector;
    }

    public void Intercambiar(int vector[], int i, int j) {
        int aux;
        aux = vector[j];
        vector[j] = vector[i];
        vector[i] = aux;
    }

    public void ordenamientoSeleccion() {
        int i, j, posicion, menor;
        for (i = 0; i < this.getIndice(); i++) {
            menor = vector[i];
            posicion = i;
            for (j = i + 1; j < this.getIndice(); j++) {
                if (vector[j] < menor) {
                    menor = vector[j];
                    posicion = j;
                }
            }
            if (posicion != i) {
                Intercambiar(vector, i, posicion);
            }
        }
    }

}

CLASE MAIN

package practica2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        busqueda bus = new busqueda();
        System.out.println("Ingrese el tamanio del vector : ");

        bus.llenarVector(Integer.parseInt(br.readLine()));
        bus.Mostrar();
        bus.ordenamientoSeleccion();
        System.out.println("");
        bus.Mostrar();

        System.out.println("Ingrese el numero a buscar : ");
        String numeroo = br.readLine();
        int numero = Integer.parseInt(numeroo);

        System.out.println("-----busqueda de secuencial-----");
        bus.busquedaSecuencial(numero);

        System.out.println("-----busqueda binaria-----");
        int busquedaBinaria = bus.busquedaBinaria(numero);
        if (busquedaBinaria != -1) {
            System.out.println(" existe en la posicion : " + busquedaBinaria);
        } else {
            System.out.println("no se encuentra");
        }
    }
}

MÉTODO DE ORDENAMIENTOS

El problema de la ordenación de un conjunto de datos según un cierto criterio es uno de los más utilizados dentro del proceso de datos, y está ampliamente estudiado en la bibliografía.
Los métodos de ordenación externos se ocupan de estudiar la problemática especifica que comporta el hecho de tener los datos a ordenar almacenados en memoria auxiliar, como es el caso de los ficheros, sobre todo en el caso de ficheros secuenciales. (Isabel Gallego Férnandez y Manuel Medina Linas).

Existen tipos de ordenamiento entre ellos tenemos:
Ordenamiento Burbuja

Consiste en comparar pares de elementos adyacentes e intercambiarlos en el caso de que no estén bien situados según el criterio de ordenación utilizado. Para cada pasada del algoritmo conseguimos que el elemento menor, si la ordenación es creciente, suba como una burbuja hasta su lugar definitivo, pasando de esta forma a engrosar en un elemento el subconjunto ordenado. El método prosigue hasta que el subconjunto desordenado no consta de ningún elemento. (Isabel Gallego Férnandez y Manuel Medina LLinás).

Ordenamiento Inserción

Consiste en dividir el conjunto de datos a ordenar en dos subconjuntos que corresponden, respectivamente, al subconjunto de datos ya ordenados y el subconjunto que contiene los datos pendientes de ordenar. Cada paso del algoritmo consiste en incrementar en un elemento el subconjunto ordenado y decrementar el desordenado, hasta que todos los elementos pertenezcan al subconjunto ordenado y el subconjunto desordenado esté vacío (Isabel Gallego Férnandez y Manuel Medina Llinás).

Ordenamiento Selección

Consiste también en dividir el conjunto de datos a ordenar en dos subconjuntos, el ordenado y el que todavía está desordenado. En cada pasada, el algoritmo selecciona el elemento que cumple el criterio de ordenación(creciente o decreciente) del subconjunto desordenado y lo coloca en el subconjunto ordenado. El algoritmo prosigue hasta que el subconjunto desordenado no consta de ningún elemento.(Isabel Gallego Férnandez y Manuel Medina Llinás).

Ordenamiento QuickSort

Es también un método de ordenación basado en el intercambio, pero en este caso los intercambios no se realizan entre elementos adyacentes, sino distanciados lo más posible.El método Quicksort está basado en la idea de partir el vector en dos particiones delimitadas por un elemento "central" tales que, al final del tratamiento de una partición, la partición izquierda contenga solo elementos menores Al "central" y la derecha mayores al "central". El método consiste en realizar particiones de las particiones hasta que consten de un solo elemento (Isabel Gallego Férnandez y Manuel Medina Llinás).

Ordenamiento Shell

Consiste en ordenar el vector mediante la ordenación de subvectores. Cada subvector se construye mediante aquellos elementos que distan entre sí una constante, empezando por los mas distantes hasta llegar al vector compuesto por los elementos que distan una posición, es decir, todo el vector. Por esta razón, al método se Shell se le denomina también método de inserción con incrementos decrecientes. (Isabel Gallego Férnandez y Manuel Medina Llinás).

   

CLASE ORDENAMIENTOS

package practica1;
import java.util.Random;
public class ordenamiento {

    int max = 100;
    int vector[] = new int[max];

    public void generar(int tamanio) {
        for (int i = 0; i < tamanio; i++) {
            Random rd = new Random();
            vector[i] = rd.nextInt(20);
        }
    }

    public void mostrar(int tamanio) {
        for (int i = 0; i < tamanio; i++) {
            System.out.println("Vector [" + i + "] = " + vector[i]);
        }
    }

    public void Intercambiar(int vector[], int i, int j) {
        int aux;
        aux = vector[j];
        vector[j] = vector[i];
        vector[i] = aux;
    }

    public void ordenamientoBurbuja(int tamanio) {
        for (int i = 0; i < tamanio; i++) {
            for (int j = 0; j < 10; j++) {
                Intercambiar(vector, i, j);
            }
        }
    }

    public void ordenamientoInsercion(int tamanio) {

        int aux, i, j;
        for (i = 0; i < tamanio; i++) {
            j = i;
            aux = vector[i];
            while (j > 0 && aux < vector[j - 1]) {
                vector[j] = vector[j - 1];
                j--;
            }
            vector[j] = aux;
            System.out.println(vector[j]);
            for (int k = 0; k < tamanio; k++) {
                System.out.print(" "+vector[k]);
                        
            }
            System.out.println(" i "+i);
            
        }
    }

    public void ordenamientoShell(int tamanio) {
        int j, l, aux;
        int k;
        k = ( tamanio / 2);
        while (k > 0) {
            for (int i = k; i < tamanio; i++) {
                j = i - k;
                while (j >= 0) {
                    l = j + k;
                    if (vector[j] <= vector[i]) {
                        j--;
                    } else {
                        aux = vector[j];
                        vector[j] = vector[i];
                        vector[i] = aux;
                    }
                }
            }
            k = k / 2;
        }

    }

    public void ordenamientoQuicksort(int vector[], int primero, int ultimo) {

        int aux;
        int i = primero;
        int j = ultimo;
        int pivote = vector[(primero + ultimo) / 2];
        while (i <= j) {
            while (vector[i] < pivote) {
                i++;
            }
            while (vector[j] > pivote) {
                j--;
            }
            if (i <= j) {
                aux = vector[i];
                vector[i] = vector[j];
                vector[j] = aux;
                i++;
                j--;
            }

        }
        if (primero < j) {
            ordenamientoQuicksort(vector, primero, j);
        }
        if (i < ultimo) {
            ordenamientoQuicksort(vector, i, ultimo);
        }

    }

    public void ordenamientoSeleccion(int tamanio) {
        int i, j, posicion, menor;
        for (i = 0; i < tamanio; i++) {
            menor = vector[i];
            posicion = i;
            for (j = i + 1; j < tamanio; j++) {
                if (vector[j] < menor) {
                    menor = vector[j];
                    posicion = j;
                }
            }
            if (posicion != i) {
                Intercambiar(vector, i, posicion);
            }
        }
    }

}

CLASE MAIN

package practica1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Vector;

/**
 *
 * @author luz
 */
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Ingrese el tamanio del vector : ");
        String tamanioo = br.readLine();
        int tamanio = Integer.parseInt(tamanioo);

        ordenamiento o = new ordenamiento();
        o.generar(tamanio);
        o.mostrar(tamanio);

        System.out.println("-----Ordenamiento de burbuja----- ");
        o.ordenamientoBurbuja(tamanio);
        o.mostrar(tamanio);

        System.out.println("-----Ordenamiento de insercion-----");
        o.ordenamientoInsercion(tamanio);
        o.mostrar(tamanio);

        System.out.println("-----ordenamiento de shell-----");
        o.ordenamientoShell(tamanio);
        o.mostrar(tamanio);

        System.out.println("-----ordenamiento de quicksort-----");
        o.ordenamientoQuicksort(o.vector, 0, tamanio-1);
        o.mostrar(tamanio);

        System.out.println("-----ordenamiento de seleccion-----");
        o.ordenamientoSeleccion(tamanio);
        o.mostrar(tamanio);

    }
}

PILAS

DEFINICIÓN DE PILAS:

Una pila es una estructura de datos de acceso restrictivo a sus elementos. 

Las operaciones que caracterizan la pila son las de introducir un nuevo elemento sobre la cima (PUSH) y la de extraer el elemento situado en la cima (POP).

Se puede entender como una pila de libros que se amontonan de abajo hacia arriba.

En principio no hay libros; después ponemos uno, y otro encima de éste, y así sucesivamente. Posteriormente los solemos retirar empezando desde la cima dela pila de libros, es decir, desde el último que pusimos, y terminaríamos por retirar el primero que pusimos, posiblemente ya cubierto de polvo.

Es una estructura de tipo LIFO (Last In First Out), es decir, último en entrar, primero en salir.