Skip to content

Commit 4936858

Browse files
nryoungnryoung
committed
Massive clean up of documentation.
1 parent fff59da commit 4936858

File tree

15 files changed

+44
-136
lines changed

15 files changed

+44
-136
lines changed

‎algorithms/searching/binary_search.py‎

Lines changed: 1 addition & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,22 +1,16 @@
11
"""
22
binary_search.py
33
4-
This module implements binary search on a sorted list.
4+
Implementation of binary search on a sorted list.
55
66
Binary Search Overview:
77
------------------------
88
Recursively partitions the list until the key is found.
99
10-
Pre: a sorted list[0,...n,] integers and the key to search for.
11-
12-
Post: returns the index of where the first element that matches the key.
13-
1410
Time Complexity: O(lg n)
1511
1612
Psuedo Code: http://en.wikipedia.org/wiki/Binary_search
1713
18-
binary_search.search(sorted_list, key) -> index
19-
binary_search.search(sorted_list, key) -> False
2014
"""
2115

2216

‎algorithms/searching/bmh_search.py‎

Lines changed: 1 addition & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -1,42 +1,19 @@
11
"""
22
bmh_search.py
33
4-
This module implements bmh search to find a substring in a string
4+
Implementation of bmh search to find a substring in a string
55
66
BMH Search Overview:
77
--------------------
88
Uses a bad-character shift of the rightmost character of the window to
99
compute shifts.
1010
11-
The trick to this algorithm is `bmbc`, a lookup table with a default
12-
value equal to the length of the pattern to be searched, so that
13-
the algorithm can skip `len(pattern)` indices through the string
14-
for efficiency's sake. For example, if we're searching through the
15-
string "cotton milled paper" for the pattern "grumble", we look at
16-
the last letter "r" (BMH goes backwards through a string) and notices
17-
that it is not equal to "e". Thus, we can afford to jump our search
18-
index back a whole seven characters.
19-
20-
However, not all the entries in `bmbc` are equal to `len(pattern)`.
21-
If we searched the string "adventure time" for "grumble", we'd find
22-
the "e" to match but mismatch the "m" and "l" in the string and
23-
pattern, respectively. In this case, we can only jump back six
24-
characters safely, which is why `bmbc` contains values that are not
25-
simply `len(pattern)`.
26-
27-
Pre: a string > substring.
28-
29-
Post: returns a list of indices where the substring was found.
30-
3111
Time: Complexity: O(m + n), where m is the substring to be found.
3212
3313
Space: Complexity: O(m), where m is the substring to be found.
3414
3515
Psuedo Code: https://github.com/FooBarWidget/boyer-moore-horspool
36-
(converted from C++)
3716
38-
bmh_search.search(string, substring) -> list[integers]
39-
bmh_search.search(string, substring) -> list[empty]
4017
"""
4118

4219

‎algorithms/searching/kmp_search.py‎

Lines changed: 1 addition & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,22 +1,16 @@
11
"""
22
kmp_search.py
33
4-
This module implements kmp search on a sorted list.
4+
Implementation of kmp search on a sorted list.
55
66
KMP Search Overview:
77
------------------------
88
Uses a prefix function to reduce the searching time.
99
10-
Pre: a string > substring.
11-
12-
Post: returns a list of indices where the substring was found.
13-
1410
Time Complexity: O(n + k), where k is the substring to be found
1511
1612
Psuedo Code: CLRS. Introduction to Algorithms. 3rd ed.
1713
18-
kmp_search.search(sorted_list) -> list[integers]
19-
kmp_search.search(sorted_list) -> list[empty]
2014
"""
2115

2216

‎algorithms/searching/rabinkarp_search.py‎

Lines changed: 4 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,26 +1,22 @@
11
"""
22
rabinkarp_search.py
33
4-
This module implements Rabin-Karp search on a given string.
4+
Implementation of Rabin-Karp search on a given string.
55
66
Rabin-Karp Search Overview:
77
------------------------
8-
Search for a substring in a given string, by comparing hash values of the strings.
9-
10-
Pre: two strings, one to search in and one to search for.
11-
12-
Post: returns a list of indices where the substring was found
8+
Search for a substring in a given string, by comparing hash values
9+
of the strings.
1310
1411
Time Complexity: O(nm)
1512
1613
Psuedo Code: http://en.wikipedia.org/wiki/Rabin-Karp_algorithm
1714
18-
rabinkarp_search.search(searchString, targetString) -> list[integers]
19-
rabinkarp_search.search(searchString, targetString) -> list[empty]
2015
"""
2116

2217
from hashlib import md5
2318

19+
2420
def search(s, sub):
2521
n, m = len(s), len(sub)
2622
hsub_digest = md5(sub).digest()

‎algorithms/shuffling/knuth.py‎

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -2,11 +2,12 @@
22
knuth.py
33
Implementation of the Fisher-Yates/Knuth shuffle
44
5-
Pre: Takes any list, unshuffled
6-
Post: Returns list shuffled randomly
5+
Fisher-Yates/Knuth Overview:
6+
----------------------------
7+
Randomly picks integers to swap elements in an ubiased manner.
78
8-
Time Complexity: n
9-
Space Complexity: n
9+
Time Complexity: O(n)
10+
Space Complexity: O(n)n
1011
1112
Pseudocode: http://en.wikipedia.org/wiki/Fisher%E1%80%93Yates_shuffle
1213

‎algorithms/sorting/bogo_sort.py‎

Lines changed: 3 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,24 +1,18 @@
11
"""
22
bogo_sort.py
33
4-
This module implements bogo sort on an unsorted list and
5-
returns the list in sorted order.
4+
Implementation of bogo sort on a list and returns a sorted list.
65
76
Bogo Sort Overview:
87
-------------------
9-
If list is not in order, picks two elements at random and swaps them.
10-
Repeat.
11-
12-
Pre:
8+
A naive sorting that picks two elements at random and swaps them.
139
1410
Time Complexity: O(n * n!)
1511
16-
Space Complexity: O(n) total
12+
Space Complexity: O(1) Auxiliary
1713
1814
Stable: No
1915
20-
bogo_sort.sort(list) -> sorted_list
21-
2216
WARNING: This algorithm may never sort the list correctly.
2317
"""
2418

‎algorithms/sorting/bubble_sort.py‎

Lines changed: 4 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,26 +1,20 @@
11
"""
22
bubble_sort.py
33
4-
This module implements bubble sort on an unsorted list and returns the sorted list.
4+
Implementation of bubble sort on a list and returns a sorted list.
55
66
Bubble Sort Overview:
77
---------------------
8-
A naive sorting that compares and swaps adjacent elements from 0,1,2,...,n.
8+
A naive sorting that compares and swaps adjacent elements
99
10-
Pre: an unsorted list[0,...,n] of integers.
10+
Time Complexity: O(n**2)
1111
12-
Post: returns a sorted list[0,...,n] in ascending order.
13-
14-
Time Complexity: O(n^2)
15-
16-
Space Complexity: O(n) total
12+
Space Complexity: O(1) Auxiliary
1713
1814
Stable: Yes
1915
2016
Psuedo code: http://en.wikipedia.org/wiki/Bubble_sort
2117
22-
bubble_sort.sort(list) -> sorted_list
23-
2418
"""
2519

2620

‎algorithms/sorting/cocktail_sort.py‎

Lines changed: 4 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,26 +1,21 @@
11
"""
22
cocktail_sort.py
33
4-
This module implements a cocktail sort (aka bidirectional bubble sort,
5-
or the happy hour sort) on an unsorted list.
4+
Implementation of cocktail sort (aka bidirectional bubble sort,
5+
or the happy hour sort) on a list.
66
77
Cocktail Sort Overview:
88
------------------------
99
Walk the list bidirectionally, swapping neighbors if one should come
1010
before/after the other.
1111
12-
Pre: An unsorted list elements that can be compared.
12+
Time Complexity: O(n**2)
1313
14-
Post: A sorted list of elements in ascending order.
15-
16-
Time Complexity: O(n^2)
17-
18-
Space Complexity: O(n) total
14+
Space Complexity: O(1) Auxiliary
1915
2016
Stable: Yes
2117
2218
Psuedo Code: http://en.wikipedia.org/wiki/Cocktail_sort
23-
cocktail_sort.sort(list) -> sorted_list
2419
"""
2520

2621

‎algorithms/sorting/comb_sort.py‎

Lines changed: 3 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,26 +1,20 @@
11
"""
22
comb_sort.py
33
4-
This module implements comb sort on an unsorted list and returns a sorted list.
4+
Implementation of comb sort on a list and returns a sorted list.
55
66
Comb Sort Overview:
77
-------------------
88
Improves on bubble sort by using a gap sequence to remove turtles.
99
10-
Pre: an unsorted list[0,...,n] of integers.
10+
Time Complexity: O(n**2)
1111
12-
Post: returns a sorted list[0,...,n] in ascending order.
13-
14-
Time Complexity: O(n^2)
15-
16-
Space Complexity: O(n) total
12+
Space Complexity: O(1) Auxiliary
1713
1814
Stable: Yes
1915
2016
Psuedo code: http://en.wikipedia.org/wiki/Comb_sort
2117
22-
comb_sort.sort(list) -> sorted_list
23-
2418
"""
2519

2620

‎algorithms/sorting/heap_sort.py‎

Lines changed: 4 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,26 +1,20 @@
11
"""
22
heap_sort.py
33
4-
This module implements heap sort on an unsorted list and returns a sorted list.
4+
Implementation of heap sort on a list and returns a sorted list.
55
66
Heap Sort Overview:
77
-------------------
8-
Uses a the max heap data structure implemented in a list.
8+
Uses the max heap data structure implemented in a list.
99
10-
Pre: an unsorted list[0,...,n] of integers.
10+
Time Complexity: O(n log n)
1111
12-
Post: returns a sorted list[0,...,n] in ascending order.
13-
14-
Time Complexity: O(n^2)
15-
16-
Space Complexity: O(n) total
12+
Space Complexity: O(1) Auxiliary
1713
1814
Stable: Yes
1915
2016
Psuedo Code: CLRS. Introduction to Algorithms. 3rd ed.
2117
22-
heap_sort.sort(list) -> sorted_list
23-
2418
"""
2519

2620

0 commit comments

Comments
 (0)