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.
-
- Método intercambio con números:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
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:
-
- Método burbuja para números:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
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:
También os dejo un enlace donde lo explica más gráficamente, pincha aquí para verlo.
-
- Quicksort con números:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
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.
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
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»
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,,,,
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
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!
Creen que puedan explicarme un poco el primer metodo de ordenar valores aleatorios?, solo la parte donde los ordenan
hello:):):):) what is wrong with this code to order a list of number?????
static int ordenarLista (ArrayList listaNum) {
int temp;
for (int i = 0; i < listaNum.size(); i++)
{
for (int j = i + 1; j listaNum.get(j))
{
temp = listaNum.get(i);
listaNum.get(i) = listaNum.get(j);
temp = listaNum.get(j);
}
}
}
return temp;
}