Algoritmo para desordenar un arreglo en C/C++

jueves, julio 31, 2008

Imagina que deseas implementar un algoritmo en C++ donde necesites desordenar aleatoriamente un arreglo; por ejemplo: en un juego donde utilices un mazo de cartas y debas barajarlo. El siguiente código puede ayudarte en esa tarea:

int mazo_ordenado[44];
int mazo_barajado[44];
bool usado[44];

for (int i=0; i < 44; i++)
usado[i]=false;

int index=0;
for (int i=0; i < 44; i++){
do{
index = (rand() % 44);
while (usado[index]);
mazo[i] = mazo_ordenado[index];
usado[index]=true;
}

Ahora, explicaré el código paso a paso. La intención es desordenar un arreglo de 44 elementos (puede ser de cualquier tamaño, solo basta reemplazar el 44 por el número de su elección). El arreglo ordenado lo tenemos en la variable mazo_ordenado. Luego creamos otros dos arreglo con la misma cantidad de elementos, uno llamado mazo_barajado donde almacenaremos el arreglo desordenado y otro llamado usado en donde guardaremos el estado de cada elemento del mazo original.

int mazo_ordenado[44];
int mazo_barajado[44];
bool usado[44];

La idea es recorrer en orden creciente el arreglo desordenado y depositar en cada uno de sus elementos un elemento aleatorio del arreglo ordenado. Con el arreglo de booleanos usado llevaremos la cuenta de cuáles elementos del arreglo original se han usado y cuáles no (con la finalidad de no duplicar elementos), por eso debemos inicializar todos sus elementos en false

for (int i=0; i < 44; i++)
usado[i]=false;

Usando la función rand() generamos índices aleatorios para obtener los elementos del arreglo original; pero debemos comprobar el valor de usado[indice] para saber si el elemento ha sido usado o no. Si el elemento ya está usado, el valor de usado[indice] será true y tendremos que generar otro índice hasta que consigamos uno no usado.

do{
index = (rand() % 44);
while (usado[index]);

Si no hemos usado el elemento apuntado por indice, el valor de usado[indice] será false y entonces procedemos a almacenar el elemento en el arreglo desordenado y cambiamos el valor de usado[indice] a true.

mazo[i] = mazo_ordenado[index];
usado[index]=true;

Esto debemos hacerlo para los 44 elementos del arreglo desordenado así que debe ir dentro de un for y con la respectiva inicialización de la variables:

int index=0;
for (int i=0; i < 44; i++){
do{
index = (rand() % 44);
while (usado[index]);
mazo[i] = mazo_ordenado[index];
usado[index]=true;
}

A la salida del for tendremos un arreglo desordenado listo para usar :D.

Prueben el código, agreguen unos cuantos printf para imprimir los valores de los mazos antes y después del for y comenten sus resultados. Si tienen alguna sugerencia o corrección posteenla también que será bien recibida. Espero que les haya sido de utilidad.

10 comentarios:

Narrador compulsivo dijo...

Muy útil. Muchas gracias ^^

Anónimo dijo...

mazo[i] no debería ser mazo_barajado[i] ?

Anónimo dijo...

es una buena solucion pero no es un algoritmo eficiente en tiempo. Por ejemplo: si se trata de un numero grande de elementos, para asignar los ultimos pasara mucho tiempo en el ciclo do{...}while buscando un espacio no asignado previamente.
Una mejor solucion se logra con estructura dinamicas (listas).

Anónimo dijo...

Existe um erro no código na linha
mazo[i] = mazo_ordenado[index];
correto
mazo_barajado[i] = mazo_ordenado[index];

DarKayserLeo dijo...

Perfecto para el juego de yugioh que estoy desarrollando. Gracias =)

Unknown dijo...

Me contenta que haya sido de utilidad.

Saludos

Anónimo dijo...

Muchas gracias.
Falta cerrar un corchete, el del do while.

Un saludo

iruga dijo...

Buena idea de código pero concuerdo con el otro comentario que no es nada eficiente en tiempo, ando buscando un código que haga lo mismo desordene números pero a grandes cantidades entre cien mil y dos millones, pero la probabilidad para el ultimo dígito en el caso de cien mil es de 1 en cien mil.... lo cual no me ayuda mucho, yo cree un código muy similar a este pero mi problema es el mismo a cantidades muy altas el tiempo es enorme.

Anónimo dijo...

Muchisimas Gracias amigo, si supieras lo util que me ha sido, espero poder compensarte algun dia.

Anónimo dijo...

No se define el valor aleatorio dentro del indice indicado, antes de:

mazo[i] = mazo_ordenado[index];

una solución rápida podría ser:

mazo_ordenado[index] = index;