8000 Merge branch 'master' into yashu · AllAlgorithms/python@5e59c93 · GitHub
[go: up one dir, main page]
Skip to content

Commit 5e59c93

Browse files
abranheabranhe
authored
Merge branch 'master' into yashu
2 parents d57fbd5 + 802e23c commit 5e59c93

File tree

3 files changed

+185
-0
lines changed

3 files changed

+185
-0
lines changed

‎algorithms/sorting/cocktail_sort.py

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
def cocktailSort(array)
2+
n = len(array)
3+
swap = 1
4+
begin = 0
5+
end = n-1
6+
#Sorting start
7+
while (swap == 1):
8+
swap = 0
9+
10+
#sorting from begin
11+
for i in range (begin, end):
12+
if (a[i] > a[i+1]) :
13+
a[i], a[i+1]= a[i+1], a[i]
14+
swap=1
15+
16+
if (swap==0):
17+
break swap = 0
18+
19+
end = end-1
20+
#sorting from end
21+
for i in range(end-1, begin-1,-1):
22+
if (a[i] > a[i+1]):
23+
a[i], a[i+1] = a[i+1], a[i]
24+
swap = 1
25+
26+
begin = begin+1

‎data-structures/InorderTreeTraversal.py

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
class Node:
2+
"""A binary tree node"""
3+
def __init__(self, data, left=None, right=None):
4+
self.data = data
5+
self.left = left
6+
self.right = right
7+
8+
9+
def morris_traversal(root):
10+
"""Generator function for iterative inorder tree traversal"""
11+
12+
current = root
13+
14+
while current is not None:
15+
16+
if current.left is None:
17+
yield current.data
18+
current = current.right
19+
else:
20+
21+
# Find the inorder predecessor of current
22+
pre = current.left
23+
while pre.right is not None and pre.right is not current:
24+
pre = pre.right
25+
26+
if pre.right is None:
27+
28+
# Make current as right child of its inorder predecessor
29+
pre.right = current
30+
current = current.left
31+
32+
else:
33+
# Revert the changes made in the 'if' part to restore the
34+
# original tree. i.e., fix the right child of predecessor
35+
pre.right = None
36+
yield current.data
37+
current = current.right
38+
39+
# Driver program to test the above function
40+
41+
root = Node(1,
42+
right = Node(3),
43+
left = Node(2,
44+
left = Node(4),
45+
right = Node(5)
46+
)
47+
)
48+
49+
for v in morris_traversal(root):
50+
print(v, end=' ')

‎data-structures/linked-lists/circulardoublylinkedlist.py

Lines changed: 109 additions & 0 deletions
< 67ED /tr>
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
class Node:
2+
def __init__(self, data):
3+
self.data = data
4+
self.next = None
5+
self.prev = None
6+
7+
8+
class CircularDoublyLinkedList:
9+
def __init__(self):
10+
self.first = None
11+
12+
def get_node(self, index):
13+
current = self.first
14+
for i in range(index):
15+
current = current.next
16+
if current == self.first:
17+
return None
18+
return current
19+
20+
def insert_after(self, ref_node, new_node):
21+
new_node.prev = ref_node
22+
new_node.next = ref_node.next
23+
new_node.next.prev = new_node
24+
ref_node.next = new_node
25+
26+
def insert_before(self, ref_node, new_node):
27+
self.insert_after(ref_node.prev, new_node)
28+
29+
def insert_at_end(self, new_node):
30+
if self.first is None:
31+
self.first = new_node
32+
new_node.next = new_node
33+
new_node.prev = new_node
34+
else:
35+
self.insert_after(self.first.prev, new_node)
36+
37+
def insert_at_beg(self, new_node):
38+
self.insert_at_end(new_node)
39+
self.first = new_node
40+
41+
def remove(self, node):
42+
if self.first.next == self.first:
43+
self.first = None
44+
else:
45+
node.prev.next = node.next
46+
node.next.prev = node.prev
47+
if self.first == node:
48+
self.first = node.next
49+
50+
def display(self):
51+
if self.first is None:
52+
return
53+
current = self.first
54+
while True:
55+
print(current.data, end = ' ')
56+
current = current.next
57+
if current == self.first:
58+
break
59+
60+
61+
a_cdllist = CircularDoublyLinkedList()
62+
63+
print('Menu')
64+
print('insert <data> after <index>')
65+
print('insert <data> before <index>')
66+
print('insert <data> at beg')
67+
print('insert <data> at end')
68+
print('remove <index>')
69+
print('quit')
70+
71+
while True:
72+
print('The list: ', end = '')
73+
a_cdllist.display()
74+
print()
75+
do = input('What would you like to do? ').split()
76+
77+
operation = do[0].strip().lower()
78+
79+
if operation == 'insert':
80+
data = int(do[1])
81+
position = do[3].strip().lower()
82+
new_node = Node(data)
83+
suboperation = do[2].strip().lower()
84+
if suboperation == 'at':
85+
if position == 'beg':
86+
a_cdllist.insert_at_beg(new_node)
87+
elif position == 'end':
88+
a_cdllist.insert_at_end(new_node)
89+
else:
90+
index = int(position)
91+
ref_node = a_cdllist.get_node(index)
92+
if ref_node is None:
93+
print('No such index.')
94+
continue
95+
if suboperation == 'after':
96+
a_cdllist.insert_after(ref_node, new_node)
97+
elif suboperation == 'before':
98+
a_cdllist.insert_before(ref_node, new_node)
99+
100+
elif operation == 'remove':
101+
index = int(do[1])
102+
node = a_cdllist.get_node(index)
103+
if node is None:
104+
print('No such index.')
105+
continue
106+
a_cdllist.remove(node)
107+
108+
elif operation == 'quit':
109+
break

0 commit comments

Comments
 (0)
0