Minicontribución: desordenar y oredenar listas

[fzp]

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 (java) [Seleccionar] Expandir

import java.util.Scanner;

public class DesordenarOrdenarLista {
public static void main(String[] args) {
int numElementos;
int [] lista;
int numAzar;
int numSup; // para elegir numAzar entre 0 y numSup - 1
int var = 0;// guarda temporalmente un elemento de lista[]

Scanner teclado;
teclado = new Scanner(System.in);
System.out.println ("Introducir longitud de la lista");
numElementos = teclado.nextInt ();

lista = new int[numElementos];
for (int i = 0; i < numElementos; i++) {
lista[i] = i;
}
System.out.println ("Lista ordenada:");
for (int i = 0; i < numElementos; i++) {
System.out.print (lista[i] + "    ");
}
System.out.println ("");

// algoritmo de desordenación
numSup = numElementos;
for (int i = 0; i < numElementos - 1;i++) {
numAzar = (int) (Math.random() * numSup);
var = lista[numAzar];
for (int j = numAzar; j < numElementos - 1; j++) {
lista[j] = lista[j+1];
}
lista[numElementos - 1] = var;
numSup--;
}
// fin de algoritmo de desordenación

System.out.println ("Lista desordenada:");
for (int i = 0; i < numElementos; i++) {
System.out.print (lista[i] + "    ");
}
System.out.println ("");


// algoritmo de ordenación
for (;;) {
char flag = 0;
for (int i = 0; i < numElementos - 1; i++) {
if (lista[i] > lista[i+1]) {
var = lista[i];
lista[i] = lista[i+1];
lista[i+1] = var;
flag = 1;
}
}
if (flag == 0)
break;
}
// fin de algoritmo de ordenación

System.out.println ("Lista nuevamente ordenada:");
for (int i = 0; i < numElementos; i++) {
System.out.print (lista[i] + "    ");
}
System.out.println ("");
}
}



[Serapis]

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

[fzp]

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 (java) [Seleccionar] Expandir

// algoritmo de ordenación
for (int i = 0; i < numElementos - 1; i++) {
int j = i + 1;
while (j < numElementos) {
if (lista[i] > lista[j]) {
var = lista[i];
lista[i] = lista[j];
lista[j] = var;
j = i + 1;
}
else j++;
}
}

// fin de algoritmo de ordenación




[Serapis]

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:

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:

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.

[fzp]

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?

[Serapis]

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.