Mercurial > hg > Members > kono > Cerium

comparison example/many_task/spe/QuickSort.cc @ 932:f4d7cf77ec3d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
sort test (add swap())
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Sat, 31 Jul 2010 00:57:46 +0900
parents ab866bc8a624
children da657af64afd
comparison
equal deleted inserted replaced
930:35efda39c2d9 932:f4d7cf77ec3d
1 #include "QuickSort.h" 1 #include "QuickSort.h"
2 #include <stdio.h> 2 #include <stdio.h>
3 #include <string.h> 3 #include <string.h>
4 #include "SpeProfile.h"
5 4
6 SchedDefineTask(QuickSort); 5 SchedDefineTask(QuickSort);
7 6
8 static void bubble_sort(DataPtr data, int begin, int end); 7 static void quick_sort( Data *data, int begin, int end ) ;
9 static void quick_sort(DataPtr data, int begin, int end);
10
11 static void swap(Data *data, int left, int right);
12
13 static int
14 run(SchedTask *smanager, void* rbuff, void* wbuff) {
15 int begin = 0;
16 int end = (long)smanager->get_param(0);
17 DataPtr r_data = (DataPtr)smanager->get_input(0);
18 DataPtr w_data = (DataPtr)smanager->get_output(0);
19 //SpeProfile *prof = new SpeProfile;
20
21 //prof->ProfStart();
22 if (0)
23 bubble_sort(r_data, begin, end-1);
24 else
25 quick_sort(r_data, begin, end-1);
26 memcpy(w_data, r_data, sizeof(Data)*end);
27 //prof->ProfStop();
28 //prof->ProfPrint();
29
30 //delete prof;
31 return 0;
32 }
33
34 static void 8 static void
35 bubble_sort(DataPtr data, int begin, int end) 9 swap( Data *data, int left, int right )
36 {
37 for (int i = 0; i < end; i++) {
38 for (int j = end; j > i; j--) {
39 if (data[j].index < data[j-1].index) {
40 swap(data, j, j-1);
41 }
42 }
43 }
44 }
45
46
47 static void
48 quick_sort(DataPtr data, int begin, int end)
49 {
50 if (begin < end) {
51
52 int where = (begin + end) / 2;
53 int pivot = data[where].index;
54 data[where].index = data[begin].index;
55 int p = begin;
56
57 for (int i = begin+1; i <= end; i++) {
58 if (data[i].index < pivot) {
59 p++;
60 swap(data, p, i);
61 }
62 }
63
64 data[begin].index = data[p].index;
65 data[p].index = pivot;
66
67 quick_sort(data, begin, p-1);
68 quick_sort(data, p+1, end);
69 }
70 }
71
72
73 static void
74 swap(Data *data, int left, int right)
75 { 10 {
76 int tmp = data[left].index; 11 int tmp = data[left].index;
77 data[left].index = data[right].index; 12 data[left].index = data[right].index;
78 data[right].index = tmp; 13 data[right].index = tmp;
79 } 14 }
80 15
16 static int
17 run(SchedTask *s, void* rbuff, void* wbuff) {
18 // copy value
19 int begin = 0;
20 #if USE_SIMPLE_TASK
21 long end = s->read_size()/sizeof(Data);
22 Data *r_data = (Data*)rbuff;
23 #else
24 int end = (long)s->get_param(0);
25 DataPtr r_data = (DataPtr)s->get_input(0);
26 #endif
27
28 //printf("[PPE] Quick: length:%d addr->%x \n",end, (int*)rbuff);
29 //printf("[PPE] Quick: data[0]: %d addr->%x\n",sizeof(r_data),r_data);
30
31 //show_data(r_data, end);
32 quick_sort(r_data, begin, end-1);
33 s->swap();
34 // memcpy(w_data, r_data, sizeof(Data)*end);
35
36 return 0;
37 }
38
39 static void
40 quick_sort( Data *data, int begin, int end ) {
41
42 if (begin < end) {
43 int where = (begin + end) / 2;
44 int pivot = data[where].index;
45 data[where].index = data[begin].index;
46 int p = begin;
47 int i;
48 for (i=begin+1; i<=end; i++) {
49 if (data[i].index < pivot) {
50 p++;
51 swap(data, p, i);
52 }
53 }
54 data[begin].index = data[p].index;
55 data[p].index = pivot;
56
57 quick_sort(data, begin, p-1);
58 quick_sort(data, p+1, end); // tail call
59 }
60 }
61
62
81 /* end */ 63 /* end */