# Untitled

By: a guest on May 11th, 2012  |  syntax: None  |  size: 2.70 KB  |  hits: 68  |  expires: Never
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>
4. #include <stdlib.h>
5.
7.
8. /*
9.
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;
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.
89.
90.                 merge(p->i, p->j);
92. }
93.
94.
95. int main()
96. {
97.                 int i;
98.                 NODE m;
99.                 m.i = 0;
100.                 m.j = 9;
102.
103.                 int ret;
104.
106.                 if (ret) {
107.                         printf("%d %s - unable to create thread - ret - %dn", __LINE__, __FUNCTION__, ret);
108.                         exit(1);
109.                 }
110.