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;
  }
 }
}

No hay comentarios:

Publicar un comentario en la entrada