elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Tutorial básico de Quickjs


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Java
| | | |-+  Minicontribución: desordenar y oredenar listas
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Minicontribución: desordenar y oredenar listas  (Leído 4,236 veces)
fzp

Desconectado Desconectado

Mensajes: 130


Ver Perfil
Minicontribución: desordenar y oredenar listas
« en: 12 Julio 2021, 11:17 am »

Una mini-contribución muy tonta, pero bueno, igual algún dia le sirve a alguien para algo.

Son algoritmos para desordenar y ordenar números naturales, pero como esos números a su vez pueden ser subíndices de listas, arreglos, vectores, tuplas... o como quiera que se les llame, pueden servir para desordenar/ordenar otras cosas.

Por ejemplo ordenar listas de palabras, de entradas de datos, etc.

En cuanto a desordenar, normalmente para lo que sirven es para simular cosas al azar. Por ejemplo un bingo, o cualquier lotería. O, por ejemplo, si se tiene un arreglo de 52 elementos correspondientes a una baraja, si se desordenan los subíndices del arreglo se desordena el arreglo y se simula el barajamiento (vaya palabro, no sé si existe). O un arreglo de 28 elementos correspondientes a las fichas de dominó, al desordenar los subíndices se simula el "meneillo" de las fichas antes de jugar.

También se podrían simular cambios al azar para juegos de recorrido de itinerario con "incidentes" al azar. Por ejemplo, supongamos que queremos hacer un "Juego de la Oca" donde los "incidentes" (la posada, el puente, la calavera, las ocas...) no estén siempre en el mismo lugar sino que en cada nuevo juego se distribuyan en el itinerario de diferente manera, se podría usar.

Explico brevemente de palabra los algoritmos (no descubro las Américas, todo el mundo los conocerá).

DESORDENAR: en cada pasada se toma un elemento al azar de los que van quedando. Al principio se elige entre todos. El elemento elegido se extrae de la lista almacenándolo temporalmente en una variable. Se "corre" toda la lista desde el elemento seleccionado hasta el final. Si imaginamos la lista de elementos en horizontal, con el elemento inicial a la izquierda y el final a la derecha, pues desde el elemento seleccionado al azar y hacia la derecha se pasa cada elemento un lugar hacia la izquierda. Y luego se coloca el elemento extraído, almacenado temporalmente en una variable, en el último lugar (en el el último de la derecha). Ahora se ddisminuye en una unidad el nº de elementos a sortear ( ya solamente se sortea entre los elementos que van quedando a la izquierda) y se repite el proceso hasta llegar a que sólo quede un elemento a la izquierda y ya todos estarán desordenados.

ORDENAR: se va recorriendo la lista de izquierda a derecha, comparando cada elemento "i" con el siguiente "i + 1", cuando se encuentra que un elemento "i" es mayor que el siguiente "i + 1" (si es ordenar de menor a mayor; si fuera de mayor a menor la comparación sería que "i" fuese menor que "i + 1") se intercambian de lugar. Antes de iniciar el recorrido se pone una bandera (flag) que se cambia cuando se produce un intercambio de posiciones. El bucle es -en principo- infinito, sin condiciones, pero cuando la bandera no ha cambiado (no se ha producido ningún intercambio de posiciones) es que ya todos los elementos han quedado ordenados, y se sale del bucle.

Lo dejo todo den un programa en Java que, primero pide el nº de elementos que tendrá la lista, construye la lista de números naturales desde 0 hasta el ingresado - 1, e imprime la lista inicial ordenada. Luego la desordena e imprime la lista desordenada, y posteriromente la vuelve a ordenar e imprime la lista nuevamente ordenada. He señalado en el mini-programita los algoritmos de desordenación/ordenación.

Código
  1. import java.util.Scanner;
  2.  
  3. public class DesordenarOrdenarLista {
  4. public static void main(String[] args) {
  5. int numElementos;
  6. int [] lista;
  7. int numAzar;
  8. int numSup; // para elegir numAzar entre 0 y numSup - 1
  9. int var = 0;// guarda temporalmente un elemento de lista[]
  10.  
  11. Scanner teclado;
  12. teclado = new Scanner(System.in);
  13. System.out.println ("Introducir longitud de la lista");
  14. numElementos = teclado.nextInt ();
  15.  
  16. lista = new int[numElementos];
  17. for (int i = 0; i < numElementos; i++) {
  18. lista[i] = i;
  19. }
  20. System.out.println ("Lista ordenada:");
  21. for (int i = 0; i < numElementos; i++) {
  22. System.out.print (lista[i] + "    ");
  23. }
  24. System.out.println ("");
  25.  
  26. // algoritmo de desordenación
  27. numSup = numElementos;
  28. for (int i = 0; i < numElementos - 1;i++) {
  29. numAzar = (int) (Math.random() * numSup);
  30. var = lista[numAzar];
  31. for (int j = numAzar; j < numElementos - 1; j++) {
  32. lista[j] = lista[j+1];
  33. }
  34. lista[numElementos - 1] = var;
  35. numSup--;
  36. }
  37. // fin de algoritmo de desordenación
  38.  
  39. System.out.println ("Lista desordenada:");
  40. for (int i = 0; i < numElementos; i++) {
  41. System.out.print (lista[i] + "    ");
  42. }
  43. System.out.println ("");
  44.  
  45.  
  46. // algoritmo de ordenación
  47. for (;;) {
  48. char flag = 0;
  49. for (int i = 0; i < numElementos - 1; i++) {
  50. if (lista[i] > lista[i+1]) {
  51. var = lista[i];
  52. lista[i] = lista[i+1];
  53. lista[i+1] = var;
  54. flag = 1;
  55. }
  56. }
  57. if (flag == 0)
  58. break;
  59. }
  60. // fin de algoritmo de ordenación
  61.  
  62. System.out.println ("Lista nuevamente ordenada:");
  63. for (int i = 0; i < numElementos; i++) {
  64. System.out.print (lista[i] + "    ");
  65. }
  66. System.out.println ("");
  67. }
  68. }
  69.  
  70.  


En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.348


Ver Perfil
Re: Minicontribución: desordenar y oredenar listas
« Respuesta #1 en: 14 Julio 2021, 02:18 am »

Hace 6 o 7 años, cree este artículo en wikipedia, porque estaba harto de ver determinadas chapuzas con malas explicaciones y peores implementaciones.
(por ejemplo eso de tener un flag (¿para descubrrir qué...?), sobra, como sobra ese bucle interno)...

https://es.wikipedia.org/wiki/Algoritmo_de_Fisher-Yates


En línea

fzp

Desconectado Desconectado

Mensajes: 130


Ver Perfil
Re: Minicontribución: desordenar y oredenar listas
« Respuesta #2 en: 15 Julio 2021, 13:25 pm »

Aquí dejo otro algoritmo para la ordenación. En el anterior había un bucle que se ejecutaba de forma indefinida y dentro de ese otro bucle que recorría la lista de principio a fin cambiando las posiciones de dos elementos que estuvieran desordenados (uno mayor que otro), realizando un sólo cambio por pasada y volviendo a recorrer la lista entera. En ese método había que detectar expresamente la forma de salir del bucle, lo que se hacia cuando en una pasada de lista no se hubiese producido ningún intercambio de elementos, lo que indicaba que la lista ya estaba ordenada. Para lo cual se usaba una bandera.

Este otro algoritmo es algo distinto. También hay dos bucles. Pero el primer bucle, con índice i no es indifinido, se ejecuta desde el primer elemento de la lista al último. Es así porque cuando cuando se termina un ciclo de bucle el elemento de la lista i ya está en su posición ordenada. Por lo tanto cuando se comienza un ciclo i+1 todos los elementos de la lista 0,1...,i están ya ordenados.

Así pues el segundo índice j se moverá solamente entre i+1 y el final de la lista. La segunda diferencia es que mientras antes se recorría la lista varias veces haciendo un sólo cambio cada vez, ahora el segundo bucle cuando encuentra dos elementos desordenados no solamente hace los cambios y sigue hasta el final de la lista, sino que vuelve a la posición i+1 de la lista, y vuelve a ir desde i+1 hasta el final o hasta que encuentre otro par desordenado. De esta forma, cuando j llegue al final de la lista querrá decir que no no hubo intercambio de posiciones desde la última vez, y que, por tanto, el elemento i ya está en su lugar y se puede pasar al i+1 sin necesidad de detectar expresamente con una bandera que la lista está ordenada, pues cuando i llegue al último elemento, todos los elementos anteriores están ya ordenados e i es el último.

El código de este otro algoritmo es:

Código
  1. // algoritmo de ordenación
  2. for (int i = 0; i < numElementos - 1; i++) {
  3. int j = i + 1;
  4. while (j < numElementos) {
  5. if (lista[i] > lista[j]) {
  6. var = lista[i];
  7. lista[i] = lista[j];
  8. lista[j] = var;
  9. j = i + 1;
  10. }
  11. else j++;
  12. }
  13. }
  14.  
  15. // fin de algoritmo de ordenación
  16.  
  17.  
  18.  
En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.348


Ver Perfil
Re: Minicontribución: desordenar y oredenar listas
« Respuesta #3 en: 15 Julio 2021, 19:59 pm »

Bravo  ;-) ;-) ;-) , acabas de descubrir el ordenamiento por el método de burbuja el más ineficiente de todos...
...pero además has realizado una implementación muy, muy, muy deficiente.
Intenta generar y ordenar una lista con solo 1000 elementos (o añade algún cero más)... y comprobarás lo lento que es.

Tú tienes esto:
Citar
Si (lista(i) > lista(J))
    var = lista(i)
    lista(i) = lista(j)
    lista(j) = var
             
     j = (i + 1)
Sino           
     j = (j + 1)
Fin si           
...que hace que ese 'j=i+1' lo haga excesivamente (10-100 veces más) lento, de lo que por sí ya es el algoritmo de burbuja.

Debieras remplazarlo por esto:
Citar
Si (lista(i) > lista(J))
    var = lista(i)
    lista(i) = lista(j)
    lista(j) = var
             
     //j = (i + 1)
Fin si             
j = (j + 1)         
Es poca la diferencia en el código, pero mucho la diferencia de eficiencia. Con 10 o 20 elementos no lo notas, cuando son 1000, se volverá intolerable, porque la ineficiencia es exponencial.


Por favor, abstente de poner código mediocre... solo conseguirás llevar la ineficiencia a otras personas. Date el plazo de aprender bien... Ahora solo sabes andar, ya aprenderás a correr.
En línea

fzp

Desconectado Desconectado

Mensajes: 130


Ver Perfil
Re: Minicontribución: desordenar y oredenar listas
« Respuesta #4 en: 15 Julio 2021, 20:15 pm »

Por favor, abstente de poner código mediocre... solo conseguirás llevar la ineficiencia a otras personas. Date el plazo de aprender bien... Ahora solo sabes andar, ya aprenderás a correr.

Pero entonces nadie me ayudaría. Ya sabes, no se hacen tareas. Si no pongo mi propio código, ¿cómo alguien como tú podría tan amablemente corregirme?
En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.348


Ver Perfil
Re: Minicontribución: desordenar y oredenar listas
« Respuesta #5 en: 15 Julio 2021, 20:33 pm »

A ver, una cosa es que:

A - Tengas un problema... donde expones tu código y declaras que problemas tienes en el mismo... y otra cosa es
B - Proveer 'código' como si fueran soluciones eficaces. ...tu mismo lo llamas contribución.
Pero ciertamente no contribuye más que a cierta confusión para otros principiantes que no tienen capacidad para valorar la 'calidad' del código expuesto.

Si tienes algún problema aclara qué problema tienes y pon el código que has hecho hasta el momento y con gusto cualquiera del foro te asistirá con las dudas o problemas que haya.
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Ayuda Acerca De Listas y Listas Circulares (Revienta Memoria :S)
Programación C/C++
Gerik 0 5,096 Último mensaje 12 Septiembre 2010, 01:49 am
por Gerik
[Reto Bash] desordenar cadena, scrabble string
Scripting
-Myx- 1 3,951 Último mensaje 7 Enero 2022, 16:44 pm
por itsy
[Resuelto] Duda javascript: desordenar array con bucle
Desarrollo Web
masterkein 2 4,292 Último mensaje 13 Mayo 2018, 02:10 am
por Serapis
MOVIDO: Duda javascript: desordenar array con bucle
Programación General
Eleкtro 0 2,336 Último mensaje 12 Mayo 2018, 22:14 pm
por Eleкtro
desordenar una frase sin repetir palabras en C
Programación C/C++
itsy 3 3,228 Último mensaje 7 Enero 2022, 22:52 pm
por Serapis
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines