diff -r 7efa32a4dc11aeb6463ff1a1120f8a5f745ee5be -r 6cd079b8d44be4bf692c64502ad981f31b31c3c2 cpp/algorithms/src/BinarySearch.h --- a/cpp/algorithms/src/BinarySearch.h Wed Feb 20 23:29:56 2013 -0600 +++ b/cpp/algorithms/src/BinarySearch.h Fri Feb 22 23:18:18 2013 -0600 @@ -26,4 +26,31 @@ } }; +template +class BinarySearchRecursive : public SearchAlgorithm +{ +public: + virtual int Search(T item) + { + return binarysearch(item, 0, this->_container.size()); + } + + int binarysearch(T item, int left, int right) + { + if (left > right) + { + return -1; + } else { + int mid = ( left + right ) / 2; + + if (this->_container.at(mid) > item) + return binarysearch(item, left, right - 1); + else if (this->_container.at(mid) < item) + return binarysearch(item, left + 1, right); + else + return mid; + } + } +}; + #endif \ No newline at end of file diff -r 7efa32a4dc11aeb6463ff1a1120f8a5f745ee5be -r 6cd079b8d44be4bf692c64502ad981f31b31c3c2 cpp/algorithms/src/Node.h --- a/cpp/algorithms/src/Node.h Wed Feb 20 23:29:56 2013 -0600 +++ b/cpp/algorithms/src/Node.h Fri Feb 22 23:18:18 2013 -0600 @@ -35,6 +35,7 @@ if (this->left != null) throw std::string("Left is not null!"); this->left = createNode(obj); + return this->left; } Node * addRight(T obj) @@ -42,6 +43,7 @@ if (this->right != null) throw std::string("Right is not null!"); this->right = createNode(obj); + return this->right; } void addLeftRight(T left, T right) diff -r 7efa32a4dc11aeb6463ff1a1120f8a5f745ee5be -r 6cd079b8d44be4bf692c64502ad981f31b31c3c2 cpp/algorithms/src/QuickSort.h --- a/cpp/algorithms/src/QuickSort.h Wed Feb 20 23:29:56 2013 -0600 +++ b/cpp/algorithms/src/QuickSort.h Fri Feb 22 23:18:18 2013 -0600 @@ -5,6 +5,79 @@ #include template +class QuickSortWiki : public SortAlgorithm +{ +public: + virtual void Sort() + { + quicksort(0, this->_container.size() - 1); + } + + void quicksort(int left, int right) + { + if (left < right) + { + + int store; + int pivindex = ( right + left ) / 2; + T pivval = this->_container.at(pivindex); + std::swap(this->_container[pivindex], this->_container[right]); + store = left; + for(int i = left; i < right - 1; i++) + { + if (this->_container[i] < pivval) + { + std::swap(this->_container[i], this->_container[store]); + store++; + } + } + std::swap(this->_container[store], this->_container[right]); + quicksort(left, store - 1); + quicksort(store + 1, right); + } else { + return; + } + } +}; + +template +class QuickSort2 : public SortAlgorithm +{ +public: + virtual void Sort() + { + quicksort(0, this->_container.size() - 1); + } + + void quicksort(int left, int right) + { + if (right <= left) + return; + + // parition + int store = 0; + int pivindex = ( left + right ) / 2; + T piv_value = this->_container[pivindex]; + std::swap(this->_container[pivindex], this->_container[right]); + store = left; + for(int i = left; i <= right - 1; i++) + { + if (this->_container[i] < piv_value) + { + std::swap(this->_container[i], this->_container[store]); + store++; + } + } + std::swap(this->_container[store], this->_container[right]); + + + quicksort(left, store - 1); + quicksort(store + 1, right); + } +}; + + +template class QuickSort : public SortAlgorithm { public: @@ -15,24 +88,29 @@ void quicksort(int left, int right) { - if (right <= left) - return; + int leftpos = left, rightpos = right; + T pivot = this->_container[(left + right) / 2]; - int store; - int pivindex = left + right / 2; - std::swap(this->_container[pivindex], this->_container[right]); - store = left; - for(int i = left; i < right - 1; i++) + while (leftpos <= rightpos) { - if (this->_container[i] <= this->_container[right]) + while(this->_container.at(leftpos) < pivot) + leftpos++; + + while(this->_container.at(rightpos) > pivot) + rightpos--; + + if (leftpos <= rightpos) { - std::swap(this->_container[i], this->_container[store]); - store++; + std::swap(this->_container[rightpos], this->_container[leftpos]); + leftpos++; + rightpos--; } } - std::swap(this->_container[store], this->_container[right]); - quicksort(left, store - 1); - quicksort(store + 1, right); + + if (left < rightpos) + quicksort(left, rightpos); + if (leftpos < right) + quicksort(leftpos, right); } }; diff -r 7efa32a4dc11aeb6463ff1a1120f8a5f745ee5be -r 6cd079b8d44be4bf692c64502ad981f31b31c3c2 cpp/algorithms/src/Tree.h --- a/cpp/algorithms/src/Tree.h Wed Feb 20 23:29:56 2013 -0600 +++ b/cpp/algorithms/src/Tree.h Fri Feb 22 23:18:18 2013 -0600 @@ -34,12 +34,30 @@ //DeleteTree(root); } - //Node * DFS(T value) - //{ - // return dfs(value, this->root); - //} + Node * DFS(T value) + { + return dfs(value, this->root); + } + Node * dfs(T value, Node * nodes) + { + if (nodes == null) + return null; + cout << "Examining: " << nodes->object << endl; + if (nodes->object == value) + return nodes; + Node * ret = null, * ret2 = null; + if (nodes->left) + ret = dfs(value, nodes->left); + if (ret != null) + return ret; + if (nodes->right) + ret = dfs(value, nodes->right); + if (ret != null) + return ret; + return null; + } Node * BFS(T value) { diff -r 7efa32a4dc11aeb6463ff1a1120f8a5f745ee5be -r 6cd079b8d44be4bf692c64502ad981f31b31c3c2 cpp/algorithms/src/main.cpp --- a/cpp/algorithms/src/main.cpp Wed Feb 20 23:29:56 2013 -0600 +++ b/cpp/algorithms/src/main.cpp Fri Feb 22 23:18:18 2013 -0600 @@ -16,16 +16,18 @@ int main() { - /*//sort1.initContainer(create_vector("test")("test2")); + //sort1.initContainer(create_vector("test")("test2")); //cout << sort1.ToString(); //vector arr1 = create_vector( - MedianSort sort1; - sort1.initContainer(create_vector(3)(2)(4)(3)(1)); - sort1.Sort(); - cout << sort1.ToString() << endl; - //BinarySearch search1; + //QuickSort2 sort1; + //sort1.initContainer(create_vector(3)(2)(7)(3)(1)); + //sort1.initContainer(create_vector(1)(2)(7)(3)); + //cout << sort1.ToString() << endl; + //sort1.Sort(); + //cout << sort1.ToString() << endl; + //BinarySearchRecursive search1; //search1.initContainer(sort1.getContainer()); - //cout << search1.Search(7) << endl;*/ + //cout << search1.Search(3) << endl; Node * root = new Node(30); Node * l = root->addLeft(20); Node * r = root->addRight(40); @@ -39,9 +41,10 @@ //{ // cout << nodes[i]->object << " "; //} - cout << tree.BFS_R(25)->object << endl; - cout << endl; - tree.DeleteTree(); + cout << tree.BFS(28)->object << endl; + //cout << tree.BFS_R(25)->object << endl; + //cout << endl; + //tree.DeleteTree(); //root->addRight( //root->left //Tree t(root); diff -r 7efa32a4dc11aeb6463ff1a1120f8a5f745ee5be -r 6cd079b8d44be4bf692c64502ad981f31b31c3c2 python/algorithms/Node.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/algorithms/Node.py Fri Feb 22 23:18:18 2013 -0600 @@ -0,0 +1,26 @@ +class Node(object): + parent = None + left = None + right = None + object = None + + def __init__(self, val): + self.object = val + + def _createNode(self, obj): + newnode = Node(obj) + newnode.parent = self + return newnode + + def addLeft(self, obj): + self.left = self._createNode(obj) + return self.left + + def addRight(self, obj): + self.right = self._createNode(obj) + return self.right + + def addLeftRight(self, left, right): + self.addLeft(left) + self.addRight(right) + diff -r 7efa32a4dc11aeb6463ff1a1120f8a5f745ee5be -r 6cd079b8d44be4bf692c64502ad981f31b31c3c2 python/algorithms/SearchAlgorithm.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/algorithms/SearchAlgorithm.py Fri Feb 22 23:18:18 2013 -0600 @@ -0,0 +1,25 @@ +from Algorithm import Algorithm + +class SearchAlgorithm(Algorithm): + # virtual void Sort + + def Search(self, val): + raise Exception("Not implemented!") + +class BinarySearch(SearchAlgorithm): + + def Search(self, val): + return self.binarysearch(val, 0, len(self._container)) + + def binarysearch(self, val, left, right): + if (left > right): + return -1; + else: + mid = ( left + right ) / 2 + + if self._container[mid] > val: + return self.binarysearch(val, left, right - 1) + elif self._container[mid] < val: + return self.binarysearch(val, left + 1, right) + else: + return mid \ No newline at end of file diff -r 7efa32a4dc11aeb6463ff1a1120f8a5f745ee5be -r 6cd079b8d44be4bf692c64502ad981f31b31c3c2 python/algorithms/SortAlgorithm.py --- a/python/algorithms/SortAlgorithm.py Wed Feb 20 23:29:56 2013 -0600 +++ b/python/algorithms/SortAlgorithm.py Fri Feb 22 23:18:18 2013 -0600 @@ -17,7 +17,7 @@ return; store = 0 - pivotindex = left + right / 2 + pivotindex = ( left + right ) / 2 self._container[pivotindex], self._container[right] = self._container[right], self._container[pivotindex] store = left for i in range(left, right): diff -r 7efa32a4dc11aeb6463ff1a1120f8a5f745ee5be -r 6cd079b8d44be4bf692c64502ad981f31b31c3c2 python/algorithms/Tree.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/python/algorithms/Tree.py Fri Feb 22 23:18:18 2013 -0600 @@ -0,0 +1,101 @@ +class Tree(object): + root = None + + def __init__(self, startnode): + self.root = startnode + + def DFS(self, val): + return self._dfs(val, self.root) + + + def _dfs(self, val, node): + if node == None: + return None + + print "Examining: " + str(node.object) + + if node.object == val: + return node + + ret = None + if node.left: + ret = self._dfs(val, node.left) + if ret: + return ret + + if node.right: + ret = self._dfs(val, node.right) + if ret: + return ret + + return None + + def BFS(self, val): + stack = [] + + stack.append(self.root) + curr = None + while (len(stack) != 0): + curr = stack[0] + del stack[0] + print "Examining: " + str(curr.object) + if curr.object == val: + return curr + if curr.left: + stack.append(curr.left) + if curr.right: + stack.append(curr.right) + + return None + + def GetBoundary(self): + edges = [] + edges.append(self.root) + + edges.extend(self._getLeftEdges(self.root.left)) + edges.extend(self._getRightEdges(self.root.right)) + + return edges + + def _getLeftEdges(self, nodes): + ret = [] + tmp = None + if nodes == None: + return nodes + if nodes.parent.right == nodes: + if not nodes.right and not nodes.left: + ret.append(nodes) + elif nodes.parent.left == nodes: + ret.append(nodes) + + tmp = self._getLeftEdges(nodes.left) + if tmp: + ret.extend(tmp) + tmp = self._getLeftEdges(nodes.right) + if tmp: + ret.extend(tmp) + + return ret + + def _getRightEdges(self, nodes): + ret = [] + tmp = None + if nodes == None: + return nodes + + tmp = self._getRightEdges(nodes.left) + if tmp: + ret.extend(tmp) + tmp = self._getRightEdges(nodes.right) + if tmp: + ret.extend(tmp) + + if nodes.parent.right == nodes: + ret.append(nodes) + elif nodes.parent.left == nodes: + if not nodes.right and not nodes.left: + ret.append(nodes) + + + + return ret \ No newline at end of file diff -r 7efa32a4dc11aeb6463ff1a1120f8a5f745ee5be -r 6cd079b8d44be4bf692c64502ad981f31b31c3c2 python/algorithms/algorithms.py --- a/python/algorithms/algorithms.py Wed Feb 20 23:29:56 2013 -0600 +++ b/python/algorithms/algorithms.py Fri Feb 22 23:18:18 2013 -0600 @@ -1,7 +1,27 @@ from SortAlgorithm import * +from SearchAlgorithm import * +from Tree import Tree +from Node import Node -sort1 = QuickSort() -sort1.initContainer(["test1","test2","tres343","asdf"]) -sort1.Sort() -print str(sort1) +#sort1 = QuickSort() +#sort1.initContainer([3,2,7,3,1]) +#sort1.Sort() +#print str(sort1) #print('Hello World') +#search1 = BinarySearch() +#search1.initContainer(sort1.getContainer()) +#print search1.Search(0) + +root = Node(30) +l = root.addLeft(20) +r = root.addRight(40) +l.addLeft(10).addLeftRight(5, 15) +l.addRight(25).addRight(28) +r.addLeft(35) +r.addRight(50).addRight(41) + +T = Tree(root) + +for i in T.GetBoundary(): + print i.object +#print T.GetBoundary() \ No newline at end of file