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