MÉTODOS DE ORDENAMIENTO

MÉTODOS DE ORDENAMIENTO 

Los métodos de ordenamiento son necesarios para que luego de ordenar, se puedan buscar datos de una manera mucho mas rápida y eficiente aplicando distintas técnicas.

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 Bubbleshort (o Método Burbuja), que son Simples iteraciones, hasta el Quickshort (Método Rápido), que al estar optimizado usando recursión, su tiempo de ejecución es menor y es más efectivo.

MÉTODOS 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
  

  MÉTODOS 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)
• ORDENAMIENTO DE BURBUJA
  
  La Ordenación de burbuja (Bubble Sort en inglés) Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar

MÉTODO BURBUJA

view plainprint?

1. public static void burbuja(int[]matrix){  
2.         int temp;  
3.         for(int i=1;i < matrix.length;i++){  
4.             for (int j=0 ; j < matrix.length- 1; j++){  
5.                 if (matrix[j] > matrix[j+1]){  
6.                     temp = matrix[j];  
7.                     matrix[j] = matrix[j+1];  
8.                     matrix[j+1] = temp;  
9.                 }  
10.             }  
11.         }  
12.     }  

ORDENAMIENTO POR INSERCION  
El ordenamiento por inserción (insertion short en inglés) 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) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

MÉTODO INSERCION 

view plainprint?

1. public static void Insercion (int[] vector) {  
2.       for (int i=1; i < vector.length; i++) {  
3.          int aux = vector[i];  
4.          int j;  
5.          for (j=i-1; j > =0 && vector[j] > aux; j--){  
6.               vector[j+1] = vector[j];  
7.           }  
8.          vector[j+1] = aux;  
9.       }  
10.    }  
11. 
    

ORDENAMIENTO POR SELECCIóN  
El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere Ooperaciones para ordenar una lista de n elementos.Su funcionamiento es el siguiente:

• Buscar el mínimo elemento de la lista

• Intercambiarlo con el primero

• Buscar el mínimo en el resto de la lista

• Intercambiarlo con el segundo

• Buscar el mínimo elemento entre una posición i y el final de la lista

• Intercambiar el mínimo con el elemento de la posición i

Este algoritmo mejora ligeramente el algoritmo de la burbuja. En el caso de tener que ordenar un vector de enteros, esta mejora no es muy sustancial, pero cuando hay que ordenar un vector de estructuras más complejas, la operación de intercambiar los elementos sería más costosa en este caso.

MÉTODO SELECCIÓN

view plainprint?

1. public static void Seleccion(int[]matrix){  
2.         int i, j, k, p, buffer, limit = matrix.length-1;  
3.         for(k = 0; k < limit; k++){  
4.             p = k;  
5.             for(i = k+1; i < = limit; i++){  
6.                 if(matrix[i] < matrix[p]) p = i;  
7.                 if(p != k){  
8.                     buffer = matrix[p];  
9.                     matrix[p] = matrix[k];  
10.                     matrix[k] = buffer;  
11.                 }  
12.             }  
13.         }  
14.     }  

  ORDENAMIENTO SHELL SHORT 

   Shell Sort es una generalización del ordenamiento por inserción , teniendo en cuenta dos observaciones:

El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".

El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.

El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.

MÉTODO SHELL SHORT

view plainprint?

1. public static void shellSort(int[] matrix) {  
2.     for ( int increment = matrix.length / 2;increment > 0;  
3.           increment = (increment == 2 ? 1 : (int) Math.round(increment / 2.2))) {  
4.         for (int i = increment; i < matrix.length; i++) {  
5.             for (int j = i; j > = increment && matrix[j - increment] > matrix[j]; j -= increment) {  
6.                 int temp = matrix[j];  
7.                 matrix[j] = matrix[j - increment];  
8.                 matrix[j - increment] = temp;  
9.             }  
10.         }  
11.     }  
12. }  

ORDENAMIENTO POR MEZCLAS (MERGE)
El algoritmo de ordenamiento por mezcla (Merge) se divide en dos procesos, primero se divide en partes iguales la lista:

view plainprint?

1. public static void mergesort(int[ ] matrix, int init, int n){  
2.     int n1;  
3.     int n2;  
4.     if (n > 1){  
5.         n1 = n / 2;  
6.         n2 = n - n1;  
7.         mergesort(matrix, init, n1);  
8.         mergesort(matrix, init + n1, n2);  
9.         merge(matrix, init, n1, n2);  
10.    }  
11. }  

Y el algoritmo que nos permite mezclar los elementos según corresponda:

view plainprint?

1. private static void merge(int[ ] matrix, int init, int n1, int n2){  
2.     int[ ] buffer = new int[n1+n2];  
3.     int temp = 0;  
4.     int temp1 = 0;  
5.     int temp2 = 0;  
6.     int i;  
7.     while ((temp1 < n1) && (temp2 < n2)){  
8.         if (matrix[init + temp1] < matrix[init + n1 + temp2]){  
9.             buffer[temp++] = matrix[init + (temp1++)];  
10.         }else{  
11.             buffer[temp++] = matrix[init + n1 + (temp2++)];  
12.         }  
13.     }  
14.     while (temp1 < n1){  
15.         buffer[temp++] = matrix[init + (temp1++)];  
16.     }  
17.     while (temp2 < n2){  
18.         buffer[temp++] = matrix[init + n1 + (temp2++)];  
19.     }  
20.     for (i = 0; i < n1+n2; i++){  
21.         matrix[init + i] = buffer[i];  
22.     }  
23. }  

ORDENAMIENTO RÁPIDO

view plainprint?

1. public static void Rapido(int matrix[], int a, int b){  
2.     matrix = new int[matrix.length];  
3.     int buf;  
4.     int from = a;  
5.     int to = b;  
6.     int pivot = matrix[(from+to)/2];  
7.     do{  
8.         while(matrix[from] < pivot){  
9.             from++;  
10.         }  
11.         while(matrix[to] > pivot){  
12.             to--;  
13.         }  
14.         if(from < = to){  
15.             buf = matrix[from];  
16.             matrix[from] = matrix[to];  
17.             matrix[to] = buf;  
18.             from++; to--;  
19.         }  
20.     }while(from < = to);  
21.     if(a < to){  
22.         Rapido(matrix, a, to);  
23.     }  
24.     if(from < b){  
25.         Rapido(matrix, from, b);  
26.     }  
27. }   

Diagrama de flujo del método de ordenamiento de quickshort

Diagrama de flujo de ordenamiento por inserción

Diagrama de flujo de ordenamiento por burbuja

{

Diagrama de flujo de ordenamiento por selección directa

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.