From 1c42208709b1040a2b213259cdaff5ee855cabab Mon Sep 17 00:00:00 2001
From: obiwankennedy <renaud@rolisteam.org>
Date: Thu, 9 Jan 2014 11:30:13 +0100
Subject: Update sortresult.cpp

dichotomy sorting
---
 node/sortresult.cpp | 53 +++++++++++++++++++++++++++++++++--------------------
 1 file changed, 33 insertions(+), 20 deletions(-)

(limited to 'node')

diff --git a/node/sortresult.cpp b/node/sortresult.cpp
index 9797310..23e3e7f 100644
--- a/node/sortresult.cpp
+++ b/node/sortresult.cpp
@@ -22,36 +22,49 @@ void SortResultNode::run(ExecutionNode* node)
         QList<Die*> diceList=previousDiceResult->getResultList();
         QList<Die*> diceList2=m_diceResult->getResultList();
 
-        /*diceList2 = diceList;
-
-        if(!m_ascending)
-        {
-            qSort(diceList2.begin(), diceList2.end(), qGreater<Die*>());
-        }
-        else
-        {
-            qSort(diceList2.begin(), diceList2.end(), qLess<Die*>());
-        }*/
-
 
+        // dichotomy sorting
         for(int i = 0; i<diceList.size();++i)
         {
             Die* tmp1 = diceList[i];
             int j =0;
             bool found = false;
-            for(; ((j < diceList2.size())&&(!found)); ++j)
+            //for(; ((j < diceList2.size())&&(!found)); ++j)
+            int start = 0;
+            int end = diceList2.size();
+            int distance = 0;
+            Die* tmp2 = NULL;
+            while(!found)
             {
-                Die* tmp2 = diceList2[j];
-//                qDebug() << tmp1->getValue() << tmp2->getValue()  << j;
-                if(tmp1->getValue() < tmp2->getValue())
+                distance = end-start;
+                j = (start+end)/2;
+
+
+                if(distance == 0)
+                {
+                    j=end;
+                    found=true;
+                }
+                else
                 {
-                    found = true;
+                    tmp2 = diceList2[j];
+                    if(tmp1->getValue() < tmp2->getValue())
+                    {
+                            end=j;
+                    }
+                    else
+                    {
+                            start=j+1;
+                    }
+
                 }
+
             }
-            if(found)
-                diceList2.insert(j-1,tmp1);
-            else
-                diceList2.append(tmp1);
+            //qDebug() << tmp1->getValue() << j  << found;
+            //if(found)
+                diceList2.insert(j,tmp1);
+            /*else
+                diceList2.append(tmp1);*/
 
         }
 
-- 
cgit v1.2.3-70-g09d2