Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <unistd.h>
- #include <pthread.h>
- #include <sys/types.h>
- #include <time.h>
- #define MAXN 100005
- #define THMAX 5
- #define min(x, y) (x <= y ? x : y)
- //array que vai ser ordenado
- int arr[MAXN];
- //mutex para tratar de regios criticas
- pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
- int flag = 0;
- //pilha de threads disponiveis atualmente
- int stack[THMAX], top;
- typedef struct{
- int a, b, x, y, idx;
- }merge_range;
- void* merge(void* data){
- //Pego os intervalos em que eu vou juntar (merge)
- merge_range *args = data;
- int l = args-> a, r = args->b, i = args->x, j = args->y;
- int val = args -> idx;
- //Variaveis auxiliares
- int ord[MAXN], k, li = l, ls = j;
- //merge
- for(k = l; l <= r && i <= j; k++){
- if(arr[l] <= arr[i]) ord[k] = arr[l++];
- else ord[k] = arr[i++];
- }
- while(l <= r) ord[k++] = arr[l++];
- while(i <= j) ord[k++] = arr[i++];
- //atualizo meu array
- for(; li <= ls; li++) arr[li] = ord[li];
- //região critica (variavel global), atualizo minha pilha de threads disponiveis
- pthread_mutex_lock(&mtx);
- stack[++top] = val;
- pthread_mutex_unlock(&mtx);
- return NULL;
- }
- void merge_sort(int n){
- //variaveis auxiliares
- int i, j, qtd = 0, aux;
- //threads
- pthread_t thr[THMAX];
- //array que vai guardar a task de cada thread em um instante da execução
- merge_range tmp[THMAX];
- //Inicializo minha pilha de threads
- for(i = 0; i < THMAX; i++) stack[i] = i;
- top = THMAX - 1;
- for(i = 1; i <= n; i <<= 1){
- for(j = 0; j + i <= n; j += (i << 1) ){
- //enquanto eu nao tiver threads disponiveis não faço nada
- while(top < 0);
- //Pego o indice da proxima thread disponivel
- aux = stack[top];
- //Inicializo os ranges que a thread ficara responsavel em dar o merge
- tmp[ aux ].a = j; tmp[ aux ].b = j + i - 1;
- tmp[ aux ].x = min(tmp[ aux ].b + 1, n - 1); tmp[aux].y = min(tmp[aux].x + i - 1, n - 1);
- //Guardo o seu indice para ser recolado na pilha
- tmp[aux].idx = stack[aux];
- //O trabalho começa
- pthread_create( &thr[ aux ], NULL, &merge, &tmp[aux]);
- pthread_join(thr[ stack[top--] ], NULL);
- }
- //Enquanto todas as threads nao tiverem terminado seu trabalho, eu espero
- while(top != THMAX - 1);
- }
- }
- int main(){
- //Entrada e saida por arquivo
- freopen("input.txt", "r", stdin);
- freopen("output_WT.txt", "w", stdout);
- //Tamanho do meu array
- int n;
- scanf("%d", &n);
- //Entrada dos elementos do array
- int i;
- for(i = 0; i < n; i++){
- scanf("%d", arr + i);
- }
- clock_t start = clock();
- //MERGE SORT
- merge_sort(n);
- //Printando array ordenado
- /*for(i = 0; i < n; i++){
- printf("%d ", arr[i]);
- }
- putchar('\n');*/
- clock_t end = clock();
- double time = (end - start) / (double)CLOCKS_PER_SEC;
- printf("%.9lf\n", time);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement