forked from laurentluce/python-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlist.py
More file actions
122 lines (102 loc) · 2.49 KB
/
Copy pathlist.py
File metadata and controls
122 lines (102 loc) · 2.49 KB
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
def find_int(i, l):
"""Find integer in a sorted list.
Example: 4 in [1, 3, 4, 6, 7, 9] -> 2
@param i integer to find.
@param l sorted list.
@returns index if found, None if not.
"""
if l:
p_idx = len(l) / 2
p = l[p_idx]
if i == p:
return p_idx
elif len(l) == 1:
return
elif i < p:
res = find_int(i, l[:p_idx])
if res:
return res
elif i > p:
res = find_int(i, l[p_idx:])
if res:
return res + p_idx
def find_max_sub(l):
"""Find subset with higest sum.
Example: [-2, 3, -4, 5, 1, -5] -> (3,4), 6
@param l list
@returns subset bounds and highest sum
"""
# max sum
max = l[0]
# current sum
m = 0
# max sum subset bounds
bounds = (0, 0)
# current subset start
s = 0
for i in range(len(l)):
m += l[i]
if m > max:
max = m
bounds = (s, i)
elif m < 0:
m = 0
s = i+1
return bounds, max
def merge_sort(l):
"""Sort list using merge sort.
Complexity: O(n log n)
@param l list to sort.
@returns sorted list.
"""
def merge(l1, l2):
"""Merge sorted lists l1 and l2.
[1, 2, 4], [1, 3, 4, 5] -> [1, 1, 2, 3, 4, 5]
@param l1 sorted list
@param l2 sorted list
@returns merge sorted list
"""
res = []
i = 0
j = 0
while i < len(l1) and j < len(l2):
if l1[i] <= l2[j]:
res.append(l1[i])
i += 1
elif l2[j] < l1[i]:
res.append(l2[j])
j += 1
while i < len(l1):
res.append(l1[i])
i += 1
while j < len(l2):
res.append(l2[j])
j += 1
return res
length = len(l)
if length <= 1:
return l
mid = length / 2
h1 = merge_sort(l[:mid])
h2 = merge_sort(l[mid:])
return merge(h1, h2)
def quicksort(l):
"""Sort list using quick sort.
Complexity: O(n log n). Worst: O(n2)
@param l list to sort.
@returns sorted list.
"""
if len(l) <= 1:
return l
pivot = l[0]
less = []
equal = []
greater = []
for e in l:
if e < pivot:
less.append(e)
elif e == pivot:
equal.append(e)
else:
greater.append(e)
return quicksort(less) + equal + quicksort(greater)