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 ;).

Comparte esta entrada en:
Safe Creative #1401310112503
Ordenar Arrays en Java (con sus indices) por "www.jarroba.com" esta bajo una licencia Creative Commons
Reconocimiento-NoComercial-CompartirIgual 3.0 Unported License.
Creado a partir de la obra en www.jarroba.com

8 comentarios en “Ordenar Arrays en Java (con sus indices)”

  1. 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).

  2. 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.

  3. 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!!!

    1. 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 🙂

  4. 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

  5. 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

    1. 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

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Uso de cookies

Este sitio web utiliza cookies para que usted tenga la mejor experiencia de usuario. Si continúa navegando está dando su consentimiento para la aceptación de las mencionadas cookies y la aceptación de nuestra política de cookies

ACEPTAR
Aviso de cookies