Mercurial > hg > Members > kono > Cerium
view example/many_task/spe/QuickSort.cc @ 230:2b114977852d
fix Random
author | gongo@localhost.localdomain |
---|---|
date | Fri, 13 Feb 2009 10:53:58 +0900 |
parents | 29e338dbc280 |
children | d734af296d38 |
line wrap: on
line source
#include "QuickSort.h" #include <stdio.h> #include <string.h> SchedDefineTask(QuickSort); int QuickSort::run(void* rbuff, void* wbuff) { int begin = 0; int end = smanager->get_param(0); DataPtr r_data = (DataPtr)smanager->get_input(0); DataPtr w_data = (DataPtr)smanager->get_output(0); quick_sort(r_data, begin, end-1); //bubble_sort(r_data, begin, end-1); memcpy(w_data, r_data, sizeof(Data)*end); return 0; } void QuickSort::bubble_sort(DataPtr data, int begin, int end) { for (int i = 0; i < end; i++) { for (int j = end; j > i; j--) { if (data[j].index < data[j-1].index) { swap(data, j, j-1); } } } } void QuickSort::quick_sort(DataPtr data, int begin, int end) { if (begin < end) { int where = (begin + end) / 2; int pivot = data[where].index; data[where].index = data[begin].index; int p = begin; for (int i = begin+1; i <= end; i++) { if (data[i].index < pivot) { p++; swap(data, p, i); } } data[begin].index = data[p].index; data[p].index = pivot; quick_sort(data, begin, p-1); quick_sort(data, p+1, end); } } void QuickSort::swap(Data *data, int left, int right) { int tmp = data[left].index; data[left].index = data[right].index; data[right].index = tmp; }