Ordenacion internas java

INTRODUCCION

Cuestiones generales
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 (sepuede 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.

7 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étodoconsiste 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 segundo 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 porel 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, elnúmero de comprobaciones que hay que hacer es de N*(N-1)/2, luego el tiempo de ejecución está en O(n2)
int array[N];
int i,j,menor,aux;

// Dar valores a los elementos del array

for(i=0;i<N-1;i++)
{
for(j=i+1,menor=i;j<N;j++)if(array[j]<array[menor]) // Si el elemento j es menor que el menor:
menor=j; // el menor pasa a ser el elemento j.
aux=array[i]; // Se intercambian los elementos
array[i]=array[menor]; // de las posiciones i y menor
array[menor]=aux; // usando una variable auxiliar.
}

7.1 Algoritmos Ordenamiento por IntercambioAlgoritmos de intercambio:
En este tipo de algoritmos se toman los elementos de dos en dos, se comparan y se INTERCAMBIAN si no están en el orden adecuado. Este proceso se repite hasta que se ha analizado todo el conjunto de elementos y ya no hay intercambios.
Entre estos algoritmos se encuentran el BURBUJA y QUICK SORT.

7.1.1Ordenación burbuja
Burbuja: Consiste en comparar pares deelementos 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 el40.

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, porlo que habría que hacer (N-1)*(N-i-1) comparaciones, para cada i desde 1 hasta N-1. El número de comparaciones es, por tanto, N(N-1)/2, lo que nos deja un tiempo de ejecución, al igual que en la selección, en O(n2).
int array[N];
int i,j,aux;

// Dar valores a los elementos del array

for(i=0;i<N-1;i++) // Hacer N-1 pasadas.
{
for(j=0;j<N-i-1;j++) // Mirar los N-i-1 pares.
{...