aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/algorithms
diff options
context:
space:
mode:
Diffstat (limited to 'algorithms')
-rw-r--r--algorithms/algorithm.py5
-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
-rw-r--r--algorithms/input_kind.py11
-rw-r--r--algorithms/params.py14
-rw-r--r--algorithms/plotter.py1
-rw-r--r--algorithms/registry.py3
-rw-r--r--algorithms/timer.py2
14 files changed, 80 insertions, 14 deletions
diff --git a/algorithms/algorithm.py b/algorithms/algorithm.py
index 74817de..66f8724 100644
--- a/algorithms/algorithm.py
+++ b/algorithms/algorithm.py
@@ -5,6 +5,7 @@
from . import input_kind
+
class Algorithm:
def __init__(self, codename, display_name, f):
self.codename = codename
@@ -16,9 +17,7 @@ class Algorithm:
#raise NotImplementedError('input generation is not defined for a generic algorithm')
return input_kind.gen_input_for_sorting(n, case)
-class SortingAlgorithm(Algorithm):
- def __init__(self, codename, display_name, f):
- super().__init__(codename, display_name, f)
+class SortingAlgorithm(Algorithm):
def gen_input(self, n, case=input_kind.InputKind.AVERAGE):
return input_kind.gen_input_for_sorting(n, case)
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()
diff --git a/algorithms/input_kind.py b/algorithms/input_kind.py
index 998f1d6..08e1c9e 100644
--- a/algorithms/input_kind.py
+++ b/algorithms/input_kind.py
@@ -7,25 +7,28 @@ from array import array
from enum import Enum
from random import seed, sample
+
seed()
+
class InputKind(Enum):
BEST, AVERAGE, WORST = 'best', 'average', 'worst'
def __str__(self):
return self.value
+
def _gen_input_from(xs):
return array('l', xs)
+
def gen_input_for_sorting(n, case=InputKind.AVERAGE):
if n < 0:
raise ValueError('input length cannot be less than zero')
if case is InputKind.BEST:
return _gen_input_from(range(n))
- elif case is InputKind.AVERAGE:
+ if case is InputKind.AVERAGE:
return _gen_input_from(sample(range(n), n))
- elif case is InputKind.WORST:
+ if case is InputKind.WORST:
return _gen_input_from(range(n - 1, -1, -1))
- else:
- raise NotImplementedError('invalid input kind: ' + str(case))
+ raise NotImplementedError('invalid input kind: ' + str(case))
diff --git a/algorithms/params.py b/algorithms/params.py
index edd1361..787cfd1 100644
--- a/algorithms/params.py
+++ b/algorithms/params.py
@@ -11,6 +11,7 @@ from .plotter import PlotBuilder
from . import registry
from .timer import Timer
+
class TimeUnits(Enum):
SECONDS = 'seconds'
MILLISECONDS = 'milliseconds'
@@ -19,16 +20,16 @@ class TimeUnits(Enum):
def get_factor(self):
if self is TimeUnits.SECONDS:
return 1.
- elif self is TimeUnits.MILLISECONDS:
+ if self is TimeUnits.MILLISECONDS:
return 1000.
- elif self is TimeUnits.MICROSECONDS:
+ if self is TimeUnits.MICROSECONDS:
return 1000000.
- else:
- raise NotImplementedError('invalid time units: ' + str(self))
+ raise NotImplementedError('invalid time units: ' + str(self))
def __str__(self):
return self.value
+
class AlgorithmParameters:
def __init__(self, algorithm, min_len, max_len,
input_kind=InputKind.AVERAGE, iterations=1):
@@ -121,10 +122,9 @@ class AlgorithmParameters:
max_y = max(ys)
if max_y > 0.1:
return TimeUnits.SECONDS
- elif max_y > 0.0001:
+ if max_y > 0.0001:
return TimeUnits.MILLISECONDS
- else:
- return TimeUnits.MICROSECONDS
+ return TimeUnits.MICROSECONDS
def plot_running_time(self, output_path=None):
xs, ys = self.measure_running_time()
diff --git a/algorithms/plotter.py b/algorithms/plotter.py
index 8086850..47d2929 100644
--- a/algorithms/plotter.py
+++ b/algorithms/plotter.py
@@ -5,6 +5,7 @@
import matplotlib.pyplot as plt
+
class PlotBuilder:
@staticmethod
def set_xlabel(s):
diff --git a/algorithms/registry.py b/algorithms/registry.py
index 787fe49..3bc6495 100644
--- a/algorithms/registry.py
+++ b/algorithms/registry.py
@@ -5,10 +5,13 @@
from . import impl
+
_ALL_ALGORITHMS = impl.refresh_algorithms()
+
def get_codenames():
return _ALL_ALGORITHMS.keys()
+
def get(codename):
return _ALL_ALGORITHMS[codename]
diff --git a/algorithms/timer.py b/algorithms/timer.py
index bd5d044..c567a3f 100644
--- a/algorithms/timer.py
+++ b/algorithms/timer.py
@@ -6,9 +6,11 @@
import gc
import time
+
def get_timestamp():
return time.perf_counter()
+
class Timer:
def __init__(self, dest, iterations=1):
self._dest = dest
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-09 17:32:39 +0000