Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on May 11th, 2012  |  syntax: None  |  size: 2.70 KB  |  hits: 68  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. parallel quicksort in c
  2. #include <stdio.h>
  3. #include <pthread.h>
  4. #include <stdlib.h>
  5.  
  6. #define NOTHREADS 2
  7.  
  8. /*
  9.  
  10. gcc -ggdb -lpthread parallel-mergesort.c
  11.  
  12.  
  13. NOTE:
  14. The mergesort boils downs to this..
  15. Given two sorted array's how do we merge this?
  16.  
  17. We need a new array to hold the result of merging
  18. otherwise it is not possible to do it using array,
  19. so we may need a linked list
  20.  
  21. */
  22.  
  23. int a[] = {10, 8, 5, 2, 3, 6, 7, 1, 4, 9};
  24.  
  25. typedef struct node {
  26. int i;
  27. int j;
  28. } NODE;
  29.  
  30. void merge(int i, int j)
  31. {
  32.         int mid = (i+j)/2;
  33.         int ai = i;
  34.         int bi = mid+1;
  35.  
  36.         int newa[j-i+1], newai = 0;
  37.  
  38.         while(ai <= mid && bi <= j) {
  39.                 if (a[ai] > a[bi])
  40.                         newa[newai++] = a[bi++];
  41.                 else                    
  42.                         newa[newai++] = a[ai++];
  43.         }
  44.  
  45.         while(ai <= mid) {
  46.                 newa[newai++] = a[ai++];
  47.         }
  48.  
  49.         while(bi <= j) {
  50.                 newa[newai++] = a[bi++];
  51.         }
  52.  
  53.         for (ai = 0; ai < (j-i+1) ; ai++)
  54.                 a[i+ai] = newa[ai];
  55.  
  56. }
  57.  
  58. void * mergesort(void *a)
  59. {
  60.                 NODE *p = (NODE *)a;
  61.                 NODE n1, n2;
  62.                 int mid = (p->i+p->j)/2;
  63.                 pthread_t tid1, tid2;
  64.                 int ret;
  65.  
  66.                 n1.i = p->i;
  67.                 n1.j = mid;
  68.  
  69.                 n2.i = mid+1;
  70.                 n2.j = p->j;
  71.  
  72.                 if (p->i >= p->j) return;
  73.  
  74.                 ret = pthread_create(&tid1, NULL, mergesort, &n1);
  75.                 if (ret) {
  76.                         printf("%d %s - unable to create thread - ret - %dn", __LINE__, __FUNCTION__, ret);    
  77.                         exit(1);
  78.                 }
  79.  
  80.  
  81.                 ret = pthread_create(&tid2, NULL, mergesort, &n2);
  82.                 if (ret) {
  83.                         printf("%d %s - unable to create thread - ret - %dn", __LINE__, __FUNCTION__, ret);    
  84.                         exit(1);
  85.                 }
  86.  
  87.                 pthread_join(tid1, NULL);
  88.                 pthread_join(tid2, NULL);
  89.  
  90.                 merge(p->i, p->j);
  91.                 pthread_exit(NULL);
  92. }
  93.  
  94.  
  95. int main()
  96. {
  97.                 int i;
  98.                 NODE m;
  99.                 m.i = 0;
  100.                 m.j = 9;
  101.                 pthread_t tid;
  102.  
  103.                 int ret;
  104.  
  105.                 ret=pthread_create(&tid, NULL, mergesort, &m);
  106.                 if (ret) {
  107.                         printf("%d %s - unable to create thread - ret - %dn", __LINE__, __FUNCTION__, ret);    
  108.                         exit(1);
  109.                 }
  110.  
  111.                 pthread_join(tid, NULL);
  112.  
  113.                 for (i = 0; i < 10; i++)
  114.                                 printf ("%d ", a[i]);
  115.  
  116.                 printf ("n");
  117.  
  118.                 // pthread_exit(NULL);
  119.                 return 0;
  120. }
create a new version of this paste RAW Paste Data