Ordenar Arrays en Java (con sus indices)
El proyecto realizado en este tutorial lo podeis descargar pinchando AQUI.
El API SortArray_1.0.jar y el JavaDoc, lo podeis descargar pinchando AQUI.
Todos los que habéis hecho o estais haciendo la carrera de ingeniería informática, habéis tenido que ver en alguna asignatura (en mi caso en la asignatura de "Algorítmica y Complejidad") los métodos de ordenación de arrays, ya que aunque se trate de algo muy trivial, no lo es tanto si se tienen que ordenar arrays de un tamaño considerable, ya que los algoritmos de ordenación de arrays tiene complejidad O(n^2).
Por hacer un breve resumen de los métodos de ordenación de arrays (sin entrar en sus detalles) se ha de decir que estos métodos se clasifican en 3 tipos que son: 1.- Métodos de inserción, 2.- Métodos de Selección y 3.- Métodos de intercambio. Dentro de los métodos de inserción se encuentran los métodos de inserción directa(*) e inserción binaria o dicotómica. Sobre los métodos de selección se encuentra el método de selección directa y en los métodos de intercambio nos encontramos con los métodos de la burbuja, la sacudida y el quickSort(*). Después de muchos años escuchando a gente, solo se acuerdan del método de la burbuja (supongo que lo recordaran por su nombre peculiar) pero hay que decir que de todos los métodos citados es el peor método que hay con diferencia para ordenar arrays. Los método marcados con (*) son los más recomendables para la ordenación de arrays; inserción directa y quickSort.
Pasando a lo que nos interesa, en java nos encontramos con el método "Sort" de la clase Array que nos ordena un array de menor a mayor. No lo se seguro, pero por el nombre "tiene pinta" que lo hace con el método quickSort. Vamos a poner un ejemplo de como llamar a este método:
// Array a ordenar:
int[] intArray = { 3, 2, 8, 5, 7, 9 };
// Método "sort" para ordenar el array
Arrays.sort(intArray);
Si ejecutáis un programa con este código en java e imprimis el array después de ejecutar este método, comprobareis que os da el array ordenado de menor a mayor.
Como veis es muy sencillo de ordenar un array de cualquier tipo de datos de menor a mayor, pero: ¿Y si lo quiero ordenar de mayor a menor? ó ¿Si quiero saber los indices del array tras la ordenación?, es decir como resuelvo el siguiente problema:
...Array desordenado de enteros ... Indices: 0 1 2 3 4 5 Array: 3 2 8 5 7 9 ...Array Ordenado decrecientemente con sus indices ... Indices: 5 2 4 3 0 1 Array: 9 8 7 5 3 2
Bueno, tranquilos que no es el fin del mundo ;). Para los experimentos que suelo hacer, necesito muchas veces obtener, dado un array, su array ordenado junto con sus indices. He encontrado muchas soluciones por web como "StackOverflow", pero al final ninguna me convence y decidi hacer una API que resuelva estos problemas para los arrays de enteros, floats, doubles y Strings. Este API la he llamado SortArray y la podeis descargar en el enlace que os he puesto arriba. El ".jar" se llama "SortArray_1.0.jar". Con esta API podeis ordenar arrays de los tipos de datos citados anteriormente y lo podeis hacer de mayor a menor o de menor a mayor, pudiendo obtener los indices de los arrays tras la ordenación. A continuación paso a poner ejemplos de la utilización del API que son los mismo que podeis encontrar en el proyecto.
Dado un Array de números enteros "intArray" lo quiero ordenar de menor a mayor y de mayor a menor, sabiendo los indices. Para ello me creo un objeto de la clase "SortArray" y llamo a los métodos de ordenación, pidiendo después los array correspondientes con los metodos "get":
// Array a ordenar:
int[] intArray = { 3, 2, 8, 5, 7, 9 };
int[] intArray2 = Arrays.copyOf(intArray, intArray.length); // Hago una copia del array para ordenarlo de mayor a menor
// Ordenamos el array de menor a mayor
SortArrays sortArrays = new SortArrays(intArray); // Nos creamos un objeto de la clase SortArray
sortArrays = sortArrays.increasingOrderInt(); // Llamamos al método que ordena el array y sus indices de menor a mayor
int [] indices = sortArrays.getIndexArray(); // Obtengo los indices de array tras ordenarlo
int [] arrayOrdenado = sortArrays.getIntArray(); // Obtengo el array de enteros ordenado
// Ordenamos el array de mayor a menor
sortArrays = new SortArrays(intArray2); // Nos creamos el objeto de la clase SortArray
sortArrays = sortArrays.decreasingOrderInt(); // Llamamos al método que ordena el array de mayor a menor
int indices [] = sortArrays.getIndexArray(); // Obtengo los indices del array tras ordenarlos
int [] arrayOrdenado = sortArrays.getIntArray(); // Obtengo el array de enteros ordenado
Este código como tal no funciona, porque es un pseudocódigo. En el proyecto que os podeis descargar esta bien escrito. Aqui lo he escrito así para que se entienda y se pueda leer bien. Si ejecutáis el proyecto vereis que os devuelve los arrays ordenados con sus respectivos indices. Si imprimis por pantalla estos arrays os saldrá lo siguiente:
...Array desordenado de enteros ... Indices: 0 1 2 3 4 5 Array: 3 2 8 5 7 9 ...Array Ordenado crecientemente con sus indices utilizando el API ... Indices: 1 0 3 4 2 5 Array: 2 3 5 7 8 9 ...Array desordenado de enteros ... Indices: 0 1 2 3 4 5 Array: 3 2 8 5 7 9 ...Array Ordenado decrecientemente con sus indices utilizando el API ... Indices: 5 2 4 3 0 1 Array: 9 8 7 5 3 2
En este caso se ha mostrado como ordenar array de tipo entero. Para ordenar los arrays de los otros tipos teneis que llamar a los siguientes métodos que podeis ver en el JavaDoc que os podeis descargar del enlace de arriba:
// ORDENAR ARRAY DE FLOATS DE MENOR A MAYOR SortArrays sortArrays = new SortArrays(floatArray); // Creamos el objeto pasandole el array al constructor sortArrays = sortArrays.increasingOrderFloat(); // Llamamos al método para que ordene el array de menor a mayor int [] indices = sortArrays.getIndexArray(); // Obtenemos los indices del array ordenado float [] arrayOrdenado = sortArrays.getFloatArray(); // Obtenemos el array ordenado de floats de menor a mayor // ORDENAR ARRAY DE FLOATS DE MAYOR A MENOR SortArrays sortArrays = new SortArrays(floatArray); // Creamos el objeto pasandole el array al constructor sortArrays = sortArrays.decreasingOrderFloat(); // Llamamos al método para que ordene el array de mayor a menor int [] indices = sortArrays.getIndexArray(); // Obtenemos los indices del array ordenado float [] arrayOrdenado = sortArrays.getFloatArray(); // Obtenemos el array ordenado de floats de menor a mayor // ORDENAR ARRAY DE DOUBLES DE MENOR A MAYOR SortArrays sortArrays = new SortArrays(doubleArray); // Creamos el objeto pasandole el array al constructor sortArrays = sortArrays.increasingOrderDouble(); // Llamamos al método para que ordene el array de menor a mayor int [] indices = sortArrays.getIndexArray(); // Obtenemos los indices del array ordenado double [] arrayOrdenado = sortArrays.getDoubleArray(); // Obtenemos el array ordenado de doubles de menor a mayor // ORDENAR ARRAY DE DOUBLES DE MAYOR A MENOR SortArrays sortArrays = new SortArrays(doubleArray); // Creamos el objeto pasandole el array al constructor sortArrays = sortArrays.decreasingOrderDouble(); // Llamamos al método para que ordene el array de mayor a menor int [] indices = sortArrays.getIndexArray(); // Obtenemos los indices del array ordenado double [] arrayOrdenado = sortArrays.getDoubleArray(); // Obtenemos el array ordenado de doubles de mayor a menor // ORDENAR ARRAY DE STRINGS DE MENOR A MAYOR SortArrays sortArrays = new SortArrays(stringArray); // Creamos el objeto pasandole el array al constructor sortArrays = sortArrays.increasingOrderString(); // Llamamos al método para que ordene el array de menor a mayor int [] indices = sortArrays.getIndexArray(); // Obtenemos los indices del array ordenado String [] arrayOrdenado = sortArrays.getStringArray(); // Obtenemos el array ordenado de strings de menor a mayor // ORDENAR ARRAY DE STRINGS DE MAYOR A MENOR SortArrays sortArrays = new SortArrays(stringArray); // Creamos el objeto pasandole el array al constructor sortArrays = sortArrays.decreasingOrderString(); // Llamamos al método para que ordene el array de mayor a menor int [] indices = sortArrays.getIndexArray(); // Obtenemos los indices del array ordenado String [] arrayOrdenado = sortArrays.getStringArray(); // Obtenemos el array ordenado de strings de mayor a menor
Con estos objetos y métodos, si queremos ordenar los siguiente arrays:
float[] floatArray = { 3.3f, 2.2f, 8.8f, 5.5f, 7.7f, 9.9f };
double[] doubleArray = { 3.33333, 2.22222, 8.88888, 5.55555, 7.77777, 9.99999 };
String[] stringArray = { "España", "Francia", "Italia", "Alemania", "Holanda" };
Vamos a tener como salida lo siguiente (esto es lo que tenéis ejecutando el proyecto que os hemos compartido):
...Array desordenado de floats ... Indices: 0 1 2 3 4 5 Array: 3.3 2.2 8.8 5.5 7.7 9.9 ...Array Ordenado crecientemente con sus indices utilizando el API ... Indices: 1 0 3 4 2 5 Array: 2.2 3.3 5.5 7.7 8.8 9.9 ...Array desordenado de floats ... Indices: 0 1 2 3 4 5 Array: 3.3 2.2 8.8 5.5 7.7 9.9 ...Array Ordenado decrecientemente con sus indices utilizando el API ... Indices: 5 2 4 3 0 1 Array: 9.9 8.8 7.7 5.5 3.3 2.2 ...Array desordenado de doubles ... Indices: 0 1 2 3 4 5 Array: 3.33333 2.22222 8.88888 5.55555 7.77777 9.99999 ...Array Ordenado crecientemente con sus indices utilizando el API ... Indices: 1 0 3 4 2 5 Array: 2.22222 3.33333 5.55555 7.77777 8.88888 9.99999 ...Array desordenado de doubles ... Indices: 0 1 2 3 4 5 Array: 3.33333 2.22222 8.88888 5.55555 7.77777 9.99999 ...Array Ordenado decrecientemente con sus indices utilizando el API ... Indices: 5 2 4 3 0 1 Array: 9.99999 8.88888 7.77777 5.55555 3.33333 2.22222 ...Array desordenado de Strings ... Indices: 0 1 2 3 4 Array: España Francia Italia Alemania Holanda ...Array Ordenado crecientemente con sus indices utilizando el API ... Indices: 3 0 1 4 2 Array: Alemania España Francia Holanda Italia ...Array desordenado de Strings ... Indices: 0 1 2 3 4 Array: España Francia Italia Alemania Holanda ...Array Ordenado decrecientemente con sus indices utilizando el API ... Indices: 2 4 1 0 3 Array: Italia Holanda Francia España Alemania
Una vez explicado el funcionamiento del API y que podeis descargar sin problema, pasamos a explicar como hemos hecho los métodos de ordenación de arrays e indices. Lo vamos a explicar para el caso de ordenar array de enteros, pero cambiando el tipo de variables, se haría lo mismo con cualquier otro tipo de datos.
Lo primero que hacemos es hacer una copia del array que queremos ordenar, para poder posteriormente compararlos y obtener los indices ordenados del array. La copia de arrays se hace de la siguiente forma:
int[] intArray = { 3, 2, 8, 5, 7, 9 }; // Array original
int[] intArrayCopia = Arrays.copyOf(intArray, intArray.length); // Copia del array
MUCHISIMO CUIDADO!!!! a la hora de hacer la copia. Mucho confunden hacer una copia con copiar la referencia. Si hacéis lo siguiente "intArray=intArrayCopia" estais haciendo una copia de la referencia del array. Esto es un poco largo de explicar pero hacer la copia bien que en eso falla mucho la gente.
Una vez que se ha hecho la copia del array, ordenamos el primer array de menor a mayor con el método "Sort" de la clase Arrays, tal y como mostramos al inicio del tutorial:
// Order the Array in increasing order Arrays.sort(intArray);
En este caso tenemos dos array, el ordenado de menor a mayor y el desordenado. Si queremos que el array este ordenado de mayor a menor, hemos creado el siguiente método que nos cambia el orden del array:
public int[] invertIntArray(int[] array) {
int i = 0;
int j = array.length - 1;
int tmp;
while (j > i) {
tmp = array[j];
array[j] = array[i];
array[i] = tmp;
j--;
i++;
}
return array;
}
Este método solo se utilizara si queremos ordenar el array de mayor a menor.
Ahora solo queda ver los indices de los array, por eso hemos hecho una copia del array original, para compararlos y obtener sus indices. El siguiente método obtiene el orden de los indices pasándole como parámetros al array desordenado y el ordenado:
private int[] orderIntIndex(int[] disorderArray, int[] orderArray) {
int lon = disorderArray.length;
int[] index = new int[lon];
Arrays.fill(index, 0);
boolean[] esta = new boolean[lon];
Arrays.fill(esta, false);
for (int i = 0; i < orderArray.length; i++) {
int in = 0;
boolean stay = false;
while (in < orderArray.length & !stay) {
if ((disorderArray[in] == orderArray[i]) & !esta[in]) {
esta[in] = true;
index[i] = in;
stay = true;
} else {
in++;
}
}
}
return index;
}
Con estos métodos es como se ha hecho el API, cambiando evidentemente los tipos de datos para cada caso. Esto ha sido todo. El API esta hecho por nosotros y lo podeis descargar y compartir libremente. Cualquier comentario o duda sobre el API, dejarnos un comentario en la entrada ;).
Me ha sido de mucha utilidad. Gracias.
Hola, escribes buenos articulos, pero queria hacerte varias sugerencias que podras seguir o no.
La primera, es decirte que leer el codigo sobre fondo negro como tienes en esos div, es bastante molesto, lo mejor es que uses un fondo blanco o lo mas claro posible.
La segunda, es que hecho en falta un poco de orden en el menu, por ejemplo a mi me interesa Todo lo referente a Java, pero esta todo muy mezclado, quizas soy yo que no he sabido manejarme por tu web, pero creo que es poco intuitiva, deberias separar mas las categorias que tocas en tu web y ponerlas mas a la vista y que sea mas facil e intuitivo navegar por tu web. Es solo un consejo, por lo demás te felicito por tu Trabajo y te doy las gracias, porque me estas ayudando con la información que publicas. un saludo
Hola Miguel, muchas gracias por las sugerencias y nos alegra que te sea útil el contenido 🙂
La primera sugerencia del fondo del código, la tendremos muy en cuenta para futuras versiones de la web.
La segunda, hemos optado por ser simplistas con el diseño de la web para que sea agradable de leer y rápida de usar. Es cierto que algunas cosas pueden estar un poco más «escondidas», pero bastaría ir a los tags para filtrar por categorías o utilizar el buscador (si quieres todo lo de Java puedes buscarlo o ir directamente a https://jarroba.com/?s=java). Esto ya es una cuestión de diseño y arte (de ahí que existan miles de webs con diseños mejores o no tan agraciadas en opiniones externas, pero que gustan a los autores de dichas webs). Desde nuestro punto de vista no nos gustaría sobrecargar la web con links, u otros que pudieran despistar cuyo valor ya esté aportado por otros lados (aunque como dije antes estén más «escondidos»).
Agradezco infinitamente tu aporte, es un buen trabajo y una excelente recopilacion.
Aunque pasen los años las formas de implementar y resolver siguen siendo las mismas.
Saludos desde México (donde el SAT nos quiebra la cabeza).
Hola Ricardo,
no se si esto sigue operativo…pero muchas gracias por el aporte, me ha servido para hacer una practica de una asignatura de la universidad.
Por otro lado, quería que me explicaras un poco como funciona el algoritmo para obterner el array de indices ordenado (a partir de 2 vectores, uno con los numeros originales, que es una copia, y otro vector con los numeros ya ordenados en orden creciente).
Además, y si no es mucha molestia, quería pedirte que me dijeras el coste computacional de utilizar el algoritmo con arrays de n elementos; aunque creo que como hay un for y dentro un while; el for lo hará como máximo n veces y el while n tambien, por lo tanto el coste computacional creo que seria del orden de O(nxn) = O (n^2).
Muchas gracias por tu atención,
has hecho un buen trabajo y ha sido de mucha ayuda,
un saludo,
Jacobo.
muchas gracias por este genial aporte no sabes la ayuda me has ayudado saludos desde méxico
Hola, tengo una duda, llevo poquito tiempo con java y me cuesta cambiar el chip a la POO. Te quería preguntar porqué implementas esa api
y no usas arrays.sort(nombre_array) y si quieres del revés, pasandole el collections.reverseOrder. Viniendo de C en lo que tienes que picar todo
el código de cero e intentando cambiar esa filosofia a la POO (que me cuesta) teniendo esa clase, no lo consideras un chollo? para los vaguetes…
O es que no confías en alguna que otra clase ya definida.
Muchas gracias por atenderme, un saludo!!!
Hola Antonio. El mejor de los inventos es el método sort(). Aunque tiene su limitaciones, como la ordenación de arrays parejos, la ordenación de objetos en listados, etc (es decir, cosas peculiares de nuestro programa, que no se pueden generalizar como un array de enteros). Por ello a veces resulta crucial hacer nuestros propios algoritmos de ordenación.
Siempre que puedas utiliza los métodos dados en el Framwork de Java, te ahorrará mucho tiempo y esfuerzo 🙂
muchisimas gracias, de echo si lo quise descargar en donde decia «AQUI» si lo entendi, pero me mando una pagina de error, muchas gracias por los links los reviso y si aun asi no logro descargarlos yo te aviso… nuevamente muchas gracias me ayudaste bastante
hola, por mas qie untento no puedo descargar los archivos que estan al principiop en azul para visualizar el codigo completo con el cual si funcionaria, ordenr los numeros de menor a mayor visualizando su indice
Hola ARA.. No lo puse muy intuitivo los enlaces de descarga, se accedían a ellos pulsado en el testo “AQUI”. Te los pongo en el comentario sin problema:
El proyecto: https://github.com/jarroba/Ordenar-Arrays-con-sus-Indices
El JavaDoc: https://github.com/jarroba/SortArrays_1.0
De todas formas los tienes tambien en nuestra cuenta de GitHub: https://github.com/jarroba?tab=repositories
Si con esto lo sigues sin descargar nos dices y te lo hacemos llegar por otra via.
SL2