diff options
author | admin@omencraft.com <admin@omencraft.com@0a769ca7-a7f5-676a-18bf-c427514a06d6> | 2011-11-04 17:27:11 +0100 |
---|---|---|
committer | admin@omencraft.com <admin@omencraft.com@0a769ca7-a7f5-676a-18bf-c427514a06d6> | 2011-11-04 17:27:11 +0100 |
commit | 563028f6dbaad33152a873ca68f4b619839a9589 (patch) | |
tree | 37de244a7e14441b58f55ad904e502e51f2ab163 /converter/quicksort.cpp | |
parent | Added cRedstone to project file (diff) | |
download | cuberite-563028f6dbaad33152a873ca68f4b619839a9589.tar cuberite-563028f6dbaad33152a873ca68f4b619839a9589.tar.gz cuberite-563028f6dbaad33152a873ca68f4b619839a9589.tar.bz2 cuberite-563028f6dbaad33152a873ca68f4b619839a9589.tar.lz cuberite-563028f6dbaad33152a873ca68f4b619839a9589.tar.xz cuberite-563028f6dbaad33152a873ca68f4b619839a9589.tar.zst cuberite-563028f6dbaad33152a873ca68f4b619839a9589.zip |
Diffstat (limited to 'converter/quicksort.cpp')
-rw-r--r-- | converter/quicksort.cpp | 88 |
1 files changed, 0 insertions, 88 deletions
diff --git a/converter/quicksort.cpp b/converter/quicksort.cpp deleted file mode 100644 index 9bc1d477f..000000000 --- a/converter/quicksort.cpp +++ /dev/null @@ -1,88 +0,0 @@ -#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; -} - |