summaryrefslogtreecommitdiffstats
path: root/converter/quicksort.cpp
diff options
context:
space:
mode:
authoradmin@omencraft.com <admin@omencraft.com@0a769ca7-a7f5-676a-18bf-c427514a06d6>2011-10-30 19:15:44 +0100
committeradmin@omencraft.com <admin@omencraft.com@0a769ca7-a7f5-676a-18bf-c427514a06d6>2011-10-30 19:15:44 +0100
commit940d36d8a1521f171674e358dada3305e66d48da (patch)
tree0d98770a7faadd0b8b9bc470e6a7e6308a8a99b3 /converter/quicksort.cpp
parentChanged long to long long so it works fine on 32bit systems (diff)
downloadcuberite-940d36d8a1521f171674e358dada3305e66d48da.tar
cuberite-940d36d8a1521f171674e358dada3305e66d48da.tar.gz
cuberite-940d36d8a1521f171674e358dada3305e66d48da.tar.bz2
cuberite-940d36d8a1521f171674e358dada3305e66d48da.tar.lz
cuberite-940d36d8a1521f171674e358dada3305e66d48da.tar.xz
cuberite-940d36d8a1521f171674e358dada3305e66d48da.tar.zst
cuberite-940d36d8a1521f171674e358dada3305e66d48da.zip
Diffstat (limited to 'converter/quicksort.cpp')
-rw-r--r--converter/quicksort.cpp88
1 files changed, 88 insertions, 0 deletions
diff --git a/converter/quicksort.cpp b/converter/quicksort.cpp
new file mode 100644
index 000000000..9bc1d477f
--- /dev/null
+++ b/converter/quicksort.cpp
@@ -0,0 +1,88 @@
+#include "quicksort.h"
+
+
+
+
+// Quicksort controller function, it partitions the different pieces of our array.
+void quicksort(int *arIntegers, int left, int right)
+{
+/* cout << "quicksort ([" << arIntegers[0] << ","
+ << arIntegers[1] << ","
+ << arIntegers[2] << ","
+ << arIntegers[3] << ","
+ << arIntegers[4] << ","
+ << arIntegers[5] << ","
+ << arIntegers[6] << "],"
+ << left << ","
+ << right << ")\n";
+*/
+ 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 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 partition(int *arIntegers, int left, int right, int pivot)
+{
+/* cout << "partition ("<< arIntegers[0] << ","
+ << arIntegers[1] << ","
+ << arIntegers[2] << ","
+ << arIntegers[3] << ","
+ << arIntegers[4] << ","
+ << arIntegers[5] << ","
+ << arIntegers[6] << "],"
+ << left << ","
+ << right << ")\n";
+*/
+ 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 swap(int &val1, int &val2)
+{
+ int temp = val1;
+ val1 = val2;
+ val2 = temp;
+}
+