Mercurial > hg > Game > Cerium

comparison example/many_task/ppe/QuickSort.cc @ 1852:7e9ebc1b08b6 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Sat, 21 Dec 2013 19:53:05 +0900
parents 637fa9a4105b
children f800f61a0311
comparison
equal deleted inserted replaced
1851:637fa9a4105b 1852:7e9ebc1b08b6
7 static void quick_sort( Data *data, int begin, int end ) ; 7 static void quick_sort( Data *data, int begin, int end ) ;
8 8
9 static void 9 static void
10 swap( Data *data, int left, int right ) 10 swap( Data *data, int left, int right )
11 { 11 {
12 Data tmp = data[left]; 12 Data tmp = data[left];
13 data[left] = data[right]; 13 data[left] = data[right];
14 data[right] = tmp; 14 data[right] = tmp;
15 } 15 }
16 16
17 //#define USE_MEMCPY 17 // #define USE_MEMCPY
18 18
19 void
20 bubble_sort(Data *data, int begin, int end)
21 {
22 for (int count=0;count<end;count++) {
23 for (int c=end;c>count;c--) {
24 if (data[c].index<data[c-1].index)swap(data,c-1,c);
25 }
26 }
27 }
28 static int 19 static int
29 run(SchedTask *s, void* rbuff, void* wbuff) { 20 run(SchedTask *s, void* rbuff, void* wbuff) {
30 // copy value 21 // copy value
31 int begin = 0; 22 int begin = 0;
32 #if USE_SIMPLE_TASK 23 #if USE_SIMPLE_TASK
33 int end = s->read_size()/sizeof(Data); 24 int end = s->read_size()/sizeof(Data);
34 Data *r_data = (Data*)rbuff; 25 Data *r_data = (Data*)rbuff;
35 #ifdef USE_MEMCPY 26 #ifdef USE_MEMCPY
36 Data *w_data = (Data*)wbuff; 27 Data *w_data = (Data*)wbuff;
41 #ifdef USE_MEMCPY 32 #ifdef USE_MEMCPY
42 DataPtr w_data = (DataPtr)s->get_output(0); 33 DataPtr w_data = (DataPtr)s->get_output(0);
43 #endif 34 #endif
44 #endif 35 #endif
45 36
46 // printf("[PPE] Quick: length:%d addr->%x \n",end, (int)rbuff); 37 //printf("[SPE] Quick: length:%d addr->%x \n",end, (int)rbuff);
47 // printf("[PPE] Quick: data[0]: %ld addr->%lx\n",sizeof(r_data),(long)r_data); 38 //printf("[PPE] Quick: data[0]: %d addr->%x\n",sizeof(r_data),r_data);
48 39
49 quick_sort(r_data, begin, end); 40 //show_data(r_data, end);
50 41 quick_sort(r_data, begin, end-1);
51 #ifdef USE_MEMCPY 42 #ifdef USE_MEMCPY
52 memcpy(w_data, r_data, sizeof(Data)*end); 43 memcpy(w_data, r_data, sizeof(Data)*end);
53 #else 44 #else
54 s->swap(); 45 s->swap();
55 #endif 46 #endif
56 47
57 return 0; 48 return 0;
58 } 49 }
59 50
60 void 51 static void
61 qsort_test(Data *data, int begin, int end ) { 52 quick_sort( Data *data, int begin, int end ) {
62 quick_sort(data, begin, end-1); 53
54 if (begin < end) {
55 int where = (begin + end) / 2;
56 int pivot = data[where].index;
57 data[where].index = data[begin].index;
58 int p = begin;
59 int i;
60 for (i=begin+1; i<end; i++) {
61 if (data[i].index < pivot) {
62 p++;
63 swap(data, p, i);
64 }
65 }
66 data[begin].index = data[p].index;
67 data[p].index = pivot;
68
69 quick_sort(data, begin, p-1);
70 quick_sort(data, p+1, end); // tail call
71 }
63 } 72 }
64 73
65 static void
66 quick_sort( Data *data, int begin, int end ) {
67 int stack[1024];
68 int sp = 0;
69 int p;
70 74
71 while (1) {
72 while (begin < end) {
73
74 if (end-begin <= 50) {
75 //bubble_sort(data, begin, end);
76 //break;
77 }
78
79 int where = (begin + end) / 2;
80 int pivot = data[where].index;
81 data[where].index = data[begin].index;
82 int i;
83 p = begin;
84 for (i=begin+1; i<end; i++) {
85 if (data[i].index < pivot) {
86 p++;
87 swap(data, p, i);
88 }
89 }
90 data[begin].index = data[p].index;
91 data[p].index = pivot;
92
93 stack[sp++] = p + 1;
94 stack[sp++] = end;
95 end = p - 1;
96 }
97 if (sp == 0) return;
98 end = stack[--sp];
99 begin = stack[--sp];
100 begin = p + 1;
101 }
102 }
103 /* end */ 75 /* end */