UNIDAD IV

Método de la Burbuja 

El método de intercambio directo, conocido coloquialmente con el nombre de la burbuja, es el mas utilizado entre los estudiantes principiantes de computación;.
La idea básica de este algoritmo consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados.

Se realizan (n-1) pasadas, transportando en cada de las mismas el menor o mayor elemento (según sea el caso) a su posición ideal. 

Ejemplo:
Se desean ordenarse las siguientes clave del arreglo 
A: 15, 67, 08, 16, 44, 27, 12, 35

Primera pasada
A[7] > A[8] 12>35 No hay intercambio 
A[6] > A[7] 27>12 Si hay intercambio
A[5] > A[6] 44>12 Si hay intercambio
A[4] > A[5] 16>12 Si hay intercambio
A[3] > A[4] 08>12 No hay intercambio
A[2] > A[3] 67>08 Si hay intercambio
A[1] > A[2] 15>08 Si hay intercambio 

Luego de la primera pasada el arreglo queda de la siguiente forma:
A: 08, 15, 67, 12, 16, 44, 27, 35

Luego de la segunda pasada el arreglo queda de la siguiente forma:
A:= 08, 12, 15, 67, 16, 27, 44, 35


Hasta la séptima pasada el arreglo queda ordenado: 08, 12, 15, 16, 27, 35, 44, 67.

public static void burbuja(int [] A){
         int i, j, aux;
         for(i=0;i<A.length-1;i++)
              for(j=0;j<A.length-i-1;j++)
                   if(A[j+1]<A[j]){
                      aux=A[j+1];
                      A[j+1]=A[j];
                      A[j]=aux;
                   }
}

MÉTODO RADIX

Es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, Radix sort no está limitado sólo a los enteros.

Existen dos clasificados del método de Radix:

LSD ---->>>dígito menos significativo
MSD --->>>dígito más significativo
Radix sort LSD procesa las representaciones de enteros empezando por el dígito menos significativo y moviéndose hacia el dígito más significativo.

Radix sort MSD trabaja en sentido contrario.

Este ordenamiento se basa en los valores de los dígitos reales en las representaciones de posiciones de los números que se ordenan.


import java.lang.*;
import java.io.*;

public class RadixSort{

    public static void radixSort(int[] arr){
        if(arr.length == 0)
            return;
        int[][] np = new int[arr.length][2];
        int[] q = new int[0x100];
        int i,j,k,l,f = 0;
        for(k=0;k<4;k++){
            for(i=0;i<(np.length-1);i++)
                np[i][1] = i+1;
            np[i][1] = -1;
            for(i=0;i<q.length;i++)
                q[i] = -1;
            for(f=i=0;i<arr.length;i++){
                j = ((0xFF<<(k<<3))&arr[i])>>(k<<3);
                if(q[j] == -1)
                    l = q[j] = f;
                else{
                    l = q[j];
                    while(np[l][1] != -1)
                        l = np[l][1];
                    np[l][1] = f;
                    l = np[l][1];
                }
                f = np[f][1];
                np[l][0] = arr[i];
                np[l][1] = -1;
            }
            for(l=q[i=j=0];i<0x100;i++)
                for(l=q[i];l!=-1;l=np[l][1])
                        arr[j++] = np[l][0];
        }
    }

    public static void main(String[] args){
        int i;
        int[] arr = new int[15];
        System.out.print("original: ");
        for(i=0;i<arr.length;i++){
            arr[i] = (int)(Math.random() * 1024);
            System.out.print(arr[i] + " ");
        }
        radixSort(arr);
        System.out.print("\nsorted: ");
        for(i=0;i<arr.length;i++)
            System.out.print(arr[i] + " ");
        System.out.println("\nDone ;-)");
    }

}

MÉTODO QUICK SORT 

 El ordenamiento por partición (Quick Sort) se puede definir en una forma más conveniente como un procedimiento recursivo.

Tiene aparentemente la propiedad de trabajar mejor para elementos de entrada desordenados completamente, que para elementos semiordenados. Esta situación es precisamente la opuesta al ordenamiento de burbuja.

Este tipo de algoritmos se basa en la técnica "divide y vencerás", o sea es más rápido y fácil ordenar dos arreglos o listas de datos pequeños , que un arreglo o lista grande.

Normalmente al inicio de la ordenación se escoge un elemento aproximadamente en la mitad del arreglo, así al empezar a ordenar, se debe llegar a que el arreglo este ordenado respecto al punto de división o la mitad del arreglo.

Se podrá garantizar que los elementos a la izquierda de la mitad son los menores y los elementos a la derecha son los mayores.

Los siguientes pasos son llamados recursivos con el propósito de efectuar la ordenación por partición al arreglo izquierdo y al arreglo derecho, que se obtienen de la primera fase. El tamaño de esos arreglos en promedio se reduce a la mitad.

Así se continúa hasta que el tamaño de los arreglos a ordenar es 1, es decir, todos los elementos  ya están ordenados.

En promedio para todos los elementos de entrada de tamaño n, el método hace O(n log n) comparaciones, el cual es relativamente eficiente.

public static void quicksort(int A[], int izq, int der) {

  int pivote=A[izq]; // tomamos primer elemento como pivote

  int i=izq; // i realiza la búsqueda de izquierda a derecha

  int j=der; // j realiza la búsqueda de derecha a izquierda

  int aux;

  while(i<j){            // mientras no se crucen las búsquedas

     while(A[i]<=pivote && i<j) i++; // busca elemento mayor que pivote

     while(A[j]>pivote) j--;         // busca elemento menor que pivote

     if (i<j) {                      // si no se han cruzado                      

         aux= A[i];                  // los intercambia

         A[i]=A[j];

         A[j]=aux;

     }

   }

   A[izq]=A[j]; // se coloca el pivote en su lugar de forma que tendremos

   A[j]=pivote; // los menores a su izquierda y los mayores a su derecha

   if(izq<j-1)

      quicksort(A,izq,j-1); // ordenamos subarray izquierdo

   if(j+1 <der)

      quicksort(A,j+1,der); // ordenamos subarray derecho

}

MÉTODO DE BÚSQUEDA 

La recuperación de información es una de las aplicaciones más importantes de las computadoras. La búsqueda de información está relacionada con las tablas para consultas. Estas tablas contienen una cantidad de información que se almacenan en forma de listas de parejas de datos. Por ejemplo un catálogo con una lista de libros de matemáticas, en donde es necesario buscar con frecuencia elementos en una lista. Existen diferentes tipos de búsqueda, pero en este informe describiremos sólo la de tipo Secuencial y Binaria.  

Método de Búsqueda Secuencial:

Este método se usa para buscar un elemento de un vector, es explorar secuencialmente el vector, es decir; recorrer el vector desde el prior elemento hasta el último. Si se encuentra el elemento buscado se debe visualizar un mensaje similar a “Fin de Búsqueda” o “Elemento encontrado” y otro que diga “posición=” en caso contrario, visualizar un mensaje similar a “Elemento no existe en la Lista”.

Este tipo de búsqueda compara cada elemento del vector con el valor a encontrar hasta que este se consiga o se termine de leer el vector completo.

 public class secuencialdesordenado {

    public void buscar()

    {

        Scanner leer=new Scanner(System.in);

    int i=0;

    boolean bandera=false;

    int x;

    int v[]= new int[10];

    for(int c=0;c<v.length;c++)

    {

        System.out.println("introduce los datos del arreglo");

        v[c]=leer.nextInt();

    }

        System.out.println("introduzca elemento a buscar");

        x=leer.nextInt();

     do{

       if(v[i]==x)

        {

            bandera=true;

        }

        else {

            bandera=false;

        }

       i++;

    }while(i<v.length && bandera==false);

        

    if(bandera==true)

    {

        System.out.println("el elemento esta en la posicion "+ i);

    }

    else if(bandera==false)

    {

        System.out.println("el elemento no esta en la lista");

    }

    }

Método de Búsqueda Binaria:

Es un método que se basa en la división sucesiva del espacio ocupado por el vector en sucesivas mitades, hasta encontrar el elemento buscado.

Esta búsqueda utiliza un método de “divide y vencerás” para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si este es el elemento buscado entonces la búsqueda ha terminado. En caso contrario se determina si el elemento buscado está en la primera o segunda mitad de la lista y a continuación se repite el proceso anterior, utilizando el elemento central de esta sublista. Este tipo de búsqueda se utiliza en vectores ordenados.

package busqueda;

/**
 *
 * @author Ivan Leiva
 */
    class BusquedaAlgoritmo {
    public static int buscar( int [] arreglo, int dato) {
    int inicio = 0;
    int fin = arreglo.length - 1;
    int pos;
    while (inicio <= fin) {
        pos = (inicio+fin) / 2;
        if ( arreglo[pos] == dato )
            return pos;
        else if ( arreglo[pos] < dato ) {
            inicio = pos+1;
        }
        else {
    fin = pos-1;
        }
    }
 return -1;
    }
}

public class Busqueda {
    public static void  main (String args[]) {
 // Llenar arreglo
 int [] edades = new int [35];
 for (int i = 0; i < edades.length ; i++)
     edades[i] = i*i ;

 // Mostrar arreglo.
 for (int i = 0; i < edades.length ; i++)
     System.out.println ( "edades["+i+"]: "+  edades[i]);

 int resultado = BusquedaAlgoritmo.buscar(edades, 100);

 if (resultado != -1) {
     System.out.println ( "Encontrado en: " +  resultado+ " valor 100");
 } else {
     System.out.println ( "El dato no se encuentra en el arreglo, o el arreglo no está ordenado."  );
 }

    }
}

UNIDAD I Y UNIDAD II

CONCEPTOS BÁSICOS 

Estructura de datos: Es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema.

Una estructura de datos define la organización e interrelación de estos y un conjunto de operaciones que se pueden realizar sobre ellos. Las operaciones básicas son:
Alta, adicionar un nuevo valor a la estructura.
Baja, borrar un valor de la estructura.
Búsqueda, encontrar un determinado valor en la estructura para realizar una operación con este valor, en forma secuencial o binario (siempre y cuando los datos estén ordenados).

Datos primitivos:Tipos de datos originales de un lenguaje de programación, esto es, aquellos que nos proporciona el lenguaje y con los que podemos (en ocasiones) construir tipos de datos abstractos y estructuras de datos.
Generalmente ejemplos de tipos primitivos son:
char (carácter)
int (entero)
float (real (coma flotante)).

Datos Compuestos: Son conjunto de partidas de datos simples con relaciones definidas entre ellos estructurados.
Arreglos 
Registros 
Archivos 

Abstracción de datos:Técnica que permite diseñar estructuras de datos que consiste en representar las características esenciales de una estructura de datos, olvidándose de los detalles específicos de implementación de los datos, escondiendo la complejidad a los usuarios para simplificar su interacción con el sistema.

UNIDAD II 

Estructuras de datos lineales y no lineales 

Estructura de datos lineales:Se caracterizan porque sus elementos están en secuencia, relacionados en forma lineal, uno luego del otro. Cada elemento de la estructura puede estar conformado por uno o varios sub-elementos o campos que pueden pertenecer a cualquier tipo de dato, pero que normalmente son tipos básicos.

Una estructura lineal de datos os lista esta conformada por ninguno, uno o varios elementos que tienen una relación dónde existe un primer elemento, seguido de un segundo elemento y así sucesivamente hasta llegar al último.
El valor contenido en los elementos pueden ser el mismo o diferente. En estas estructuras se realizan operaciones de agregar y/o eliminar elementos a la lista según un criterio particular.


Se clasifican en listas de acceso restringido y listas de acceso no restringido.
las listas de acceso restringido son las pilas, colas y dipolos.

Pilas: En las pilas, las operaciones de acceso se realizan por un unico extremo de la lista, al cual normalmente se denomina tope de la pila. Las operaciones básicas sobre una pila son: crearlo, destruirla, agregar un nuevo elemento, suprimir un elemento, consultar el elemento del tope verificar si esta vacía

Colas: En las colas, estas operaciones de acceso se realizan por ambos extremos de la lista llamados gralmente, inicio y fin de la cola. Operaciones básicas son: creación, destrucción, inserción al final de un nuevo elemento, consultar que elemento esta al inicio y cual al final, y verificar si la cola está vacía.

Lista:La lista es el tipo más general de estructura lineal donde las inserciones y eliminaciones se hacen en cualquier punto de la lista, por ello se debe especificar donde se requiere que se haga la operación.
Sus operaciones
básicas son: creación, destrucción, inserción, eliminación, consulta y verificación de lista vacía.

CÓDIGO DE  UNA PILApublic class PilaArray 
{
  
 private int vector[];
 private int cima, tamano;


  public PilaArray( int tamano_p)//tamano de la pila parametro constructor
  {
    if( tamano_p < 0)
    {    
      tamano = 0;  
      System.err.println("Error, tamano no valido");
    }//fin if
    else
    {
        
       vector = new int[ tamano_p ];
       tamano = tamano_p;
       cima = -1;
    }//fin else    
    
    
      
  }
    
//para saber si la pila esta vacia 
  public boolean vacia()
  {
   if(cima == -1)
       return true;
   
   return false;
  }
    
  
  //Devuelva true si logra insertar elemento
  public boolean inserta(int valor)
  {
    //si ya no hay espacio...  
    if( cima == tamano-1 )
    {
      System.err.println("OverFloat");
      return false;
    }    
    else
    {
      vector [ ++cima ] = valor;
      System.out.println("Agregado correctamente");
      return true;
    }    
  }
  
  //devuelve el valor de la cima de la pila
  public int cima()
  {
    //si la pila esta vacia...  
    if( vacia() )  
    { 
       System.err.println("La pila esta vacia"); 
       //si la pila esta vacia se retorna un 0 ... solo por ejemplo
       
       return 0;
    }  
    else
    {
      return vector[ cima-- ];  
    }    
  }
  
  //limpia la pila
  public void vaciar()
  {
     cima = -1; 
  }
  
  

}//fin clase pila


CÓDIGO DE UNA COLA

public class Cola {
    
    class Nodo {
        int info;
        Nodo sig;
    }
    
    private Nodo raiz,fondo;
    
    Cola() {
        raiz=null;
        fondo=null;
    }
    
    boolean vacia (){
        if (raiz == null)
            return true;
        else
            return false;
    }

    void insertar (int info)
    {
        Nodo nuevo;
        nuevo = new Nodo ();
        nuevo.info = info;
        nuevo.sig = null;
        if (vacia ()) {
            raiz = nuevo;
            fondo = nuevo;
        } else {
            fondo.sig = nuevo;
            fondo = nuevo;
        }
    }

    int extraer ()
    {
        if (!vacia ())
        {
            int informacion = raiz.info;
            if (raiz == fondo){
                raiz = null;
                fondo = null;
            } else {
                raiz = raiz.sig;
            }
            return informacion;
        } else
            return Integer.MAX_VALUE;
    }

    public void imprimir() {
        Nodo reco=raiz;
        System.out.println("Listado de todos los elementos de la cola.");
        while (reco!=null) {
            System.out.print(reco.info+"-");
            reco=reco.sig;
        }
        System.out.println();
    }
        
    public static void main(String[] ar) {
        Cola cola1=new Cola();
        cola1.insertar(5);
        cola1.insertar(10);
        cola1.insertar(50);
        cola1.imprimir();
        System.out.println("Extraemos uno de la cola:"+cola1.extraer());
        cola1.imprimir();        
    }
}

CÓDIGO DE UNA LISTA
public class Pila {

    class Nodo {
        int info;
        Nodo sig;
    }

    private Nodo raiz;
    
    public Pila () {
        raiz=null;
    }
    
    public void insertar(int x) {
    Nodo nuevo;
        nuevo = new Nodo();
        nuevo.info = x;
        if (raiz==null)
        {
            nuevo.sig = null;
            raiz = nuevo;
        }
        else
        {
            nuevo.sig = raiz;
            raiz = nuevo;
        }
    }
    
    public int extraer ()
    {
        if (raiz!=null)
        {
            int informacion = raiz.info;
            raiz = raiz.sig;
            return informacion;
        }
        else
        {
            return Integer.MAX_VALUE;
        }
    }
    
    public void imprimir() {
        Nodo reco=raiz;
        System.out.println("Listado de todos los elementos de la pila.");
        while (reco!=null) {
            System.out.print(reco.info+"-");
            reco=reco.sig;
        }
        System.out.println();
    }
    
    public static void main(String[] ar) {
        Pila pila1=new Pila();
        pila1.insertar(10);
        pila1.insertar(40);
        pila1.insertar(3);
        pila1.imprimir();
        System.out.println("Extraemos de la pila:"+pila1.extraer());
        pila1.imprimir();        
    }

}

Estructura de datos no lineales: Las estructuras de datos no lineales se les llama 

también estructuras de datos multienlazadas. Cada elemento puede estar enlazado a cualquier otro componentes. Se trata de estructuras de datos en las que cada 
elemento puede tener varios sucesores y/o varios predecesores.

Árboles: Cada elemento sólo puede estar enlazado con su predecesor y sus sucesores. Puede tener varios sucesores

Bicola La bicola o doble cola es un tipo de cola especial que permiten la inserción y eliminación de elementos de ambos extremos de la cola.
Puede representarse a partir de un vector y dos índices, siendo su representación más frecuente una lista circular doblemente enlazada.
Todas las operaciones de este tipo de datos tienen coste constante.

Cola circular: Una cola circular o anillo es una estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor. Los elementos pueden consultarse, añadirse y eliminarse únicamente desde la cabeza del anillo que es una posición distinguida. Existen dos operaciones de rotaciones, una en cada sentido, de manera que la cabeza del anillo pasa a ser el elemento sucesor, o el predecesor, respectivamente, de la cabeza actual.

Cola estática 
import java.util.Vector;

public class Cola {

//private int inicio;
//private int fin;
private int size;
private Vector elementos;

public Cola() {
super();
elementos = new Vector();
//inicio = fin = 0;
size = 0;
}

public boolean colaVacia () {
//if ( (fin-inicio)==0) {
if ( size==0) {
return true;
}
return false;
}

public void encolar ( Tipo o ) {
//elementos.add(fin++, o);
elementos.add(size++, o);
}

public Tipo desencolar () {
Tipo retorno;

try {
if(colaVacia())
throw new ErrorColaVacia();
else {
//return elementos.get(inicio++);
retorno = elementos.get(0);
elementos.remove(0);
size--;
return retorno;
}
} catch(ErrorColaVacia error) {
System.out.println("ERROR: la cola esta vacía");
return null;
}
}

/*
public int getFin() {
return fin;
}

public int getInicio() {
return inicio;
}
*/
public int getSize() {
//return (fin-inicio);
return (size);
}
}

@SuppressWarnings("serial")
class ErrorColaVacia extends Exception {
public ErrorColaVacia() {
super();
}
}
[/JAVA]


[JAVA]
package colas;

public class Test {

@SuppressWarnings("unchecked")
public static void main(String[] args) {
Cola cola;

cola = new Cola();
System.out.println("Elementos en cola: " + cola.getSize());

cola.encolar("Uno");
System.out.println("Elementos en cola: " + cola.getSize());

cola.encolar("Dos");
System.out.println("Elementos en cola: " + cola.getSize());

System.out.println("Extraigo.........: " + cola.desencolar().toString());
System.out.println("Elementos en cola: " + cola.getSize());

cola.encolar("Tres");
System.out.println("Elementos en cola: " + cola.getSize());

System.out.println("Extraigo.........: " + cola.desencolar().toString());
System.out.println("Elementos en cola: " + cola.getSize());

System.out.println("Extraigo.........: " + cola.desencolar().toString());
System.out.println("Elementos en cola: " + cola.getSize());

System.out.println("Extraigo.........: " + cola.desencolar().toString());
System.out.println("Elementos en cola: " + cola.getSize());

}


}

Pila dinámica
package estructuradedatospilas;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class pilas {
     public static void main(String[] args) {
        Scanner leer = new Scanner (System.in);
        int num;
        int op;
        LinkedList pila = new LinkedList();
        do{
            System.out.println("\t menu \t");
            System.out.println("operaciones con pilas");
            System.out.println("1.-insertar al principio");
            System.out.println("2.-insertar al final");
            System.out.println("3.-borrar al final");
            System.out.println("4.-mostrar la pila");
            System.out.println("5.-salir");
            System.out.println("\n");
            System.out.println("elija la operacion que desee");
            op=leer.nextInt();
            switch (op){
                case 1:
                    System.out.println("inserte numero");
                    num=leer.nextInt();
                    pila.addFirst(num);
                    break;

                case 2:
                        System.out.println("inserte numero");
                        num=leer.nextInt();
                        pila.addLast(num);
                        break;


                case 3:
                    System.out.println("se borra el nodo final");
                    pila.removeLast();
                    break;

                case 4:
                    System.out.println("la pila es la siguiente");
                    List pila2= new ArrayList(pila);
                    Iterator it = pila2.iterator();
                    while (it.hasNext()){
                        System.out.println(it.next()+"");

                    }
                    break;
                    case 5:
                     System.out.println("al rato");
                     break;
            }
        }
        while (op !=5);   }         
   }