jueves, 10 de noviembre de 2011

Metodos de Ordenamiento

Los algoritmos de ordenamiento nos permiten, como su nombre lo dice, ordenar. En este caso, nos servirán para ordenar vectores o matrices con valores asignados aleatoriamente. Nos centraremos en los métodos más populares, analizando la cantidad de comparaciones que suceden, el tiempo que demora y revisando el código, escrito en Java, de cada algoritmo.




Estos metodos son simples de entender y de programar ya que son iterativos, simples
ciclos y sentencias que hacen que el vector pueda ser ordenado.
Existe desde el metodo mas simple, al mas complejo como lo son:


1) Burbuja
2) Insercion
3) Quicksort
4) Shellsort




1) Metodo de la Burbuja:


El metodo de la burbuja es uno de los mas simples, es tan facil como comparar todos
los elementos de una lista contra todos, si se cumple que uno es mayor o menor a
otro, entonces los intercambia de posición.
Por ejemeplo, imaginemos que tenemos los siguientes valores:





Lo que haria una burbuja simple, seria comenzar recorriendo los valores de izq. a derecha, comenzando por el 5. Lo compara con el 6, con el 1, con el 0 y con el 3, si es mayor o menor (dependiendo si el orden es ascendiente o descendiente) se intercambian de posicion. Luego continua con el siguiente, con el 6, y lo compara con todos los elementos de la lista, esperando ver si se cumple o no la misma condicion que con el primer elemento. Asi, sucesivamente, hasta el ultimo elemento de la lista.


2) Metodo de Insercion y Seleccion:

 El ordenamiento por inserción es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.
Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.




Ejemplo de funcionamiento
En el siguiente ejemplo, 32 debe ser insertado entre 26 y 47, y por lo tanto 47, 59 y 96 deben ser desplazados.
               k+1
11 26 47 59 96 32 
11 26    47 59 96
11 26 32 47 59 96




En la implementación computacional, el elemento k+1 va comparándose de atrás para adelante, deteniéndose con el primer elemento menor. Simultáneamente se van haciendo los desplazamientos.
11 26 47 59 96 32
11 26 47 59    96
11 26 47    59 96
11 26    47 59 96
11 26 32 47 59 96








public static void insertSort (int[] v) {
      int aux;
      int j;
      for (int i=1; i<v.length; i++) {
         j=i;
         aux = v[i];
         for (j=i-1; j>=0 && v[j]>aux; j--){
            v[j+1] = v[j];
            v[j] = aux;
         }
      }
   }


El ordenamiento por seleccion consiste en recorrer un arreglo desde la primera posicion hasta n-1, en cada vez que se recorre se busca encontrar el elemento, mas pequeño, de tal forma que despues de la primera vez en la posicion 0 este es el elemento mas pequeño de todo el arreglo; en la segunda vez el segundo elemento mas pequeño y asi suscesivamente hasta ordenar todos los elementos. Este metodo no es el mas eficiente, pero es uno de los mas faciles de implementar




3) Quicksort:

 Este metodo consiste en resolver un problema a partir de la solucion de subproblemas del mismo tipo, pero de moenor de tamaño. Si los subproblemas son todavia son relativamente grandes se aplicara de nuevo esta tecnica hasta alcanzar subproblemas lo sufiencientemente pequeños para ser solucionados directamente.


* Se plante el problema de forma que pueda ser descompuesto en "K" subproblemas del mismo tipo, pero de menor tamaño. Es decir, si el tamaño de la entrada es "n", hemos de conseguir dividir el problema en "k" subproblemas, cada uno de tamaño "nk" y donde 0 es <= nk < n. A esta tarea se le conoce como division.


*Se resuelven independientemente todos los subproblemas. El tamaño de los subproblemas debe ser menor que el tamaño original del problema.


*Finalmente se deben conbinar las soluciones obtenidas anteriormente para construir la solucion del problema original.


#Ejemplo:


public void quicksort (int [] a, int izq, int der) {
int i = izq;
int j = der;


int pivote = a [ (izq + der) / 2 ];
do {
while (a[i] < pivote) {
i ++
}


while (a[j] > pivote) {
j++
}
if ( i <= j) {
int aux = a[i];
a[i] = a [j];
a[j] = aux;
i++;
j--;
}
}
while (i <= j) ;
if (izq < j) {
quicksort (a, izq, j);
}
 if (i < der) {
quicksort  (a,i, der);
}


}






Sea x un arreglo y n el número de elementos en arreglo qsue se debe ordenar. Elegir un elemento a de una posición especifica en el arreglo (por ejemplo, a puede elegirse como el primer elemento del arreglo. Suponer que los elemento de x están separados de manera que a está colocado en la posición j y se cumplen las siguientes condiciones.

1.- Cada uno de los elementos en las posiciones de 0 a j-1 es menor o igual que a.
2.- Cada uno de los elementos en las posiciones j+1 a n-1 es mayor o igual que a.

Observe que si se cumplen esas dos condiciones para una a y j particulares, a es el j-ésimo menor elemento de x, de manera que a se mantiene en su posición j cuando el arreglo está ordenado en su totalidad. Si se repite este procedimiento con los subarreglos que van de x[0] a x[j-1] y de x[j+1] a x[n-1] y con todos los subarreglos creados mediante este proceso, el resultado final será un archivo ordenado.

Ilustremos el quicksort con un ejemplo. Si un arreglo esta dado por:

x = [25 57 48 37 12 92 86 33]

y el primer elemento se coloca en su posición correcta, el arreglo resultante es:

x = [12 25 57 48 37 92 86 33]

En este punto 25 esta en su posición correcta por lo cual podemos dividir el arreglo en

x = [12] 25 [57 48 37 92 86 33]

Ahora repetimos el procedimiento con los dos subarreglos

x = 12  25  [48 37 33] 57 [92 86]

x = 12  25  33 [37 48]  57 [86] [92]

x = 12  25  33 [37 48]  57  86 92

x = 12  25  33 37 48  57  86 92

El procedimiento es entonces.

  • Buscar la partición del arreglo j.
  • Ordenar el subarreglo x[0] a x[j-1]
  • Ordenar el subarreglo x[j+1] a x[n-1]

Su implementación en Java es:

  public void quiksort(int x[],int lo,int ho)
  {
    int t, l=lo, h=ho, mid;

    if(ho>lo)
    {
      mid=x[(lo+ho)/2];
      while(l<h)
      {
        while((l<ho)&&(x[l]<mid))  ++l;
        while((h>lo)&&(x[h]>mid))  --h;
        if(l<=h)
        {
          t    = x[l];
          x[l] = x[h];
          x[h] = t;
          ++l;
          --h;
        }
      }

      if(lo<h) quiksort(x,lo,h);
      if(l<ho) quiksort(x,l,ho);
    }
  }



4) Shellsor:
Ordena una estructura de una manera similar a la de ordenamiento Burbuja, sin embargo no ordena elementos adyacentes sino que utiliza una segmentación entre los datos. Esta segmentación puede ser de cualquier tamaño de acuerdo a una secuencia de valores que empiezan con un valor grande (pero menor al tamaño total de la estructura) y van disminuyendo hasta llegar al '1'. Una secuencia que se ha comprobado ser de las mejores es: ...1093, 364, 121, 40, 13, 4, 1. En contraste, una secuencia que es mala porque no produce un ordenamiento muy eficiente es ...64, 32, 16, 8, 4, 2, 1.


* Es rápido, fácil de entender y fácil de implementar. Sin embargo, su análisis de la complejidad es un poco más sofisticado.La idea de Shell es la siguiente:- organizar la secuencia de datos en una matriz de dos dimensiones ordenar las columnas de la matriz- El efecto es que la secuencia de datos es parcialmente ordenados.
- El proceso anterior se repite, pero cada vez con un conjunto más estrecho, es decir, con un menor número de columnas.
- En el último paso, la matriz se compone de una sola columna. En cada paso, el sortedness de la secuencia se incrementa, hasta que en el último paso es completamente ordenados. Sin embargo, el número de operaciones de ordenación necesarias en cada paso es limitado, debido a la presortedness de la secuencia obtenida en los pasos anteriores.


Ejemplo: Supongamos 3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2 la secuencia de datos ordenados.
En primer lugar, se organiza en una matriz con siete columnas (izquierda), las columnas se ordenan (derecha):


3 7 9 0 5 1 6
8 4 2 0 6 1 5
7 3 4 8 9 2


   
3 3 2 0 5

1 57 4 4 0 6 1 6
8 7 9 9 8 2


3 3 2
0 5 1
5 7 4
4 0 6
1 6 8
7 9 9
8 2



   
0 0 1
1 2 2
3 3 4
4 5 6
5 6 8
7 7 9
8 9

Ahora, la secuencia es casi completamente ordenados. Cuando la organización en una columna en el último paso, es sólo un 6, un 8 y un 9 que tienen que mover un poco a su posición correcta.Elementos de información de 8 y 9 han llegado ya a la final de la secuencia, pero un pequeño elemento (2) también sigue ahí. En el siguiente paso, la secuencia se organiza en tres columnas, que son ordenados de nuevo:



 

void shellsort ( int a[], int n)
/* Este procedimiento recibe un arreglo a ordenar a[] y el tamaño del arreglo n. Utiliza en este caso una serie de t=6 incrementos h=[1,4,13,40,121,364] para el proceso (asumimos que el arreglo no es muy grande). */
{
 int x,i,j,inc,s;
 
 for(s=1; s < t; s++)   /* recorre el arreglo de incrementos */
 {
  inc = h[s];
  for(i=inc+1; i < n; i++) 
  {
   x = a[i];
   j = i-inc;
   while( j > 0 && a[j] > x)
   {
    a[j+h] = a[j];
    j = j-h;
   }
   a[j+h] = x;
  }
 }
}

miércoles, 9 de noviembre de 2011

"Arboles en Java . . ."

Los árboles se pueden definir como un tipo restringido de grafo.






Un grafo se define de la siguiente manera: Un grafo consiste de un número de nodos (puntos o vértices) y un grupo de arcos que unen parejas de nodos. A todos los pares de nodos unidos por un arco se les llama nodos adyacentes. Los arcos pueden tener una dirección determinada, generando así un grafo dirigido, el cual de lo contrario sería no-dirigido. (También existen los grafos mixtos).
Por convención a los nodos de un grafo se le representa con círculos y los arcos que los conectan como líneas(no-dirigido) o flechas (dirigido).

Los árboles son entonces un subconjunto importante de los grafos, y son una herramienta útil para describir estructuras que representan algún tipo de jerarquía.
Un árbol dirigido tiene un nodo al que se le llama "raíz" y de este nodo parten todas las conexiones a los demás nodos. A los nodos terminales se les llama "hojas" y a todos los demás se les llama nodos intermedios.
De acuerdo al número de arcos que parten de cada nodo en un árbol, este se puede clasificar en diferentes categorías. Así se tienen árboles binarios, árboles 2-3-4, árboles rojo-negro, árboles B, etc.

A los nodos que dependen de otro nodo también se les conoce como nodos "hijos" o descendientes y al otro se le llama nodo "padre".
De esto de puede concluir que cada nodo padre es una raíz de un sub-árbol.

El número de sub-árboles que tiene un nodo determinan el grado del nodo. Naturalmente el grado de las hojas es de cero. Por convención al nodo raíz de árbol se le considera el nivel cero del árbol.
Cuando se tienen varios árboles en un conjunto,al conjunto se le llama bosque.

Altura de un nodo: Es la longitud del camino más largo desde el nodo hasta una hoja que sea descendiente de este nodo.
Altura de un árbol = altura del nodo raíz.
Para poder realizar búsquedas eficientes en árboles se manejan dos características: Los árboles pueden estar balanceados por altura o por peso.

Árbol balanceado por altura: en dónde todos los hijos o nodos hoja se intentan mantener a la misma distancia de la raíz.
Árbol balanceado por peso: en dónde los nodos más visitados o utilizados se mantienen a poca distancia de la raíz.


Tipos de Árboles:

Árboles binarios

Un árbol binario representado con nodos ligados:
Como lo indica su nombre, estos árboles estan formados por nodos que pueden tener un máximo de 2 hijos.

DEFINICIONES :

Arbol relleno : Cuando todo nodo tiene 2 hijos o bien es hoja.

Arbol binario completo : Un arbol binario relleno en dónde todas las hojas tienen la misma profundidad.

Métodos para recorrer un árbol binario:

a) Pre-orden (preorder) :

Primero se recorre la raíz
Segundo se recorre el subárbol izquierdo en pre-orden
Tercero se recorre el subárbol derecho en pre-orden

b) En-orden (inorder)
Primero se recorre el subárbol izquierdo en-orden
Segundo se recorre la raíz
Tercero se recorre el subárbol derecho en-orden

c) Post-orden (postorder)
Primero se recorre el subárbol izquierdo en post-orden
Segundo se recorre el subárbol derecho en post-orden
Tercero se recorre la raiz
Intercambiando izquierda por derecha en los tres métodos anteriores se obtienen tres métodos a los cuales se les llama :

Pre-orden converso
En-orden converso
Post-orden converso