Skip to content

Commit 5fdabd3

Browse files
kishinmanglanikishinmanglani
committed
Merge branch 'master' of ssh://github.com/kishinmanglani/algorithms
2 parents 5281800 + 96ebe18 commit 5fdabd3

File tree

9 files changed

+77
-70
lines changed

9 files changed

+77
-70
lines changed

‎AUTHORS.rst‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,3 +7,4 @@ List of contributors:
77
- kngspook
88
- cmackenziek
99
- nyqvist
10+
- jabagawee

‎algorithms/searching/bmh_search.py‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,8 @@
2222
bmh_search.search(string, substring) -> list[integers]
2323
bmh_search.search(string, substring) -> list[empty]
2424
"""
25+
26+
2527
def search(text, pattern):
2628
m = len(pattern)
2729
n = len(text)
@@ -44,5 +46,5 @@ def search(text, pattern):
4446
if j == -1:
4547
offsets.append(i + 1)
4648
k += bmbc[ord(text[k])]
47-
49+
4850
return offsets

‎algorithms/searching/rabinkarp_search.py‎

Lines changed: 13 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -21,15 +21,16 @@
2121

2222
import hashlib
2323

24-
def search(s,sub):
25-
n, m = len(s), len(sub)
26-
hsub, hs = hashlib.md5(sub), hashlib.md5(s[0:m])
27-
28-
for i in range(n - m + 1):
29-
if hs.hexdigest() == hsub.hexdigest():
30-
if s[i:i+m] == sub:
31-
return i
32-
news = s[i+1:i+m+1]
33-
hs = hashlib.md5(news)
34-
35-
return False
24+
25+
def search(s, sub):
26+
n, m = len(s), len(sub)
27+
hsub, hs = hashlib.md5(sub), hashlib.md5(s[0:m])
28+
29+
for i in range(n - m + 1):
30+
if hs.hexdigest() == hsub.hexdigest():
31+
if s[i:i + m] == sub:
32+
return i
33+
news = s[i + 1:i + m + 1]
34+
hs = hashlib.md5(news)
35+
36+
return False

‎algorithms/shuffling/knuth.py‎

Lines changed: 16 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,22 +1,22 @@
1-
"""
2-
knuth.py
3-
Implementation of the Fisher-Yates/Knuth shuffle
4-
5-
Pre: Takes any list, unshuffled
6-
Post: Returns list shuffled randomly
7-
8-
Time Complexity: n
9-
Space Complexity: n
10-
11-
Pseudocode: http://en.wikipedia.org/wiki/Fisher%E1%80%93Yates_shuffle
1+
"""
2+
knuth.py
3+
Implementation of the Fisher-Yates/Knuth shuffle
4+
5+
Pre: Takes any list, unshuffled
6+
Post: Returns list shuffled randomly
7+
8+
Time Complexity: n
9+
Space Complexity: n
10+
11+
Pseudocode: http://en.wikipedia.org/wiki/Fisher%E1%80%93Yates_shuffle
1212
1313
"""
1414
import random
1515

1616

1717
def shuffle(li):
18-
random.seed()
19-
for i in xrange(len(li) - 1, 0, -1):
20-
j = random.randint(0, i)
21-
li[i], li[j] = li[j], li[i]
22-
return li
18+
random.seed()
19+
for i in xrange(len(li) - 1, 0, -1):
20+
j = random.randint(0, i)
21+
li[i], li[j] = li[j], li[i]
22+
return li

‎algorithms/sorting/bogo_sort.py‎

Lines changed: 27 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,15 @@
11
"""
2-
bogo_sort.py
3-
4-
This module implements bogo sort on an unsorted list and
5-
returns the list in sorted order.
6-
7-
Bogo Sort Overview:
8-
-------------------
9-
If list is not in order, picks two elements at random and swaps them.
10-
Repeat.
11-
12-
Pre:
2+
bogo_sort.py
3+
4+
This module implements bogo sort on an unsorted list and
5+
returns the list in sorted order.
6+
7+
Bogo Sort Overview:
8+
-------------------
9+
If list is not in order, picks two elements at random and swaps them.
10+
Repeat.
11+
12+
Pre:
1313
1414
Time Complexity: O(n * n!)
1515
@@ -24,22 +24,24 @@
2424

2525
import random
2626

27+
2728
def sort(seq):
28-
if len(seq) == 1: return seq
29-
random.seed()
30-
while not is_sorted(seq):
31-
if len(seq) == 2:
32-
i = 0
33-
j = 1
34-
else:
35-
i = random.randint(0, len(seq)-2)
36-
j = random.randint(i, len(seq)-1)
37-
seq[i], seq[j] = seq[j], seq[i]
38-
return seq
29+
if len(seq) == 1:
30+
return seq
31+
random.seed()
32+
while not is_sorted(seq):
33+
if len(seq) == 2:
34+
i = 0
35+
j = 1
36+
else:
37+
i = random.randint(0, len(seq) - 2)
38+
j = random.randint(i, len(seq) - 1)
39+
seq[i], seq[j] = seq[j], seq[i]
40+
return seq
3941

4042

4143
def is_sorted(seq):
42-
for i in xrange(1, len(seq)):
43-
if seq[i-1] > seq[i]:
44+
for i in xrange(1, len(seq)):
45+
if seq[i - 1] > seq[i]:
4446
return False
45-
return True
47+
return True

‎algorithms/sorting/cocktail_sort.py‎

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@
1010
before/after the other.
1111
1212
Pre: An unsorted list elements that can be compared.
13-
13+
1414
Post: A sorted list of elements in ascending order.
1515
1616
Time Complexity: O(n^2)
@@ -23,24 +23,24 @@
2323
cocktail_sort.sort(list) -> sorted_list
2424
"""
2525

26+
2627
def sort(seq):
2728
lower_bound = -1
28-
upper_bound = len(seq)-1
29+
upper_bound = len(seq) - 1
2930
swapped = True
3031
while swapped:
3132
swapped = False
3233
lower_bound += 1
3334
for i in range(lower_bound, upper_bound):
34-
if seq[i] > seq[i+1]:
35-
seq[i], seq[i+1] = seq[i+1], seq[i]
35+
if seq[i] > seq[i + 1]:
36+
seq[i], seq[i + 1] = seq[i + 1], seq[i]
3637
swapped = True
3738
if not swapped:
3839
break
3940
swapped = False
4041
upper_bound -= 1
4142
for i in range(upper_bound, lower_bound, -1):
42-
if seq[i] < seq[i-1]:
43-
seq[i], seq[i-1] = seq[i-1], seq[i]
43+
if seq[i] < seq[i - 1]:
44+
seq[i], seq[i - 1] = seq[i - 1], seq[i]
4445
swapped = True
4546
return seq
46-

‎algorithms/tests/test_searching.py‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -44,18 +44,20 @@ def test_kmpsearch(self):
4444
self.assertIs(rv1, 9)
4545
self.assertFalse(rv2)
4646

47+
4748
class TestRabinKarpSearch(unittest.TestCase):
4849
"""
4950
Tests Rabin-Karp search on string "ABCDEFGHIJKLMNOP"
5051
"""
5152

5253
def test_rabinkarpsearch(self):
5354
self.string = "ABCDEFGHIJKLMNOP"
54-
rv1 = rabinkarp_search.search(self.string,"MNOP")
55-
rv2 = rabinkarp_search.search(self.string,"BCA")
56-
self.assertIs(rv1,12)
55+
rv1 = rabinkarp_search.search(self.string, "MNOP")
56+
rv2 = rabinkarp_search.search(self.string, "BCA")
57+
self.assertIs(rv1, 12)
5758
self.assertFalse(rv2)
5859

60+
5961
class TestBMHSearch(unittest.TestCase):
6062
"""
6163
Tests BMH search on string "ABCDE FG ABCDEABCDEF"
@@ -65,7 +67,5 @@ def test_bmhsearch(self):
6567
self.string = "ABCDE FG ABCDEABCDEF"
6668
rv1 = bmh_search.search(self.string, "ABCDEA")
6769
rv2 = bmh_search.search(self.string, "ABCDER")
68-
self.assertIs(rv1[0],9)
70+
self.assertIs(rv1[0], 9)
6971
self.assertFalse(rv2)
70-
71-

‎algorithms/tests/test_shuffling.py‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,14 @@
11
import unittest
22
from ..shuffling import knuth
33

4+
45
class ShufflingAlgorithmTestCase(unittest.TestCase):
56
"""
67
Shared code for shuffling unit tests.
78
"""
89

910
def setUp(self):
10-
self.sorted = range(10)
11+
self.sorted = range(10)
1112

1213

1314
class TestKnuthShuffle(ShufflingAlgorithmTestCase):

‎algorithms/tests/test_sorting.py‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@ class SortingAlgorithmTestCase(unittest.TestCase):
77
"""
88
Shared code for a sorting unit test.
99
"""
10-
10+
1111
def setUp(self):
1212
self.input = range(10)
1313
random.shuffle(self.input)
@@ -101,6 +101,7 @@ def test_combsort(self):
101101
self.output = comb_sort.sort(self.input)
102102
self.assertEqual(self.correct, self.output)
103103

104+
104105
class TestCocktailSort(SortingAlgorithmTestCase):
105106
"""
106107
Tests Cocktail sort on a small range from 0-9
@@ -109,4 +110,3 @@ class TestCocktailSort(SortingAlgorithmTestCase):
109110
def test_cocktailsort(self):
110111
self.output = cocktail_sort.sort(self.input)
111112
self.assertEqual(self.correct, self.output)
112-

0 commit comments

Comments
 (0)