|
109
|
1 #include "QuickSort.h"
|
|
|
2 #include <stdio.h>
|
|
|
3 #include <string.h>
|
|
|
4
|
|
|
5 SchedDefineTask(QuickSort);
|
|
|
6
|
|
|
7 int
|
|
|
8 QuickSort::run(void* rbuff, void* wbuff) {
|
|
|
9 // copy value
|
|
|
10 int begin = 0;
|
|
|
11 int end = get_param(0);
|
|
220
|
12
|
|
109
|
13 Data *r_data = (Data*)get_input(rbuff, 0);
|
|
|
14 Data *w_data = (Data*)get_output(wbuff, 0);
|
|
|
15
|
|
|
16 //printf("[PPE] Quick: length:%d addr->%x \n",end, (int*)rbuff);
|
|
|
17 //printf("[PPE] Quick: data[0]: %d addr->%x\n",sizeof(r_data),r_data);
|
|
|
18
|
|
|
19 //show_data(r_data, end);
|
|
|
20 quick_sort(r_data, begin, end-1);
|
|
|
21 memcpy(w_data, r_data, sizeof(Data)*end);
|
|
|
22
|
|
|
23 return 0;
|
|
|
24 }
|
|
|
25
|
|
|
26 void
|
|
|
27 QuickSort::quick_sort( Data *data, int begin, int end ) {
|
|
|
28
|
|
|
29 if (begin < end) {
|
|
|
30 int where = (begin + end) / 2;
|
|
|
31 int pivot = data[where].index;
|
|
|
32 data[where].index = data[begin].index;
|
|
|
33 int p = begin;
|
|
|
34 int i;
|
|
|
35 for (i=begin+1; i<=end; i++) {
|
|
|
36 if (data[i].index < pivot) {
|
|
|
37 p++;
|
|
|
38 swap(data, p, i);
|
|
|
39 }
|
|
|
40 }
|
|
|
41 data[begin].index = data[p].index;
|
|
|
42 data[p].index = pivot;
|
|
|
43
|
|
|
44 quick_sort(data, begin, p-1);
|
|
|
45 quick_sort(data, p+1, end);
|
|
|
46 }
|
|
|
47 }
|
|
|
48
|
|
|
49 void
|
|
|
50 QuickSort::swap( Data *data, int left, int right )
|
|
|
51 {
|
|
|
52 int tmp = data[left].index;
|
|
|
53 data[left].index = data[right].index;
|
|
|
54 data[right].index = tmp;
|
|
|
55 }
|
