Formas de ordenar un array en Java

java_base_web

Hola a todos, hoy os enseñare las distintas formas que tenemos para ordenar un array.

Ordenar un array es muy importante, ya sea de números o de cadenas, puede haber casos en que nos interese que los datos esten ordenados en un array. Tenemos varias formas de hacerlo, tanto con números como con cadenas:

  • Intercambio: consiste en comparar el primer valor con el resto de las posiciones posteriores, cambiando el valor de las posiciones en caso de que el segundo sea menor que el primero comparado, después la segunda posición con el resto de posiciones posteriores. Te enseñamos un ejemplo de como funciona.

ejemplo ordenación intercambio

    • Método intercambio con números:
public static void intercambio(int lista[]){

		//Usamos un bucle anidado
		for(int i=0;i<(lista.length-1);i++){
			for(int j=i+1;j<lista.length;j++){
				if(lista[i]>lista[j]){
					//Intercambiamos valores
					int variableauxiliar=lista[i];
					lista[i]=lista[j];
					lista[j]=variableauxiliar;

				}
			}
		}
	}
    • Método intercambio con cadenas:
public static void intercambioPalabras(String lista[]){

		//Usamos un bucle anidado
				for(int i=0;i<(lista.length-1);i++){
					for(int j=i+1;j<lista.length;j++){
						if(lista[i].compareToIgnoreCase(lista[j])>0){
							//Intercambiamos valores
							String variableauxiliar=lista[i];
							lista[i]=lista[j];
							lista[j]=variableauxiliar;

						}
					}
				}
	}

Veamos un ejemplo:

public class IntercambioApp {

	public static void main(String[] args) {

		final int TAMANIO=10;
		int lista[]=new int [TAMANIO];
		rellenarArray(lista);

		String lista_String[]={"americano", "Zagal", "pedro", "Tocado", "coz"};

		System.out.println("Array de números sin ordenar:");
		imprimirArray(lista);

		//ordenamos el array
		intercambio(lista);

		System.out.println("Array de números ordenado:");
		imprimirArray(lista);

		System.out.println("Array de String sin ordenar:");
		imprimirArray(lista_String);

		//ordenamos el array
		intercambioPalabras(lista_String);

		System.out.println("Array de String ordenado:");
		imprimirArray(lista_String);

	}

	public static void imprimirArray (int lista[]){
		for(int i=0;i<lista.length;i++){
			System.out.println(lista[i]);
		}
	}

	public static void imprimirArray (String lista[]){
		for(int i=0;i<lista.length;i++){
			System.out.println(lista[i]);
		}
	}

	public static void rellenarArray (int lista[]){
		for(int i=0;i<lista.length;i++){
			lista[i]=numeroAleatorio();
		}
	}

	private static int numeroAleatorio (){
		return ((int)Math.floor(Math.random()*1000));
	}

	public static void intercambio(int lista[]){

		//Usamos un bucle anidado
		for(int i=0;i<(lista.length-1);i++){
			for(int j=i+1;j<lista.length;j++){
				if(lista[i]>lista[j]){
					//Intercambiamos valores
					int variableauxiliar=lista[i];
					lista[i]=lista[j];
					lista[j]=variableauxiliar;

				}
			}
		}
	}

	public static void intercambioPalabras(String lista[]){

		//Usamos un bucle anidado
				for(int i=0;i<(lista.length-1);i++){
					for(int j=i+1;j<lista.length;j++){
						if(lista[i].compareToIgnoreCase(lista[j])>0){
							//Intercambiamos valores
							String variableauxiliar=lista[i];
							lista[i]=lista[j];
							lista[j]=variableauxiliar;

						}
					}
				}
	}
}
  • Burbuja: consiste en comparar el primero con el segundo, si el segundo es menor que el primero se intercambian los valores. Después el segundo con el tercero y así sucesivamente, cuando no haya ningún intercambio, el array estará ordenado. Lo peor de este método de ordenación, es que tiene una complejidad de O(n2) haciendo que cuanto mas valores a ordenar mayor tiempo tardara en ordenar. Te mostramos un ejemplo de como funciona:

ejemplo ordenación burbuja

    • Método burbuja para números:
public static void burbuja (int lista[]){
		int cuentaintercambios=0;
		//Usamos un bucle anidado, saldra cuando este ordenado el array
		for (boolean ordenado=false;!ordenado;){
			for (int i=0;i<lista.length-1;i++){
				if (lista[i]>lista[i+1]){
					//Intercambiamos valores
					int variableauxiliar=lista[i];
					lista[i]=lista[i+1];
					lista[i+1]=variableauxiliar;
					//indicamos que hay un cambio
					cuentaintercambios++;
				}
			}
			//Si no hay intercambios, es que esta ordenado.
			if (cuentaintercambios==0){
				ordenado=true;
			}
			//Inicializamos la variable de nuevo para que empiece a contar de nuevo
			cuentaintercambios=0;
		}
	}
    • Método burbuja para cadena:
public static void burbujaPalabras (String lista_palabras[]){
		boolean ordenado=false;
		int cuentaIntercambios=0;
		//Usamos un bucle anidado, saldra cuando este ordenado el array
		while(!ordenado){
			for(int i=0;i<lista_palabras.length-1;i++){
				if (lista_palabras[i].compareToIgnoreCase(lista_palabras[i+1])>0){
					//Intercambiamos valores
					String aux=lista_palabras[i];
					lista_palabras[i]=lista_palabras[i+1];
					lista_palabras[i+1]=aux;
					//indicamos que hay un cambio
					cuentaIntercambios++;
				}
			}
			//Si no hay intercambios, es que esta ordenado.
			if (cuentaIntercambios==0){
				ordenado=true;
			}
			//Inicializamos la variable de nuevo para que empiece a contar de nuevo
			cuentaIntercambios=0;
		}

	}

Veamos un ejemplo completo:

public class BurbujaApp {

	public static void main(String[] args) {

		final int TAMANIO=10;
		int lista[]=new int [TAMANIO];
		rellenarArray(lista);

		String lista_String[]={"americano", "Zagal", "pedro", "Tocado", "coz"};

		System.out.println("Array de números sin ordenar:");
		imprimirArray(lista);

		//ordenamos el array
		burbuja(lista);

		System.out.println("Array de números ordenado:");
		imprimirArray(lista);

		System.out.println("Array de String sin ordenar:");
		imprimirArray(lista_String);

		//ordenamos el array
		burbujaPalabras (lista_String);

		System.out.println("Array de String ordenado:");
		imprimirArray(lista_String);
	}

	public static void imprimirArray (int lista[]){
		for(int i=0;i<lista.length;i++){
			System.out.println(lista[i]);
		}
	}

	public static void imprimirArray (String lista[]){
		for(int i=0;i<lista.length;i++){
			System.out.println(lista[i]);
		}
	}

	public static void rellenarArray (int lista[]){
		for(int i=0;i<lista.length;i++){
			lista[i]=numeroAleatorio();
		}
	}

	private static int numeroAleatorio (){
		return ((int)Math.floor(Math.random()*1000));
	}

	public static void burbuja (int lista[]){
		int cuentaintercambios=0;
		//Usamos un bucle anidado, saldra cuando este ordenado el array
		for (boolean ordenado=false;!ordenado;){
			for (int i=0;i<lista.length-1;i++){
				if (lista[i]>lista[i+1]){
					//Intercambiamos valores
					int variableauxiliar=lista[i];
					lista[i]=lista[i+1];
					lista[i+1]=variableauxiliar;
					//indicamos que hay un cambio
					cuentaintercambios++;
				}
			}
			//Si no hay intercambios, es que esta ordenado.
			if (cuentaintercambios==0){
				ordenado=true;
			}
			//Inicializamos la variable de nuevo para que empiece a contar de nuevo
			cuentaintercambios=0;
		}
	}

	public static void burbujaPalabras (String lista_palabras[]){
		boolean ordenado=false;
		int cuentaIntercambios=0;
		//Usamos un bucle anidado, saldra cuando este ordenado el array
		while(!ordenado){
			for(int i=0;i<lista_palabras.length-1;i++){
				if (lista_palabras[i].compareToIgnoreCase(lista_palabras[i+1])>0){
					//Intercambiamos valores
					String aux=lista_palabras[i];
					lista_palabras[i]=lista_palabras[i+1];
					lista_palabras[i+1]=aux;
					//indicamos que hay un cambio
					cuentaIntercambios++;
				}
			}
			//Si no hay intercambios, es que esta ordenado.
			if (cuentaIntercambios==0){
				ordenado=true;
			}
			//Inicializamos la variable de nuevo para que empiece a contar de nuevo
			cuentaIntercambios=0;
		}

	}
}
  • Quicksort:  consiste en ordenar un array mediante un pivote, que es un punto intermedio en el array, es como si se ordenaran pequeños trozos del array, haciendo que a la izquierda esten los menores a ese pivote y en la derecha lo mayores a este, después se vuelve a calcular el pivote de trozos de listas. Usa recursividad. Le pasamos el array, su posición inicial y su posición final como parámetro. Tiene una complejidad de O(n log2 n), haciendo que mejore el rendimiento aun teniendo muchos valores que ordenar. Te dejo un ejemplo:

ejemplo ordenacion quicksort

También os dejo un enlace donde lo explica más gráficamente, pincha aquí para verlo.

    • Quicksort con números:
	public static void quicksort (int lista1[], int izq, int der){
		int i=izq;
		int j=der;
		int pivote=lista1[(i+j)/2];
		do {
			while (lista1[i]<pivote){
				i++;
			}
			while (lista1[j]>pivote){
				j--;
			}
			if (i<=j){
				int aux=lista1[i];
				lista1[i]=lista1[j];
				lista1[j]=aux;
				i++;
				j--;
			}
		}while(i<=j);
		if (izq<j){
			quicksort(lista1, izq, j);
		}
		if (i<der){
			quicksort(lista1, i, der);
		}
	}
    • Quicksort con cadenas:
public static void quicksortP (String lista1[], int izq, int der){
		int i=izq;
		int j=der;
		int pivote=(i+j)/2;
		do {
			while (lista1[i].compareToIgnoreCase(lista1[pivote])<0){
				i++;
			}
			while (lista1[j].compareToIgnoreCase(lista1[pivote])>0){
				j--;
			}
			if (i<=j){
				String aux=lista1[i];
				lista1[i]=lista1[j];
				lista1[j]=aux;
				i++;
				j--;
			}
		}while(i<=j);
		if (izq<j){
			quicksortP(lista1, izq, j);
		}
		if (i<der){
			quicksortP(lista1, i, der);
		}
	}

Veamos un ejemplo completo:

public class QuicksortApp {

	public static void main(String[] args) {

		final int TAMANIO=10;
		int lista[]=new int [TAMANIO];
		rellenarArray(lista);

		String lista_String[]={"americano", "Zagal", "pedro", "Tocado", "coz"};

		System.out.println("Array de números sin ordenar:");
		imprimirArray(lista);

		//ordenamos el array
		quicksort(lista, 0, lista.length-1);

		System.out.println("Array de números ordenado:");
		imprimirArray(lista);

		System.out.println("Array de String sin ordenar:");
		imprimirArray(lista_String);

		//ordenamos el array
		quicksortP(lista_String, 0, lista_String.length-1);

		System.out.println("Array de String ordenado:");
		imprimirArray(lista_String);

	}

	public static void imprimirArray (int lista[]){
		for(int i=0;i<lista.length;i++){
			System.out.println(lista[i]);
		}
	}

	public static void imprimirArray (String lista[]){
		for(int i=0;i<lista.length;i++){
			System.out.println(lista[i]);
		}
	}

	public static void rellenarArray (int lista[]){
		for(int i=0;i<lista.length;i++){
			lista[i]=numeroAleatorio();
		}
	}

	private static int numeroAleatorio (){
		return ((int)Math.floor(Math.random()*1000));
	}

	public static void quicksort (int lista1[], int izq, int der){
		int i=izq;
		int j=der;
		int pivote=lista1[(i+j)/2];
		do {
			while (lista1[i]<pivote){
				i++;
			}
			while (lista1[j]>pivote){
				j--;
			}
			if (i<=j){
				int aux=lista1[i];
				lista1[i]=lista1[j];
				lista1[j]=aux;
				i++;
				j--;
			}
		}while(i<=j);
		if (izq<j){
			quicksort(lista1, izq, j);
		}
		if (i<der){
			quicksort(lista1, i, der);
		}
	}

	public static void quicksortP (String lista1[], int izq, int der){
		int i=izq;
		int j=der;
		int pivote=(i+j)/2;
		do {
			while (lista1[i].compareToIgnoreCase(lista1[pivote])<0){
				i++;
			}
			while (lista1[j].compareToIgnoreCase(lista1[pivote])>0){
				j--;
			}
			if (i<=j){
				String aux=lista1[i];
				lista1[i]=lista1[j];
				lista1[j]=aux;
				i++;
				j--;
			}
		}while(i<=j);
		if (izq<j){
			quicksortP(lista1, izq, j);
		}
		if (i<der){
			quicksortP(lista1, i, der);
		}
	}
}
  • Método sort de java.util.Arrays: para ejecutarlo escribimos Arrays.sort(array a ordenar); simplemente insertamos como parámetro el array que queremos ordenar. Tiene varios métodos para distintos tipos. Te mostramos un ejemplo practico:
import java.util.Arrays;
public class sortApp {

	public static void main(String[] args) {

		final int TAMANIO=10;
		int lista[]=new int [TAMANIO];
		rellenarArray(lista);

		String lista_String[]={"americano", "Zagal", "pedro", "Tocado", "coz"};

		System.out.println("Array de números sin ordenar:");
		imprimirArray(lista);

		//ordenamos el array
		Arrays.sort(lista);

		System.out.println("Array de números ordenado:");
		imprimirArray(lista);

		System.out.println("Array de String sin ordenar:");
		imprimirArray(lista_String);

		//ordenamos el array, ordenara primero las mayusculas y luego las minusculas
		Arrays.sort(lista_String);

		System.out.println("Array de String ordenado:");
		imprimirArray(lista_String);
	}

	public static void imprimirArray (int lista[]){
		for(int i=0;i<lista.length;i++){
			System.out.println(lista[i]);
		}
	}

	public static void imprimirArray (String lista[]){
		for(int i=0;i<lista.length;i++){
			System.out.println(lista[i]);
		}
	}

	public static void rellenarArray (int lista[]){
		for(int i=0;i<lista.length;i++){
			lista[i]=numeroAleatorio();
		}
	}

	private static int numeroAleatorio (){
		return ((int)Math.floor(Math.random()*1000));
	}
}

Espero que os sea de ayuda. Si tenéis dudas, preguntad. Estamos para ayudarte.

Etiquetas

6 comments

  1. Madre de Dios!! supongo que para los expertos esto será música celestial… yo, pobre y triste analfabeto de las ciencias informáticas, me quedo como estaba. De todas formas y como miembro del club dejo el comentario y paso a otra página… quizá me entere de algo en ella.
    Traffic-Club
    RjL-Cine de Balcón
    Saludos,
    RjLebrancón

  2. Como el compañero RjLebrancón, no puedo hacer ningún comentario de valor ante tal despliegue de fórmulas y códigos, pero te saludo como miembro de Traffic-Club desde “Millas y birras”

  3. Podrías explicarme teniendo 3 vectores independientes, como ordenarlos con quicksort de forma que si ordenas por nombre coincida con su apellido y su dni y si ordenas por DNI coincida con su nombre etc,,,,

  4. Lo mas fácil es hacer un array que contenga objetos, que en tu caso tendría apellido, DNI y nombre, así al cambiar se cambiarían los 3 datos que necesitas que en realidad son 1.

    Otra forma, algo mas complicada,seria modificando el método para que aceptase una matriz en lugar de un vector y personalizarlo según tu gusto.

    También puedes pasar los 3 arrays y a la hora del intercambio que también intercambie esas posiciones.

    Yo te recomendaría la primera opción.

    Si necesitas algo mas, puedes comentarlo por aqui o mandar un mensaje a administrador@discoduroderoer.es

  5. Hola amigo, excelente explicacion.
    Pero creo que el grafico esta mal, el pivote en la segunda llamada no es 21 si no es 15.
    La lista en la primera pasada queda: 24,21,15,46,65,88,75,85,76,99,84,79
    La lista se divide en dos:
    24,21,15,46,65
    88,75,85,76,99,84,79
    Si divides el 4 que es el valor que tiene i te dara 2, la posicion lista[2]=15
    Lo puedes comprobar haciendo un:
    int pivote=lista1[(i+j)/2];
    System.out.println(“Pivote: “+pivote);

    Pivote: 65
    Pivote: 15
    Pivote: 24
    Pivote: 46
    Pivote: 76
    Pivote: 76
    Pivote: 99
    Pivote: 88
    Pivote: 84

    O tal vez este haciendo algo mal yo, no me quiero quedar con la duda.
    Por cierto buen pagina la tuya te felicito!

Deja un comentario

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