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.

25 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
    Respuestas
    1. Pues a lo mejor tener una clase principal Noob :v

      Eliminar
    2. Debes tener una clase main donde manda llamar la clase donde defines tu ordenamiento

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

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

    ResponderEliminar
  4. vine aqui por que me comi una salchipapa :v

    ResponderEliminar
  5. vine aqui por que me comi una salchipapa :v

    ResponderEliminar
  6. uno entra a ver si esta la tarea y aqui vendiendo comida chatarra :´(
    jajajjajajaj

    ResponderEliminar
  7. Metodo Seleccion : la variable j no llegas a utilizarla, y hay error en tiempo de ejecucion.

    ResponderEliminar
  8. tu algoritmo recurrente quicksort es incorrecto , no ordena correctamente, intenta con estos datos y veras { 23, 31, 1, 21, 36, 72}

    ResponderEliminar
  9. 1. Se desea implementar una solución que permita al usuario ingresar el tamaño del arreglo y los elementos al mismo, así como seleccionar entre varias opciones de salida del problema. Para la solución del problema el usuario podrá seleccionar entre las siguientes opciones:
    a. Ordenamiento de los elementos por el método de burbuja
    b. Ordenamiento de los elementos por el método de inserción
    c. Ordenamiento de los elementos por el método de selección

    ResponderEliminar
    Respuestas
    1. nesitas el codigo? (cualquier cosa me avisa ando activoxd)
      creo que hice similar primero ingresar el tamaño del vector luego te muestra un menu dinde te pide que es lo que quieres hacer;
      1,llenar vector
      2,mostrar vector
      clasificacion u ordenacion
      3 metodo burbuja
      4, insercion, etc
      metodos de busqueda
      11, secuencial
      12binario
      13salir


      Eliminar
  10. quien me ayuda haciendo una prueba de escritorio de cada uno de los métodos

    ResponderEliminar
  11. Aquellos que solucionaron el error de shell short, compartan el dato por favor. <3

    ResponderEliminar
    Respuestas
    1. // Metodo ShellShort
      public void shellsorth(){
      int salto, aux, i;
      boolean cambios;

      for (salto = arreglo.length / 2; salto != 0; salto /= 2) {
      cambios = true;
      while (cambios) { // Mientras se intercambie algún elemento
      cambios = false;
      for (i = salto; i < arreglo.length; i++) // se da una pasada
      {
      if (arreglo[i - salto] > arreglo[i]) { // y si están desordenados
      aux = arreglo[i]; // se reordenan
      arreglo[i] = arreglo[i - salto];
      arreglo[i - salto] = aux;
      cambios = true; // y se marca como cambio.
      }
      }
      }
      }
      }
      //Usen ese esta mas chido aparte es de la misma pagina

      Eliminar