algorithms

algorithms Commit Details


Date:2013-02-22 23:18:00 (11 years 9 months ago)
Author:Natalie Adams
Branch:default
Commit:6cd079b8d44b
Parents: 7efa32a4dc11
Message:Adding and update algorithms
Changes:
Apython/algorithms/Node.py (full)
Apython/algorithms/SearchAlgorithm.py (full)
Apython/algorithms/Tree.py (full)
Mcpp/algorithms/src/BinarySearch.h (1 diff)
Mcpp/algorithms/src/Node.h (2 diffs)
Mcpp/algorithms/src/QuickSort.h (2 diffs)
Mcpp/algorithms/src/Tree.h (1 diff)
Mcpp/algorithms/src/main.cpp (2 diffs)
Mpython/algorithms/SortAlgorithm.py (1 diff)
Mpython/algorithms/algorithms.py (1 diff)

File differences

cpp/algorithms/src/BinarySearch.h
2626
2727
2828
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
2956
␉}␍␊
};␍␊
␍␊
template <class T>␍␊
class BinarySearchRecursive : public SearchAlgorithm<T>␍␊
{␍␊
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
cpp/algorithms/src/Node.h
3535
3636
3737
38
3839
3940
4041
......
4243
4344
4445
46
4547
4648
4749
␉␉if (this->left != null)␍␊
␉␉␉throw std::string("Left is not null!");␍␊
␉␉this->left = createNode(obj);␍␊
␉␉return this->left;␍␊
␉}␍␊
␍␊
␉Node<T> * addRight(T obj)␍␊
␉␉if (this->right != null)␍␊
␉␉␉throw std::string("Right is not null!");␍␊
␉␉this->right = createNode(obj);␍␊
␉␉return this->right;␍␊
␉}␍␊
␍␊
␉void addLeftRight(T left, T right)␍␊
cpp/algorithms/src/QuickSort.h
55
66
77
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
881
982
1083
......
1588
1689
1790
18
19
91
92
2093
21
22
23
24
25
94
2695
27
96
97
98
99
100
101
102
28103
29
30
104
105
106
31107
32108
33
34
35
109
110
111
112
113
36114
37115
38116
#include <algorithm>␍␊
␍␊
template <class T>␍␊
class QuickSortWiki : public SortAlgorithm<T>␍␊
{␍␊
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 T>␍␊
class QuickSort2 : public SortAlgorithm<T>␍␊
{␍␊
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 T>␍␊
class QuickSort : public SortAlgorithm<T>␍␊
{␍␊
public:␍␊
␍␊
␉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);␍␊
␉}␍␊
};␍␊
␍␊
cpp/algorithms/src/Tree.h
3434
3535
3636
37
38
39
40
37
38
39
40
4141
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
4259
60
4361
4462
4563
␉␉//DeleteTree(root);␍␊
␉}␍␊
␍␊
␉//Node<T> * DFS(T value)␍␊
␉//{␍␊
␉//␉return dfs(value, this->root);␍␊
␉//}␍␊
␉Node<T> * DFS(T value)␍␊
␉{␍␊
␉␉return dfs(value, this->root);␍␊
␉}␍␊
␍␊
␉Node<T> * dfs(T value, Node<T> * nodes)␍␊
␉{␍␊
␉␉if (nodes == null)␍␊
␉␉␉return null;␍␊
␉␉cout << "Examining: " << nodes->object << endl;␍␊
␉␉if (nodes->object == value)␍␊
␉␉␉return nodes;␍␊
␉␉Node<T> * 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<T> * BFS(T value)␍␊
␉{␍␊
cpp/algorithms/src/main.cpp
1616
1717
1818
19
19
2020
2121
22
23
24
25
26
22
23
24
25
26
27
28
2729
28
30
2931
3032
3133
......
3941
4042
4143
42
43
44
44
45
46
47
4548
4649
4750
␍␊
int main()␍␊
{␍␊
␉/*//sort1.initContainer(create_vector<string>("test")("test2"));␍␊
␉//sort1.initContainer(create_vector<string>("test")("test2"));␍␊
␉//cout << sort1.ToString();␍␊
␉//vector<int> arr1 = create_vector<int>(␍␊
␉MedianSort<int> sort1;␍␊
␉sort1.initContainer(create_vector<int>(3)(2)(4)(3)(1));␍␊
␉sort1.Sort();␍␊
␉cout << sort1.ToString() << endl;␍␊
␉//BinarySearch<int> search1;␍␊
␉//QuickSort2<int> sort1;␍␊
␉//sort1.initContainer(create_vector<int>(3)(2)(7)(3)(1));␍␊
␉//sort1.initContainer(create_vector<int>(1)(2)(7)(3));␍␊
␉//cout << sort1.ToString() << endl;␍␊
␉//sort1.Sort();␍␊
␉//cout << sort1.ToString() << endl;␍␊
␉//BinarySearchRecursive<int> search1;␍␊
␉//search1.initContainer(sort1.getContainer());␍␊
␉//cout << search1.Search(7) << endl;*/␍␊
␉//cout << search1.Search(3) << endl;␍␊
␉Node<int> * root = new Node<int>(30);␍␊
␉Node<int> * l = root->addLeft(20);␍␊
␉Node<int> * r = root->addRight(40);␍␊
␉//{␍␊
␉//␉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<int> t(root);␍␊
python/algorithms/Node.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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)␍␊
␍␊
python/algorithms/SearchAlgorithm.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
python/algorithms/SortAlgorithm.py
1717
1818
1919
20
20
2121
2222
2323
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):␍␊
python/algorithms/Tree.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
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
python/algorithms/algorithms.py
11
2
3
4
25
3
4
5
6
6
7
8
9
710
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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()

Archive Download the corresponding diff file

Branches

Tags

Page rendered in 0.44672s using 14 queries.