diff -r 28e26cad1a6da73b5e6a5c030a65ee5bb77aed0d -r 8b7c98b7acaac42034eff0ebee63d7b143841e26 cpp/algorithms/algorithms.vcxproj --- a/cpp/algorithms/algorithms.vcxproj Sat Feb 16 22:33:58 2013 -0600 +++ b/cpp/algorithms/algorithms.vcxproj Sun Feb 17 18:50:14 2013 -0600 @@ -15,9 +15,11 @@ + + diff -r 28e26cad1a6da73b5e6a5c030a65ee5bb77aed0d -r 8b7c98b7acaac42034eff0ebee63d7b143841e26 cpp/algorithms/algorithms.vcxproj.filters --- a/cpp/algorithms/algorithms.vcxproj.filters Sat Feb 16 22:33:58 2013 -0600 +++ b/cpp/algorithms/algorithms.vcxproj.filters Sun Feb 17 18:50:14 2013 -0600 @@ -44,5 +44,11 @@ Header Files + + Header Files + + + Header Files + \ No newline at end of file diff -r 28e26cad1a6da73b5e6a5c030a65ee5bb77aed0d -r 8b7c98b7acaac42034eff0ebee63d7b143841e26 cpp/algorithms/src/Algorithm.h --- a/cpp/algorithms/src/Algorithm.h Sat Feb 16 22:33:58 2013 -0600 +++ b/cpp/algorithms/src/Algorithm.h Sun Feb 17 18:50:14 2013 -0600 @@ -28,6 +28,11 @@ ss << "] "; return ss.str(); } + + std::vector getContainer() + { + return this->_container; + } }; #endif \ No newline at end of file diff -r 28e26cad1a6da73b5e6a5c030a65ee5bb77aed0d -r 8b7c98b7acaac42034eff0ebee63d7b143841e26 cpp/algorithms/src/BinarySearch.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/cpp/algorithms/src/BinarySearch.h Sun Feb 17 18:50:14 2013 -0600 @@ -0,0 +1,29 @@ +#ifndef BINARYSEARCH_H +#define BINARYSEARCH_H + +#include "SearchAlgorithm.h" + +template +class BinarySearch : public SearchAlgorithm +{ +public: + virtual int Search(T item) + { + int low = 0; + int high = this->_container.size() - 1; + int idx; + while (low <= high) + { + idx = ( low + high ) / 2; + if ( item == this->_container.at(idx) ) + return idx; + else if ( item < this->_container.at(idx) ) + high = idx - 1; + else + low = idx + 1; + } + return -1; + } +}; + +#endif \ No newline at end of file diff -r 28e26cad1a6da73b5e6a5c030a65ee5bb77aed0d -r 8b7c98b7acaac42034eff0ebee63d7b143841e26 cpp/algorithms/src/MergeSort.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/cpp/algorithms/src/MergeSort.h Sun Feb 17 18:50:14 2013 -0600 @@ -0,0 +1,61 @@ +#ifndef MERGESORT_H +#define MERGESORT_H + +#include "SortAlgorithm.h" +#include + +template +class MergeSort : public SortAlgorithm +{ +public: + + virtual void Sort() + { + this->_container = mergesort(this->_container); + } + + std::vector mergesort(std::vector arr) + { + if (arr.size() <= 1) + return arr; + size_t middle = arr.size() / 2; + std::vector left(arr.begin(), arr.begin() + middle); + std::vector right(arr.begin() + middle, arr.end()); + + left = mergesort(left); + right = mergesort(right); + + return merge(left, right); + } + + std::vector merge(std::vector left, std::vector right) + { + std::vector res; + + while (left.size() > 0 || right.size() > 0) + { + if (left.size() > 0 && right.size() > 0) + { + if (left.at(0) <= right.at(0)) + { + res.push_back(left.at(0)); + left.erase(left.begin()); + } else { + res.push_back(right.at(0)); + right.erase(right.begin()); + } + } else if (left.size() > 0) { + res.push_back(left.at(0)); + left.erase(left.begin()); + } else if (right.size() > 0) { + res.push_back(right.at(0)); + right.erase(right.begin()); + } + + } + + return res; + } +}; + +#endif \ No newline at end of file diff -r 28e26cad1a6da73b5e6a5c030a65ee5bb77aed0d -r 8b7c98b7acaac42034eff0ebee63d7b143841e26 cpp/algorithms/src/SearchAlgorithm.h --- a/cpp/algorithms/src/SearchAlgorithm.h Sat Feb 16 22:33:58 2013 -0600 +++ b/cpp/algorithms/src/SearchAlgorithm.h Sun Feb 17 18:50:14 2013 -0600 @@ -3,11 +3,12 @@ #include "Algorithm.h" -class SearchAlgorithm +template +class SearchAlgorithm : public Algorithm { public: //void f() { this-> - virtual void Search() = 0; + virtual int Search(T item) = 0; }; #endif \ No newline at end of file diff -r 28e26cad1a6da73b5e6a5c030a65ee5bb77aed0d -r 8b7c98b7acaac42034eff0ebee63d7b143841e26 cpp/algorithms/src/main.cpp --- a/cpp/algorithms/src/main.cpp Sat Feb 16 22:33:58 2013 -0600 +++ b/cpp/algorithms/src/main.cpp Sun Feb 17 18:50:14 2013 -0600 @@ -7,16 +7,21 @@ #include "InsertSort.h" #include "MedianSort.h" #include "QuickSort.h" +#include "MergeSort.h" +#include "BinarySearch.h" using namespace std; int main() { - QuickSort sort1; + MergeSort sort1; //sort1.initContainer(create_vector("test")("test2")); //cout << sort1.ToString(); //vector arr1 = create_vector( - sort1.initContainer(create_vector(3)(2)(3)(1)); + sort1.initContainer(create_vector(3)(2)(4)(3)(1)); sort1.Sort(); cout << sort1.ToString() << endl; + BinarySearch search1; + search1.initContainer(sort1.getContainer()); + cout << search1.Search(7) << endl; } \ No newline at end of file