ORDENACION INTERNA

Su finalidad es organizar ciertos datos (normalmente arrays o ficheros) en un orden creciente o decreciente mediante una regla prefijada (numérica, alfabética...). Atendiendo al tipo de elemento que se quiera ordenar puede ser: Ordenación interna: Los datos se encuentran en memoria (ya sean arrays, listas, etc), y son de acceso aleatorio o directo (se puede acceder a un determinado campo sin pasar por los anteriores). Ordenación externa: Los datos están en un dispositivo de almacenamiento externo (ficheros), y su ordenación es más lenta que la interna. Ordenación interna Los métodos de ordenación interna se aplican principalmente a arrays unidimensionales. Los principales algoritmos de ordenación interna son:
Selección: Este método consiste en buscar el elemento más pequeño del array y ponerlo en primera posición; luego, entre los restantes, se busca el elemento más pequeño y se coloca en segudo lugar, y así sucesivamente hasta colocar el último elemento. Por ejemplo, si tenemos el array {40,21,4,9,10,35}, los pasos a seguir son:

{4,21,40,9,10,35} <-- Se coloca el 4, el más pequeño, en primera posición : se cambia el 4 por el 40. {4,9,40,21,10,35} <-- Se coloca el 9, en segunda posición: se cambia el 9 por el 21. {4,9,10,21,40,35} <-- Se coloca el 10, en tercera posición: se cambia el 10 por el 40. {4,9,10,21,40,35} <-- Se coloca el 21, en tercera posición: ya está colocado. {4,9,10,21,35,40} <-- Se coloca el 35, en tercera posición: se cambia el 35 por el 40. Si el array tiene N elementos, el número de comprobaciones que hay que hacer es de N*(N-1)/2. private static void permuta (int[] V, int i, int j) { int t; t= V[i]; V[i]= V[j]; V[j]= t; } // Ordenacion por seleccion public static void seleccion (int[] V) { int L= V.length; int menor,i,j; for (i= 0; i < L-1; i++) { for (j= i+1,menor=i; j < L; j++) if (V[j] < V[menor]) menor= j; // el mas pequeño permuta (V, i, menor); } } Burbuja: Consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados. Con el array anterior, {40,21,4,9,10,35}: Primera pasada: {21,40,4,9,10,35} <-- Se cambia el 21 por el 40. {21,4,40,9,10,35} <-- Se cambia el 40 por el 4. {21,4,9,40,10,35} <-- Se cambia el 9 por el 40. {21,4,9,10,40,35} <-- Se cambia el 40 por el 10. {21,4,9,10,35,40} <-- Se cambia el 35 por el 40. Segunda pasada: {4,21,9,10,35,40} <-- Se cambia el 21 por el 4. {4,9,21,10,35,40} <-- Se cambia el 9 por el 21. {4,9,10,21,35,40} <-- Se cambia el 21 por el 10. Ya están ordenados, pero para comprobarlo habría que acabar esta segunda comprobación y hacer una tercera. Si el array tiene N elementos, para estar seguro de que el array está ordenado, hay que hacer N-1 pasadas, por lo que habría que hacer (N-1)*(N-i-1) comparaciones. //metodo de la burbuja public static void burbuja (int[] V) { int L= V.length; boolean cambios; for (int i= 0; i < L-1; i++) { cambios= false; for (int j= L-1; j > i; j--) { if (V[j-1] > V[j]) { permuta (V, j-1, j); cambios= true; } } if (! cambios) break; } }
Inserción directa: En este método lo que se hace es tener una sublista ordenada de elementos del array e ir insertando el resto en el lugar adecuado para que la sublista no pierda el orden. Para el ejemplo {40,21,4,9,10,35}, se tiene:
{40,21,4,9,10,35} <-- La primera sublista ordenada es {40}. Insertamos el 21: {40,40,4,9,10,35} <-- aux=21; {21,40,4,9,10,35} <-- Ahora la sublista ordenada es {21,40}. Insertamos el 4: {21,40,40,9,10,35} <-- aux=4; {21,21,40,9,10,35} <-- aux=4; {4,21,40,9,10,35} <-- Ahora la sublista ordenada es {4,21,40}. Insertamos el 9: {4,21,40,40,10,35} <-- aux=9; {4,21,21,40,10,35} <-- aux=9; {4,9,21,40,10,35} <-- Ahora la sublista ordenada es {4,9,21,40}. Insertamos el 10: {4,9,21,40,40,35} <-- aux=10; {4,9,21,21,40,35} <-- aux=10; {4,9,10,21,40,35} <-- Ahora la sublista ordenada es {4,9,10,21,40}. Y por último insertamos el 35: {4,9,10,21,40,40} <-- aux=35; {4,9,10,21,35,40} <-- El array está ordenado. En el peor de los casos, el número de comparaciones que hay que realizar es de N*(N-1)/2. public static void inserccion(int[] V) { int L= V.length; int j, aux; for (int i= 0; i < L-1; i++) { j= i+1; aux= V[j]; while (j > 0 && aux < V[j-1]) { V[j]= V[j-1]; j--; } V[j]= aux; } } Inserción binaria: Es el mismo método que la inserción directa, excepto que la búsqueda del orden de un elemento en la sublista ordenada se realiza mediante una búsqueda binaria, lo que supone un ahorro de tiempo .
Shell: Es una mejora del método de inserción directa, utilizado cuando el array tiene un gran número de elementos. En este método no se compara a cada elemento con el de su izquierda, como en el de inserción, sino con el que está a un cierto número de lugares (llamado salto) a su izquierda. Este salto es constante, y su valor inicial es N/2 (siendo N el número de elementos, y siendo división entera). Se van dando pasadas hasta que en una pasada no se intercambie ningún elemento de sitio. Entonces el salto se reduce a la mitad, y se vuelven a dar pasadas hasta que no se intercambie ningún elemento, y así sucesivamente hasta que el salto vale 1.