Mélanger un tableau rapidement.

Voir version :

Pas de dépendances

Télécharger :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

void Melanger(int* tab,int nb)
{
    int i,nb2;
    nb2 = nb;
    for(i=0;i<nb;i++)
    {
        int tmp;
        int index = rand()%nb2;
        tmp = tab[index];
        tab[index] = tab[nb2-1];
        tab[nb-i-1] = tmp;
        nb2--;
    }
}

void Remplir(int* tab,int taille)
{
    int i;
    for(i=0;i<taille;i++)
        tab[i] = i/4;
}

void Afficher(int tab[],int taille)
{
    int i;
    for(i=0;i<taille;i++)
        printf("%d\t",tab[i]);
}


int main()
{
    int taille = 100;
    int* tab = malloc(taille*sizeof(int));
    srand(time(NULL));
    Remplir(tab,taille);
    Melanger(tab,taille);
    Afficher(tab,taille);
    free(tab);
    return 0;
}

	Un petit exemple de mélange de tableau.

	Je crée un tableau, ici de 100 éléments.
	Dans la fonction Remplir, je mets quatre 0, quatre 1, quatre 2, etc...
	Je pourrais mettre ce que je veux.

	Puis j'appelle ma fonction Melanger.

	A la fin, lors de l'affichage, le tableau est mélangé, mais j'ai gardé, dans le désordre, mes quatre 0, quatre 1, ....

	La coeur du programme est la fonction Melanger. Elle s'inspire de l'exemple précédent, 
	mais optimise en l'allouant pas un tableau supplémentaire.

	L'idée va être de choisir un index aléatoirement dans le tableau source, de ranger la valeur correspondante dans le tableau
	final.

	L'astuce de l'économie du tableau vient du fait qu'après chaque choix, on va réduire la taille du tableau "source" de 1,
	ce qui créera une place pour le tableau final, qui sera ainsi le même tableau remplit de la fin vers le début.

	Voici un petit exemple avec des lettres (éviter la confusion entre index et valeurs.

	Je veux mélanger :

	A B C D E F

	Première itération, je choisis un index au hasard, mettons 3.
	Donc je garde le "D" d'index 3 dans tmp.

	Cela me donne :
	A B C . E F

	Or, on ne fera pas de trou : pour éviter ça, on prend le dernier élément et on le met à la place :

	A B C F E .

	Une case s'est créée, ça tombe bien puisque j'ai un "D3 à placer.

	j'obtiens :

	A B C F E|D

	J'ai volontairement mis une cassure (qui est mon nb2), a gauche, le tableau ou tirer des éléments, à droite le résultat

	Je continue :

	A B C F E|D  --> Je choisis l'index 1 "B"
	A E C F|B D  --> Je choisis l'index 0 "A"
	F E C|A B D  --> Je choisis l'index 2 "C" (ici, échanger le dernier élément avec le dernier ne change rien)
	F E|C A B D  --> Je choisis l'index 0 "F"
	E|F C A B D  --> Je choisis l'index 0 "E" (obligé)
	E F C A B D

	Voila mon tableau mélangé.

	De la doc si besoin :
	http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle