From c10ba99d155ec0f1b0b735d3651d3b78304c6b82 Mon Sep 17 00:00:00 2001
From: "admin@omencraft.com"
 <admin@omencraft.com@0a769ca7-a7f5-676a-18bf-c427514a06d6>
Date: Fri, 4 Nov 2011 20:13:10 +0000
Subject: fixing svn directory

git-svn-id: http://mc-server.googlecode.com/svn/trunk@58 0a769ca7-a7f5-676a-18bf-c427514a06d6
---
 converter/source/cQuicksort.cpp | 67 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 67 insertions(+)
 create mode 100644 converter/source/cQuicksort.cpp

(limited to 'converter/source/cQuicksort.cpp')

diff --git a/converter/source/cQuicksort.cpp b/converter/source/cQuicksort.cpp
new file mode 100644
index 000000000..8a00805eb
--- /dev/null
+++ b/converter/source/cQuicksort.cpp
@@ -0,0 +1,67 @@
+#include "cQuicksort.h"
+#include <ctype.h>
+
+
+
+// Quicksort controller function, it partitions the different pieces of our array.
+void cQuicksort::quicksort(int *arIntegers, int left, int right)
+{
+    if (right > left)
+    {
+         int pivotIndex = median3(arIntegers,left,right);
+         int pivotNewIndex = partition(arIntegers, left, right, pivotIndex);
+
+         // Recursive call to quicksort to sort each half.
+         quicksort(arIntegers, left, pivotNewIndex-1);
+         quicksort(arIntegers, pivotNewIndex+1, right);
+    }
+}
+
+int cQuicksort::median3(int *arIntegers,int left,int right)
+{
+        int center = (left+right)/2;
+
+   if(arIntegers[center] < arIntegers[left])
+        swap(arIntegers[left],arIntegers[center]);
+   if(arIntegers[right] < arIntegers[left])
+        swap(arIntegers[left],arIntegers[right]);
+   if(arIntegers[right] < arIntegers[center])
+        swap(arIntegers[center],arIntegers[right]);
+
+   swap(arIntegers[center],arIntegers[right-1]);
+
+   return center;
+}
+
+// This function takes an array (or one half an array) and sorts it.
+// It then returns a new pivot index number back to quicksort.
+int cQuicksort::partition(int *arIntegers, int left, int right, int pivot)
+{
+     int pivotValue = arIntegers[pivot];
+
+     // Swap it out all the way to the end of the array
+     // So we know where it always is.
+     swap(arIntegers[pivot], arIntegers[right]);
+     int storeIndex = left;
+
+     // Move through the array from start to finish comparing each to our
+     // pivot value (not index, the value that was located at the pivot index)
+     for (int i = left; i < right; i++)
+     {
+         if (arIntegers[i] <= pivotValue)
+         {
+             swap(arIntegers[i], arIntegers[storeIndex]);
+             storeIndex++;
+         }
+     }
+     swap(arIntegers[storeIndex], arIntegers[right]);
+     return storeIndex;
+}
+
+// Simple swap function for our in place swapping.
+void cQuicksort::swap(int &val1, int &val2)
+{
+    int temp = val1;
+    val1 = val2;
+    val2 = temp;
+}
-- 
cgit v1.2.3