# HG changeset patch
# User Shinji KONO <kono@ie.u-ryukyu.ac.jp>
# Date 1387623185 -32400
# Node ID 7e9ebc1b08b6664e1012b9bf8f57863c795f4624
# Parent  637fa9a4105b1b53d5527d300d83ae4bc3965cb0
fix

diff -r 637fa9a4105b -r 7e9ebc1b08b6 example/many_task/ppe/QuickSort.cc
--- a/example/many_task/ppe/QuickSort.cc	Sat Dec 21 19:42:17 2013 +0900
+++ b/example/many_task/ppe/QuickSort.cc	Sat Dec 21 19:53:05 2013 +0900
@@ -9,26 +9,17 @@
 static void
 swap( Data *data, int left, int right )
 {
-    Data tmp    = data[left];
+    Data tmp	      = data[left];
     data[left]  = data[right];
     data[right] = tmp;
 }
 
-//#define USE_MEMCPY
+// #define USE_MEMCPY
 
-void
-bubble_sort(Data *data, int begin, int end)
-{
-    for (int count=0;count<end;count++) {
-        for (int c=end;c>count;c--) {
-            if (data[c].index<data[c-1].index)swap(data,c-1,c);
-        }
-    }
-}
 static int
 run(SchedTask *s, void* rbuff, void* wbuff) {
     // copy value
-    int begin  = 0;
+    int begin	= 0;
 #if USE_SIMPLE_TASK
     int end = s->read_size()/sizeof(Data);
     Data *r_data = (Data*)rbuff;
@@ -43,11 +34,11 @@
 #endif
 #endif
 
-    // printf("[PPE] Quick: length:%d addr->%x \n",end, (int)rbuff);
-    // printf("[PPE] Quick: data[0]: %ld addr->%lx\n",sizeof(r_data),(long)r_data);
+    //printf("[SPE] Quick: length:%d addr->%x \n",end, (int)rbuff);
+    //printf("[PPE] Quick: data[0]: %d addr->%x\n",sizeof(r_data),r_data); 
 
-    quick_sort(r_data, begin, end);
-
+    //show_data(r_data, end);
+    quick_sort(r_data, begin, end-1);
 #ifdef USE_MEMCPY
     memcpy(w_data, r_data, sizeof(Data)*end);
 #else
@@ -57,47 +48,28 @@
     return 0;
 }
 
-void
-qsort_test(Data *data, int begin, int end ) {
-    quick_sort(data, begin, end-1);
+static void 
+quick_sort( Data *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;
+	int i;
+	for (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); // tail call
+    }
 }
 
-static void
-quick_sort( Data *data, int begin, int end ) {
-    int stack[1024];
-    int sp = 0;
-    int p;
 
-    while (1) {
-        while (begin < end) {
-
-            if (end-begin <= 50) {
-                //bubble_sort(data, begin, end);
-                //break;
-            }
-
-            int where = (begin + end) / 2;
-            int pivot = data[where].index;
-            data[where].index = data[begin].index;
-            int i;
-            p = begin;
-            for (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;
-
-            stack[sp++] = p + 1;
-            stack[sp++] = end;
-            end = p - 1;
-        }
-        if (sp == 0) return;
-        end = stack[--sp];
-        begin = stack[--sp];
-        begin = p + 1;
-        }
-}
 /* end */