Tri de tableau semi-aleatoire

Tri de tableau semi-aleatoire - Algo - Programmation

Marsh Posté le 22-05-2006 à 20:58:22    

Je cherche, je ne sais pas si ca existe en fait (meme comme je ne voudrais pas reinventer la roue :o ), un algo qui trierait un tableau en ayant entré au prealablement un entier. En clair ca serait un tri random sauf que moi je precise le random :D
Donc avec un meme entier et un meme tableau, on retrouve le meme tableau trié au final. Je ne sais pas si vous m'avez compris ?
Je cherche pas un simple decalage a droite ou a gauche, sinon je l'aurais fais moi meme. :)
 
Voila, si jamais vous avez deja vu ca, ou si vous avez une idée de comment s'y prendre.


Message édité par Tounet le 22-05-2006 à 20:59:09

---------------
Les hommes n'acceptent le changement que dans la nécessité et ils ne voient la nécessité que dans la crise.
Reply

Marsh Posté le 22-05-2006 à 20:58:22   

Reply

Marsh Posté le 22-05-2006 à 21:19:08    

j'ai rien compris [:moule_bite]

Reply

Marsh Posté le 22-05-2006 à 21:54:39    

Imagine un appel de fonction du genre rand_tab(entier,tableau) qui te renvois un tableau classé differement, mais qui te renvoir tjrs le meme tableau si tes parametres de depart sont les memes. Je suis clair la ?


---------------
Les hommes n'acceptent le changement que dans la nécessité et ils ne voient la nécessité que dans la crise.
Reply

Marsh Posté le 22-05-2006 à 22:06:29    

bha tu utilise l'entier donné en argument dans srand() comme graine, puis tu fais ton algo de mélange à coup de rand() ...


---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.
Reply

Marsh Posté le 23-05-2006 à 09:56:26    

ca revient à calculer le hashcode de chacune des données du tableau et avec ça tu trouveras l'indice du tableau où les ranger. Tu gères les collisions avec l'algorithme de "linear probing".

Reply

Marsh Posté le 23-05-2006 à 10:43:32    

J'ai trouve un truc pas mal qui marche plutot bien.
Le seul truc c'est que le tableau ne doit pas etre plus grand que le RAND_MAX. Mais bon de toute facon je ne comptais pas faire ca avec des tableaux immenses.
 

Code :
  1. srand(x)
  2. for (i = 0; i < nb_car - 1; i++)
  3. {
  4.      j = i + rand() / (RAND_MAX / (nb_car - i) + 1);
  5.      tmp = tab[j];
  6.      tab[j] = tab[i];
  7.      tab[i] = tmp;
  8. }


Message édité par Tounet le 23-05-2006 à 10:45:10

---------------
Les hommes n'acceptent le changement que dans la nécessité et ils ne voient la nécessité que dans la crise.
Reply

Marsh Posté le 23-05-2006 à 10:53:31    

en utilisant du rand(), j'ai du mal à voir comment tu peux "trier" un même tableau 2 fois de suite de la même façon  :heink:

Reply

Marsh Posté le 23-05-2006 à 10:56:58    

Reply

Marsh Posté le 23-05-2006 à 11:25:30    

Giz a écrit :

en utilisant du rand(), j'ai du mal à voir comment tu peux "trier" un même tableau 2 fois de suite de la même façon  :heink:


 
T'as rate la 1ere ligne du programme :o


---------------
Les hommes n'acceptent le changement que dans la nécessité et ils ne voient la nécessité que dans la crise.
Reply

Marsh Posté le 23-05-2006 à 12:01:04    

avec srand() tu réinitialises ta suite aléatoire...donc ton rand() ne générera jamais la même suite de chiffre dans ta boucle. Avec rand() tout seul OK. Mais la suite changera au prochain rédémarrage de ton PC. Franchement avec du rand(), je vois pas comment ça peut marcher. Sinon le hashCode, à quoi ça sert ? :sarcastic:


Message édité par Giz le 23-05-2006 à 12:01:48
Reply

Marsh Posté le 23-05-2006 à 12:01:04   

Reply

Marsh Posté le 23-05-2006 à 12:09:08    

T'as pas bien compris l'utilisation de srand. :o
Srand initialise une suite aleatoire a l'aide d'un entier, mais si tu passes tjrs le meme entier a srand, ta suite aleatoire reste la meme derriere.
C'est d'ailleurs pour ca quand on veut generer qq chose qui se rapproche d'un vrai nombre aleatoire, on utilise un srand(time(NULL)).
 
Ne t'inquiete pas j'ai teste et ca marche tres bien. :)


---------------
Les hommes n'acceptent le changement que dans la nécessité et ils ne voient la nécessité que dans la crise.
Reply

Marsh Posté le 23-05-2006 à 12:33:42    

ha bon...ma foi. Et ça marche même quand tu redémarre le PC ? (tu auras la même suite à chaque fois) :??:

Reply

Marsh Posté le 23-05-2006 à 12:34:11    

OUI, lis le man ptin :o


---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.
Reply

Marsh Posté le 23-05-2006 à 12:38:09    

merde alors, je savais pas ça.
 
EDIT : pourquoi alors on n'utiliserai pas cette méthode pour générer un hashCode ?


Message édité par Giz le 23-05-2006 à 12:46:13
Reply

Marsh Posté le 23-05-2006 à 12:59:22    

un hashcode, c'est a dire ? genre du md5 ou du SHA ?


---------------
Les hommes n'acceptent le changement que dans la nécessité et ils ne voient la nécessité que dans la crise.
Reply

Marsh Posté le 23-05-2006 à 13:41:50    

Ouai non en fait ça changera rien du tout.


Message édité par Giz le 23-05-2006 à 13:49:12
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed