MAPA CONCEPTUAL SOBRE ARREGLOS

MÉTODOS DE ORDENAMIENTO

Para poder ordenar una cantidad determinada de números almacenadas en un vector o matriz, existen distintos métodos (algoritmos) con distintas características y complejidad. Existe desde el método más simple, como el Bubblesort (o Método Burbuja), que son Simples iteraciones, hasta el Quicksort (Método Rápido), que al estar optimizado usando recursión, su tiempo de ejecución es menor y es más efectivo. 

Bubble Sort (Ordenamiento Burbuja)

Es el algoritmo de ordenamiento más sencillo de todos, conocido también como método del intercambio directo, el funcionamiento se basa en la revisión de cada elemento de la lista que va a ser ordenada con el elemento siguiente, intercambiando sus posiciones si están en el orden equivocado, para esto se requieren varias revisiones hasta que ya no se necesiten más intercambios, lo que indica que la lista ha sido ordenada.

El origen del nombre de este algoritmo proviene de la forma con la que suben por la lista los elementos durante los intercambios, tal y como si fueran "burbujas", el algoritmo fundamental de este método es la simple comparación de elementos siendo así el más fácil de implementar.

A continuación el algoritmo del método de ordenamiento burbuja

public class ORDENAMIENTO_BURBUJA {

    public static void main(String[] args) {
        int[] vector = {15, 8, 3, 4, 12, 1};
        int temp;

        for (int i = 0; i < vector.length; i++) {
            for (int j = i + 1; j < vector.length; j++) {
                if (vector[i] > vector[j]) {
                    temp = vector[i];
                    vector[i] = vector[j];
                    vector[j] = temp;
                }
            }
        }
        for (int k = 0; k < vector.length; k++) {
            System.out.println(vector[k]);
        }
    }
}

Quick Sort (Ordenamiento Rápido): 

Es el algoritmo de ordenamiento más eficiente de todos, se basa en la técnica de "Divide y Vencerás", que permite en promedio, ordenar n elementos en un tiempo proporcional a n*log(n). 

Algoritmo Fundamental: 

• Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote. 
• Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
•  La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha. 
• Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

A continuación el algoritmo del método de ordenamiento QuickSort

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

public class ordenamiento_quicksort {

    static BufferedReader entrada = new BufferedReader(new InputStreamReader(
            System.in));

    public static void main(String[] args) throws IOException {

        int n;
        int[] v;
        System.out.print("Ingrese el numero de elementos: ");
        n = Integer.parseInt(entrada.readLine());
        v = new int[n];
        entradaArreglo(v, n);
        System.out.println("\n\tLista original de " + n + " elementos");
        imprimirArreglo(v, n);
        ordenarecursivo(v, n);
        System.out.println("\n\tLista ordenada de " + n + " elementos");
        imprimirArreglo(v, n);

    }

    static void ordenarecursivo(int a[], int n) {
        ordenareducer(a, 0, n - 1);
    }

    static void ordenareducer(int a[], int INI, int FIN) {
        int IZQ, DER, POS, AUX;
        boolean BAND;
        IZQ = INI;
        DER = FIN;
        POS = INI;
        BAND = true;
        while (BAND) {
            BAND = false;
            while (a[POS] <= a[DER] && (POS != DER)) {
                DER = DER - 1;
            }
            if (POS != DER) {
                AUX = a[POS];
                a[POS] = a[DER];
                a[DER] = AUX;
                POS = DER;
                while (a[POS] >= a[IZQ] && (POS != IZQ)) {
                    IZQ = IZQ + 1;
                }
                if (POS != IZQ) {
                    BAND = true;
                    AUX = a[POS];
                    a[POS] = a[IZQ];
                    a[IZQ] = AUX;
                    POS = IZQ;
                }
            }

        }
        if ((POS - 1) > INI) {
            ordenareducer(a, INI, POS - 1);
        }
        if (FIN > (POS + 1)) {
            ordenareducer(a, POS + 1, FIN);
        }
    }

    static void imprimirArreglo(int a[], int n) {
        for (int i = 0; i < n; i++) {
            String c;
            c = (i % 10 == 0) ? "\n" : " ";
            System.out.print(c + a[i]);
        }
    }

    static void entradaArreglo(int a[], int n) throws IOException {
        System.out.println("\n Entrada de los elementos");
        for (int i = 0; i < n; i++) {
            System.out.print("a[" + i + "]= ");
            a[i] = Integer.parseInt(entrada.readLine());
        }
    }

}

MÉTODOS DE BUSQUEDA

La búsqueda es una operación que tiene por objeto la localización de un elemento dentro de la estructura de datos. A menudo un programador estará trabajando con grandes cantidades de datos almacenados en arreglos y pudiera resultar necesario determinar si un arreglo contiene un valor que coincide con algún valor clave o buscado. 

Encontramos dos métodos que localizan elementos dentro de un array: Búsqueda secuencial y búsqueda binaria. 

Búsqueda Secuencial 
Se utiliza cuando el vector no está ordenado o no puede ser ordenado previamente. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del vector hasta encontrarlo o hasta que se llegue al final,recorre el vector desde el primer elemento hasta el último.La existencia se puede asegurar cuando el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del vector. 
 A continuación se presentara el código de el método de búsqueda secuencial 

 Creamos nuestra clase busqueda_secuencial

public class busqueda_secuencial {

    static void buscar(int[] a, int num) {
        int band = 0;
        for (int i = 0; i < a.length; i++) {
            if (num == a[i]) {
                System.out.println("el numero esta en la posicion [" + (i) + "]");
                band++;
            }
        }
        if (band == 0) {
            System.out.println("no existe");
        }
        System.out.println("band= " + band);
    }

    public static void seleccion(int a[]) {
        int aux, i;
        for (i = 0; i < a.length; i++) {
            for (int k = i + 1; k < a.length; k++) {
                if (a[i] > a[k]) {
                    aux = a[i];
                    a[i] = a[k];
                    a[k] = aux;
                }
            }
            for (int k = 0; k < a.length; k++) {
                System.out.print(a[k] + " ");
            }
            System.out.print(" i=" + i);
            System.out.println("");
        }
    }
}

Creamos nuestra clase principal test_busquedaSecuencial

import java.util.Scanner;

public class test_busquedaSecuencial {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        busqueda_secuencial b = new busqueda_secuencial();
        int a[] = {9, 5, 4, 1, 4};
        int num;
        System.out.println("Vector");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println("\ningrese numero  buscar: ");
        num = sc.nextInt();

        b.buscar(a, num);
    }

}

Búsqueda Binaria
Se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado.
Este método consiste en una vez que tengamos el numero para buscar,trabajamos con el indice inicial y final del array,se ase una semisuma y al indice que le toca ese valor se convierte en el indice intermedio y se le pregunta si es mayor,menor o igual al numero buscado;si el numero buscado es el indice intermedio pues el elemento a sido encontrado,en caso contrario si el indice intermedio es menor pues pasa a ser el indice final ,y si el indice intermedio es mayor pues pasa a ser el indice inicial,y así sucesivamente hasta encontrar el elemento buscado.

A continuación se presentara el código de el método de búsqueda secuencial 

Creamos nuestra clase busqueda_binaria

public class busqueda_binaria {

     void mostrarArreglo(int vector[]) {
          for(int i =0; i vector[i]) {
                    temp = vector[j];
                    vector[j] = vector[i];
                    vector[i] = temp;
                }
            }
        }
    }

    public void busquedbinaria(int Vector[], int num) {
        int tam = Vector.length;
        int min = 0, med = 0, max = tam;
        while (min <= max) {
            med = (min + max) / 2;
            if (num == Vector[med]) {
                System.out.println("su numero es " + num + "  en la posicion  " + med);
                max=0;           
            }
            if (num < Vector[med]) {
                max = med;
            } else {
                min = med;
            }
        }
    }

Creamos nuestra clase principal test_busquedaBinaria

import java.util.Scanner;

public class test_busqueaBinaria {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        busqueda_binaria  a= new busqueda_binaria ();
        int Vector []= {3,1,6,7,5,8};
        int num;  
      a.mostrarArreglo(Vector);
      a.ordenarArreglo(Vector);
        System.out.println("------vector ordenado");
      a.mostrarArreglo(Vector);
        System.out.println("------ingresar numero a buscar");
        num=sc.nextInt();
      a.busquedbinaria(Vector, num);   
    }
}

PILAS Y COLAS

Pila 

Es una estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO(ultimo en entrar,primero en salir).

Operaciones de la Pila 

Las operaciones que se pueden realizar con una pila son: 

• Push(pila,elemento)Introduce un elemento a la pila,también se le conoce como poner o meter.
• Pop(pila)Elimina un elemento de la pila,también se le conoce como sacar o quitar.
• Vaciar,función booleana que indica si la pila esta vacía o no.

Cola 

Es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (primero en entrar,primero en salir). 

Operaciones de la cola 

Las operaciones que se pueden realizar en una cola son: 

• Encolar(añadir,entrar,insertar)Se añade un elemento a la cola,se añade al final de esta.
• Desencolar(sacar,salir,eliminar)Se elimina el elemento frontal de la cola es decir el primer elemento que entro.

Comparación entre Pilas y Colas 
 Pilas:

•  En las Pilas se puede acceder a los elementos de la lista solo a través de la cima de la misma.
• Se puede acceder a los elementos de la Pila solo a través del sistema LIFO. 
• Se considera como una estructura de datos Las In Fist Out.
•  Solo se puede agregar elementos a la parte superior de la Pila. 

Colas: 

• Se pude acceder a los elementos de la lista desde cualquier extremo de la misma, ya sea desde el comienzo o desde el final.
•  Los elementos se eliminan de la Cola en el orden de llegada. 
• Se considera como una estructura First In First Out. 
• En las bi-colas se pueden agregar elementos desde ambos extremos de la lista, ya sea desde el comienzo o desde el final.

 Ejemplo:

A continuación se mostrara un algoritmo sobre pilas y colas Primero se crea una clase nodo para la pila

public class Nodo {
    //Datos que se guardara en el Nodo
    private Object valor;
    //Referencia al nodo siguiente
    private Nodo siguiente;
    
    //Constructor. Recibe el dato a guardar y el nodo siguiente
    public Nodo(Object val,Nodo sig){
        this.valor = val;
        this.siguiente = sig;
    }
    
    //Getters y Setters para tomar y cambiar valores.
    public Object getValor() {
        return valor;
    }

    public void setValor(int valor) {
        this.valor = valor;
    }

    public Nodo getSiguiente() {
        return siguiente;
    }

    public void setSiguiente(Nodo siguiente) {
        this.siguiente = siguiente;
    }
}

Ahora creamos nuestra clase arreglo

public class Arreglo {
    //Creamos dos Nodos, que seran el primero y el ultimo nodo de nuestro arreglo
    private Nodo primero,ultimo;
    private int tamaño;
    
    //Constructor. Inicializacion de las variables
    public Arreglo(){
        ultimo = primero = null;
        tamaño = 0;
    }
    
    //Funcion que inserta un dato al principio del arreglo, recibe como parametro el dato a insertar
    public void insertarPrimero(Object valor){
        if(tamaño == 0){
            primero = new Nodo(valor,null);
            ultimo = primero;
            tamaño++;
        }
        else{
            Nodo temporal = primero;
            primero = new Nodo(valor,temporal);
            tamaño++;
        }
    }
    
    //Funcion que inserta un dato al final del arreglo recibe como parametro el dato a insertar
    public void insertarUltimo(Object valor){
        if(tamaño == 0){
            primero = new Nodo(valor,null);
            ultimo = primero;
            tamaño++;
        }
        else{
            Nodo temporal = ultimo;
            ultimo = new Nodo(valor, null);
            temporal.setSiguiente(ultimo);
            tamaño++;
        }
    }
    
    //Funcion que elimina el primer nodo del arreglo
    public void eliminarPrimero(){
        if(tamaño == 0)return;
        Nodo temporal = primero;
        temporal = primero.getSiguiente();
        primero = null;
        primero = temporal;
        tamaño--;
    }
    
    //Funcion que elimmina el ultimo nodo del arreglo
    public void eliminarUltimo(){
        if(tamaño == 0)return;
        if(tamaño == 1){
            ultimo = primero = null;
            tamaño = 0;
            return;
        }
        Nodo temporal = primero;
        while(temporal.getSiguiente() != ultimo){
            temporal = temporal.getSiguiente();
        }
        temporal.setSiguiente(null);
        ultimo = temporal;
        tamaño--;
    }
    
    
    public int getTamaño(){
        return tamaño;
    }
    

    public Object[] getElementos(){
        if(tamaño == 0)return new Object[0];
        Object[] elementos = new Object[tamaño];
        int i = 0;
        Nodo temporal = primero;
        while(temporal != null){
            System.out.print(temporal.getValor().toString()+"  ");
            elementos[i++] = temporal.getValor();
            temporal = temporal.getSiguiente();
        }
        System.out.println("");
        return elementos;
    }
    
    public static void main(String[] args) {
        Arreglo lista = new Arreglo();
        lista.insertarPrimero(1);
    }
    
}

Creamos nuestra clase pila

public class Pila {
    //Declaramos una variable tipo Arreglo
    private Arreglo pila;
    
    //Contructor. Inicializacion del arreglo
    public Pila(){
        pila = new Arreglo();
    }
    
    //Funcion que inserta un elemento a la pila
    public void push(Object dato){
        pila.insertarPrimero(dato);
    }
    
    //Funcion que elimina un elemento de la pila
    public Object pop(){
        Object Dato = pila.getElementos()[0];
        pila.eliminarPrimero();
        return Dato;
    }
    
    //Funcion que devuelve el tope de la pila
    public Object peek(){
        return pila.getElementos()[0];
    }
    
    //Funcion que devueleve el tamaño de la pila
    public int size(){
        return pila.getTamaño();
    }
    
    //Funcion que devuelve los elementos de la pila
    public Object[] getElementos(){
        return pila.getElementos();
    }
}

Creamos nuestra clase cola

public class Cola {
    private Arreglo cola;
    
    public Cola(){
        cola = new Arreglo();
    }
    
    public void encolar(Object dato){
        cola.insertarUltimo(dato);
    }
    
    public Object desencolar(){
        Object dato = cola.getElementos()[0];
        cola.eliminarPrimero();
        return dato;
    }
    
    public Object frente(){
        return cola.getElementos()[0];
    }
    
    public int size(){
        return cola.getTamaño();
    }
    
    public Object[] getElementos(){
        return cola.getElementos();
    }
    
}