aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/algorithms/impl
diff options
context:
space:
mode:
Diffstat (limited to 'algorithms/impl')
-rw-r--r--algorithms/impl/__init__.py2
-rw-r--r--algorithms/impl/bubble_sort.py6
-rw-r--r--algorithms/impl/heapsort.py11
-rw-r--r--algorithms/impl/insertion_sort.py5
-rw-r--r--algorithms/impl/median.py6
-rw-r--r--algorithms/impl/merge_sort.py6
-rw-r--r--algorithms/impl/quicksort.py17
-rw-r--r--algorithms/impl/selection_sort.py5
8 files changed, 58 insertions, 0 deletions
diff --git a/algorithms/impl/__init__.py b/algorithms/impl/__init__.py
index 579b091..84bd702 100644
--- a/algorithms/impl/__init__.py
+++ b/algorithms/impl/__init__.py
@@ -9,8 +9,10 @@ from pkgutil import iter_modules
from .. import algorithm
+
_ALGORITHMS_NAME = '_ALGORITHMS'
+
def refresh_algorithms():
all_algorithms = {}
diff --git a/algorithms/impl/bubble_sort.py b/algorithms/impl/bubble_sort.py
index 95fb661..0ea66bb 100644
--- a/algorithms/impl/bubble_sort.py
+++ b/algorithms/impl/bubble_sort.py
@@ -7,6 +7,7 @@ import sys
from ..algorithm import SortingAlgorithm
+
def bubble_sort(xs):
while True:
swapped = False
@@ -18,6 +19,7 @@ def bubble_sort(xs):
break
return xs
+
def bubble_sort_optimized(xs):
n = len(xs)
while True:
@@ -31,20 +33,24 @@ def bubble_sort_optimized(xs):
break
return xs
+
_ALGORITHMS = [
SortingAlgorithm('bubble_sort', 'Bubble sort', bubble_sort),
SortingAlgorithm('bubble_sort_optimized', 'Bubble sort (optimized)', bubble_sort_optimized),
]
+
def _parse_args(args=None):
if args is None:
args = sys.argv[1:]
return list(map(int, args))
+
def main(args=None):
xs = _parse_args(args)
print(bubble_sort(list(xs)))
print(bubble_sort_optimized(list(xs)))
+
if __name__ == '__main__':
main()
diff --git a/algorithms/impl/heapsort.py b/algorithms/impl/heapsort.py
index bf9f464..81bea20 100644
--- a/algorithms/impl/heapsort.py
+++ b/algorithms/impl/heapsort.py
@@ -9,6 +9,7 @@ from ..algorithm import SortingAlgorithm
# Disclaimer: implemented in the most literate way.
+
def heapsort(xs):
_heapify(xs)
first, last = 0, len(xs) - 1
@@ -17,26 +18,32 @@ def heapsort(xs):
_siftdown(xs, first, end - 1)
return xs
+
# In a heap stored in a zero-based array,
# left_child = node * 2 + 1
# right_child = node * 2 + 2
# parent = (node - 1) // 2
+
def _get_parent(node):
return (node - 1) // 2
+
def _get_left_child(node):
return node * 2 + 1
+
def _get_right_child(node):
return node * 2 + 2
+
def _heapify(xs):
last = len(xs) - 1
first_parent, last_parent = 0, _get_parent(last)
for parent in range(last_parent, first_parent - 1, -1):
_siftdown(xs, parent, last)
+
def _siftdown(xs, start, end):
root = start
while True:
@@ -54,18 +61,22 @@ def _siftdown(xs, start, end):
else:
break
+
_ALGORITHMS = [
SortingAlgorithm('heapsort', 'Heapsort', heapsort),
]
+
def _parse_args(args=None):
if args is None:
args = sys.argv[1:]
return list(map(int, args))
+
def main(args=None):
xs = _parse_args(args)
print(heapsort(list(xs)))
+
if __name__ == '__main__':
main()
diff --git a/algorithms/impl/insertion_sort.py b/algorithms/impl/insertion_sort.py
index 1abbf84..13f16a0 100644
--- a/algorithms/impl/insertion_sort.py
+++ b/algorithms/impl/insertion_sort.py
@@ -7,6 +7,7 @@ import sys
from ..algorithm import SortingAlgorithm
+
def insertion_sort(xs):
for i in range(1, len(xs)):
j = i
@@ -15,18 +16,22 @@ def insertion_sort(xs):
j -= 1
return xs
+
_ALGORITHMS = [
SortingAlgorithm('insertion_sort', 'Insertion sort', insertion_sort),
]
+
def _parse_args(args=None):
if args is None:
args = sys.argv[1:]
return list(map(int, args))
+
def main(args=None):
xs = _parse_args(args)
print(insertion_sort(list(xs)))
+
if __name__ == '__main__':
main()
diff --git a/algorithms/impl/median.py b/algorithms/impl/median.py
index b48e511..a754cdb 100644
--- a/algorithms/impl/median.py
+++ b/algorithms/impl/median.py
@@ -9,6 +9,7 @@ import sys
from ..algorithm import Algorithm
from .quicksort import quicksort_random
+
def calc_median_heaps(xs):
cur_median = 0.0
min_heap, max_heap = [], []
@@ -33,6 +34,7 @@ def calc_median_heaps(xs):
cur_median = min_heap[0]
return cur_median
+
def calc_median_sorting(xs):
if not xs:
return 0.0
@@ -42,20 +44,24 @@ def calc_median_sorting(xs):
else:
return xs[len(xs) // 2 - 1] / 2 + xs[len(xs) // 2] / 2
+
_ALGORITHMS = [
Algorithm('median_sorting', 'Median value (using explicit sorting)', calc_median_sorting),
Algorithm('median_heaps', 'Median value (using heaps)', calc_median_heaps),
]
+
def _parse_args(args=None):
if args is None:
args = sys.argv[1:]
return list(map(int, args))
+
def main(args=None):
xs = _parse_args(args)
print(calc_median_sorting(list(xs)))
print(calc_median_heaps(list(xs)))
+
if __name__ == '__main__':
main()
diff --git a/algorithms/impl/merge_sort.py b/algorithms/impl/merge_sort.py
index 2b96d21..fecdf78 100644
--- a/algorithms/impl/merge_sort.py
+++ b/algorithms/impl/merge_sort.py
@@ -7,6 +7,7 @@ import sys
from ..algorithm import SortingAlgorithm
+
def merge(left, right):
result = []
l, r = 0, 0
@@ -23,24 +24,29 @@ def merge(left, right):
result.extend(right[r:])
return result
+
def merge_sort(xs):
if len(xs) < 2:
return xs
mid = len(xs) // 2
return merge(merge_sort(xs[:mid]), merge_sort(xs[mid:]))
+
_ALGORITHMS = [
SortingAlgorithm('merge_sort', 'Merge sort', merge_sort),
]
+
def _parse_args(args=None):
if args is None:
args = sys.argv[1:]
return list(map(int, args))
+
def main(args=None):
xs = _parse_args(args)
print(merge_sort(list(xs)))
+
if __name__ == '__main__':
main()
diff --git a/algorithms/impl/quicksort.py b/algorithms/impl/quicksort.py
index 1e835c4..dd0c92b 100644
--- a/algorithms/impl/quicksort.py
+++ b/algorithms/impl/quicksort.py
@@ -8,8 +8,10 @@ import sys
from ..algorithm import SortingAlgorithm
+
seed()
+
def _partition(xs, beg, end, select_pivot):
pivot = select_pivot(xs, beg, end)
xs[pivot], xs[end] = xs[end], xs[pivot]
@@ -20,47 +22,59 @@ def _partition(xs, beg, end, select_pivot):
xs[beg], xs[end] = xs[end], xs[beg]
return beg
+
def _quicksort(xs, beg, end, select_pivot):
if beg < end:
pivot = _partition(xs, beg, end, select_pivot)
_quicksort(xs, beg, pivot - 1, select_pivot)
_quicksort(xs, pivot + 1, end, select_pivot)
+
def _select_first(xs, beg, end):
return beg
+
def _select_second(xs, beg, end):
return beg + 1
+
def _select_middle(xs, beg, end):
return (beg + end) // 2
+
def _select_last(xs, beg, end):
return end
+
def _select_random(xs, beg, end):
return randrange(beg, end + 1)
+
def quicksort_first(xs):
_quicksort(xs, 0, len(xs) - 1, _select_first)
return xs
+
def quicksort_second(xs):
_quicksort(xs, 0, len(xs) - 1, _select_second)
return xs
+
def quicksort_middle(xs):
_quicksort(xs, 0, len(xs) - 1, _select_middle)
return xs
+
def quicksort_last(xs):
_quicksort(xs, 0, len(xs) - 1, _select_last)
return xs
+
def quicksort_random(xs):
_quicksort(xs, 0, len(xs) - 1, _select_random)
return xs
+
_ALGORITHMS = [
SortingAlgorithm('quicksort_first', 'Quicksort (first element as pivot)', quicksort_first),
SortingAlgorithm('quicksort_second', 'Quicksort (second element as pivot)', quicksort_second),
@@ -69,11 +83,13 @@ _ALGORITHMS = [
SortingAlgorithm('quicksort_random', 'Quicksort (random element as pivot)', quicksort_random),
]
+
def _parse_args(args=None):
if args is None:
args = sys.argv[1:]
return list(map(int, args))
+
def main(args=None):
xs = _parse_args(args)
print(quicksort_first(list(xs)))
@@ -82,5 +98,6 @@ def main(args=None):
print(quicksort_last(list(xs)))
print(quicksort_random(list(xs)))
+
if __name__ == '__main__':
main()
diff --git a/algorithms/impl/selection_sort.py b/algorithms/impl/selection_sort.py
index ad4a420..e9a5a09 100644
--- a/algorithms/impl/selection_sort.py
+++ b/algorithms/impl/selection_sort.py
@@ -7,6 +7,7 @@ import sys
from ..algorithm import SortingAlgorithm
+
def selection_sort(xs):
for i in range(len(xs) - 1):
min_i = i
@@ -17,18 +18,22 @@ def selection_sort(xs):
xs[i], xs[min_i] = xs[min_i], xs[i]
return xs
+
_ALGORITHMS = [
SortingAlgorithm('selection_sort', 'Selection sort', selection_sort),
]
+
def _parse_args(args=None):
if args is None:
args = sys.argv[1:]
return list(map(int, args))
+
def main(args=None):
xs = _parse_args(args)
print(selection_sort(list(xs)))
+
if __name__ == '__main__':
main()
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 06:03:29 +0000