martes, 21 de junio de 2011

METODOS DE ORDENAMIENTO [JAVA]

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.

METODOS ITERATIVOS

Estos métodos son simples de entender y de programar ya que son iterativos, simples ciclos y sentencias que hacen que el vector pueda ser ordenado.
Dentro de los Algoritmos iterativos encontramos:

  • ·         Burbuja
  • ·         Inserción
  • ·         Selección
  • ·         Shellsort

    METODOS RECURSIVOS

Estos métodos son aún más complejos, requieren de mayor atención y conocimiento para ser entendidos. Son rápidos y efectivos, utilizan generalmente la técnica Divide y vencerás, que consiste en dividir un problema grande en varios pequeños para que sea más fácil resolverlos.
Mediante llamadas recursivas a sí mismas, es posible que el tiempo de ejecución y de ordenación sea más óptimo.
Dentó de los algoritmos recursivos encontramos:

  • Ordenamiento por Mezclas (merge)
  • Ordenamiento Rápido (quick)

METODO BURBUJA

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

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

METODO SELECCIÓN
public static void Seleccion(int[]matrix){
        int i, j, k, p, buffer, limit = matrix.length-1;
        for(k = 0; k < limit; k++){
            p = k;
            for(i = k+1; i < = limit; i++){
                if(matrix[i] < matrix[p]) p = i;
                if(p != k){
                    buffer = matrix[p];
                    matrix[p] = matrix[k];
                    matrix[k] = buffer;
                }
            }
        }
    }

METODO SHELL SHORT
public static void shellSort(int[] matrix) {
    for ( int increment = matrix.length / 2;increment > 0;
          increment = (increment == 2 ? 1 : (int) Math.round(increment / 2.2))) {
        for (int i = increment; i < matrix.length; i++) {
            for (int j = i; j > = increment && matrix[j - increment] > matrix[j]; j -= increment) {
                int temp = matrix[j];
                matrix[j] = matrix[j - increment];
                matrix[j - increment] = temp;
            }
        }
    }
}

ORDENAMIENTO POR MEZCLAS (MERGE)
El algoritmo de ordenamiento por mezcla (Merge) se divide en dos procesos, primero se divide en partes iguales la lista:
public static void mergesort(int[ ] matrix, int init, int n){
    int n1;
    int n2;
    if (n > 1){
        n1 = n / 2;
        n2 = n - n1;
        mergesort(matrix, init, n1);
        mergesort(matrix, init + n1, n2);
        merge(matrix, init, n1, n2);
   }
}
Y el algoritmo que nos permite mezclar los elementos según corresponda:
private static void merge(int[ ] matrix, int init, int n1, int n2){
    int[ ] buffer = new int[n1+n2];
    int temp = 0;
    int temp1 = 0;
    int temp2 = 0;
    int i;
    while ((temp1 < n1) && (temp2 < n2)){
        if (matrix[init + temp1] < matrix[init + n1 + temp2]){
            buffer[temp++] = matrix[init + (temp1++)];
        }else{
            buffer[temp++] = matrix[init + n1 + (temp2++)];
        }
    }
    while (temp1 < n1){
        buffer[temp++] = matrix[init + (temp1++)];
    }
    while (temp2 < n2){
        buffer[temp++] = matrix[init + n1 + (temp2++)];
    }
    for (i = 0; i < n1+n2; i++){
        matrix[init + i] = buffer[i];
    }
}

ORDENAMIENTO RAPIDO
public static void Rapido(int matrix[], int a, int b){
    matrix = new int[matrix.length];
    int buf;
    int from = a;
    int to = b;
    int pivot = matrix[(from+to)/2];
    do{
        while(matrix[from] < pivot){
            from++;
        }
        while(matrix[to] > pivot){
            to--;
        }
        if(from < = to){
            buf = matrix[from];
            matrix[from] = matrix[to];
            matrix[to] = buf;
            from++; to--;
        }
    }while(from < = to);
    if(a < to){
        Rapido(matrix, a, to);
    }
    if(from < b){
        Rapido(matrix, from, b);
    }
} 

COMPLEJIDAD
Cada algoritmo de ordenamiento por definición tiene operaciones y cálculos mínimos y máximos que realiza (complejidad), a continuación una tabla que indica la cantidad de cálculos que corresponden a cada método de ordenamiento:

Algoritmo
Operaciones máximas
Burbuja
Ω(n2)
Inserción
Ω(n2/4)
Selección
Ω(n2)
Shell
Ω(n log2n)
Merge
Ω(n logn)
Quick
Ω(n2) en peor de los casos y Ω(n logn) en el promedio de los casos.
 Se puede decir que faltan metodos de ordenamiento pero estos son los mas usuales. Gracias.

3 comentarios:

  1. Compañero me sale el error de que no se han encontrado clases principales al aplicar estos algoritmos que deberia hacer? muchas gracias

    ResponderEliminar
  2. Debes tener en cuenta si ya tienes definidos los vectores...

    ResponderEliminar
  3. Gracias compa, me ahorraste algo de tiempo =D

    ResponderEliminar