Discussion :

[Rostov]

Bonjour. Je dois réaliser un programme qui trie un tableau de char avec 3 threads, plus un thread qui affiche l'état d'avancement du tri. Je comprends pas bien comment faire pour que les threads trie chacun une partie du tableau. Merci pour vos réponses.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
#include <pthread.h>
#include <stdio.h>
#include <time.h>
#include <signal.h>
#include <semaphore.h>
#include <unistd.h>
//#include <Generateur.h>
#define M 100000000
#define M1 10000
#define B 31415821
#define C 55
#define C_1 C-1
#define D 23
static int alea[C];
static int j=0;
 
int mult(int p, int q) {
int p1, p0, q1, q0;
p1 = p/M1;
p0 = p%M1;
q1 = 1/M1;
q0 = q%M1;
return (((p0*q1+p1*q0)%M1)*M1+p0*q0)%M;
}
 
void init_alea(int germe) {
	alea[0] = germe;
	j = 0;
	while (j<C_1) {
		j++;
		alea[j] = (mult(B,alea[alea[j-1]])+1)%M;
	}
}
 
int alea_int(int plage){
	int res;
	j=(j+1)%C;
	alea[j]=(alea[(j+D)%C]+alea[(j+C_1)%C])%M;
	res = ((alea[j]/M1)*plage)/M1;
	return res;
}
 
#define	MAX 10
#define TRUE 1
#define FALSE 0
 
typedef struct {
	int id_th;
	pthread_t p_th;
}pth_descr;
sem_t mutex, synchro;
int tab_sc[29];
int tab_Sem[29];
void init (){
int i;
	for (i=0;i<=30;i++){ 
			tab_sc[i]=1;
		if ((i>9)&&(i<11)){
				tab_sc[i]=2;
		}
		if((i>19)&&(i<21)){
			tab_sc[i]=2;
		}
	}
}
 
int main(void) {
int test;
	init();
	printf("%i", &tab_sc[5]);
	//init_alea(97);
	//test=alea_int(97);
	return 0;
}
 
void tri_a_bulle(int t[], int const n)
{
 	int j   = 0; /* Variable de boucle */
 	int tmp = 0; /* Variable de stockage temporaire */
 
	/* BoolÈen marquant l'arrÍt du tri si le tableau est ordonnÈ */
	int en_desordre = TRUE; 
	/* Boucle de rÈpÈtition du tri et le test qui
	 arrÍte le tri dËs que le tableau est ordonnÈ(en_desordre=FALSE) */
	while(en_desordre)
	{
		/* Supposons le tableau ordonnÈ */
		en_desordre = FALSE;
		/* VÈrification des ÈlÈments des places j et j+1 */
		for(j = 0 ; j < n- 1 ; j++)
		{
			/* Si les 2 ÈlÈments sont mal triÈs */
			if(t[j] > t[j+1])
			{
				/* Inversion des 2 ÈlÈments */
 				tmp = t[j+1];
 				t[j+1] = t[j];
 				t[j] = tmp;
 
 				/* Le tableau n'est toujours pas triÈ */
				en_desordre = TRUE;
 			}
		}
	}
}

[Lavock]

Pour un tri multi-threadé, je dirai sans hésiter de faire un quick-sort. Pour le nombre de thread limité, ça me semble embêtant tout de même.

Sinon, il tu peux jouer avec les mutex et un tri shell.

Si tu tiens au tri à bulle, il faut des case de débordement (commune au 3 threads), contrôlées par des mutex une fois de plus.

[Rostov]

Merci beaucoup pour la réponse.