From 2183f3f860af34e45058ef078045322062b51f42 Mon Sep 17 00:00:00 2001 From: Egor Tensin Date: Sun, 17 Apr 2016 00:49:33 +0300 Subject: rearrange source files * Add a useful `algorithms` package to provide convinient access to the implemented algorithms. * This allows to e.g. dynamically list available algorithms, which greatly simplifies a lot of things. --- algorithms/__init__.py | 0 algorithms/algorithm.py | 25 +++++++++++++ algorithms/impl/__init__.py | 29 +++++++++++++++ algorithms/impl/bubble_sort.py | 39 +++++++++++++++++++++ algorithms/impl/heapsort.py | 59 +++++++++++++++++++++++++++++++ algorithms/impl/insertion_sort.py | 20 +++++++++++ algorithms/impl/merge_sort.py | 34 ++++++++++++++++++ algorithms/impl/quicksort.py | 74 +++++++++++++++++++++++++++++++++++++++ algorithms/impl/selection_sort.py | 22 ++++++++++++ algorithms/registry.py | 17 +++++++++ 10 files changed, 319 insertions(+) create mode 100644 algorithms/__init__.py create mode 100644 algorithms/algorithm.py create mode 100644 algorithms/impl/__init__.py create mode 100644 algorithms/impl/bubble_sort.py create mode 100644 algorithms/impl/heapsort.py create mode 100644 algorithms/impl/insertion_sort.py create mode 100644 algorithms/impl/merge_sort.py create mode 100644 algorithms/impl/quicksort.py create mode 100644 algorithms/impl/selection_sort.py create mode 100644 algorithms/registry.py (limited to 'algorithms') diff --git a/algorithms/__init__.py b/algorithms/__init__.py new file mode 100644 index 0000000..e69de29 diff --git a/algorithms/algorithm.py b/algorithms/algorithm.py new file mode 100644 index 0000000..322a51f --- /dev/null +++ b/algorithms/algorithm.py @@ -0,0 +1,25 @@ +# Copyright 2016 Egor Tensin +# This file is licensed under the terms of the MIT License. +# See LICENSE.txt for details. + +class Algorithm: + def __init__(self, codename, display_name, f): + self._codename = codename + self._display_name = display_name + self._f = f + + def get_codename(self): + return self._codename + + def get_display_name(self): + return self._display_name + + def get_function(self): + return self._f + + def __str__(self): + return self.get_display_name() + +class SortingAlgorithm(Algorithm): + def __init__(self, codename, display_name, f): + super().__init__(codename, display_name, f) diff --git a/algorithms/impl/__init__.py b/algorithms/impl/__init__.py new file mode 100644 index 0000000..29cd51c --- /dev/null +++ b/algorithms/impl/__init__.py @@ -0,0 +1,29 @@ +# Copyright 2016 Egor Tensin +# This file is licensed under the terms of the MIT License. +# See LICENSE.txt for details. + +_ALL_ALGORITHMS = {} + +def _refresh_algorithms(): + _ALGORITHMS_NAME = '_ALGORITHMS' + global _ALL_ALGORITHMS + _ALL_ALGORITHMS = {} + + from algorithms.algorithm import Algorithm + + from importlib import import_module + import os.path + from pkgutil import iter_modules + + for _, module_name, is_pkg in iter_modules([os.path.dirname(__file__)]): + if is_pkg: + continue + module = import_module('.' + module_name, __package__) + if hasattr(module, _ALGORITHMS_NAME): + module_algorithms = getattr(module, _ALGORITHMS_NAME) + for algorithm in module_algorithms: + assert isinstance(algorithm, Algorithm) + assert algorithm.get_codename() not in _ALL_ALGORITHMS + _ALL_ALGORITHMS[algorithm.get_codename()] = algorithm + +_refresh_algorithms() diff --git a/algorithms/impl/bubble_sort.py b/algorithms/impl/bubble_sort.py new file mode 100644 index 0000000..2abfc43 --- /dev/null +++ b/algorithms/impl/bubble_sort.py @@ -0,0 +1,39 @@ +# Copyright 2015 Egor Tensin +# This file is licensed under the terms of the MIT License. +# See LICENSE.txt for details. + +def bubble_sort(xs): + while True: + swapped = False + for i in range(1, len(xs)): + if xs[i - 1] > xs[i]: + xs[i], xs[i - 1] = xs[i - 1], xs[i] + swapped = True + if not swapped: + break + return xs + +def bubble_sort_optimized(xs): + n = len(xs) + while True: + new_n = 0 + for i in range(1, n): + if xs[i - 1] > xs[i]: + xs[i], xs[i - 1] = xs[i - 1], xs[i] + new_n = i + n = new_n + if not n: + break + return xs + +if __name__ == '__main__': + import sys + xs = list(map(int, sys.argv[1:])) + print(bubble_sort(list(xs))) + print(bubble_sort_optimized(list(xs))) +else: + from algorithms.algorithm import SortingAlgorithm + _ALGORITHMS = [ + SortingAlgorithm('bubble_sort', 'Bubble sort', bubble_sort), + SortingAlgorithm('bubble_sort_optimized', 'Bubble sort (optimized)', bubble_sort_optimized), + ] diff --git a/algorithms/impl/heapsort.py b/algorithms/impl/heapsort.py new file mode 100644 index 0000000..db3b6bd --- /dev/null +++ b/algorithms/impl/heapsort.py @@ -0,0 +1,59 @@ +# Copyright 2015 Egor Tensin +# This file is licensed under the terms of the MIT License. +# See LICENSE.txt for details. + +# Disclaimer: implemented in the most literate way. + +def heapsort(xs): + _heapify(xs) + first, last = 0, len(xs) - 1 + for end in range(last, first, -1): + xs[end], xs[first] = xs[first], xs[end] + _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: + # We swap if there is at least one child + child = _get_left_child(root) + if child > end: + break + # If there are two children, select the minimum + right_child = _get_right_child(root) + if right_child <= end and xs[child] < xs[right_child]: + child = right_child + if xs[root] < xs[child]: + xs[root], xs[child] = xs[child], xs[root] + root = child + else: + break + +if __name__ == '__main__': + import sys + print(heapsort(list(map(int, sys.argv[1:])))) +else: + from algorithms.algorithm import SortingAlgorithm + _ALGORITHMS = [ + SortingAlgorithm('heapsort', 'Heapsort', heapsort), + ] diff --git a/algorithms/impl/insertion_sort.py b/algorithms/impl/insertion_sort.py new file mode 100644 index 0000000..f671712 --- /dev/null +++ b/algorithms/impl/insertion_sort.py @@ -0,0 +1,20 @@ +# Copyright 2015 Egor Tensin +# This file is licensed under the terms of the MIT License. +# See LICENSE.txt for details. + +def insertion_sort(xs): + for i in range(1, len(xs)): + j = i + while j > 0 and xs[j - 1] > xs[j]: + xs[j], xs[j - 1] = xs[j - 1], xs[j] + j -= 1 + return xs + +if __name__ == '__main__': + import sys + print(insertion_sort(list(map(int, sys.argv[1:])))) +else: + from algorithms.algorithm import SortingAlgorithm + _ALGORITHMS = [ + SortingAlgorithm('insertion_sort', 'Insertion sort', insertion_sort), + ] diff --git a/algorithms/impl/merge_sort.py b/algorithms/impl/merge_sort.py new file mode 100644 index 0000000..9fa96ec --- /dev/null +++ b/algorithms/impl/merge_sort.py @@ -0,0 +1,34 @@ +# Copyright 2015 Egor Tensin +# This file is licensed under the terms of the MIT License. +# See LICENSE.txt for details. + +def merge(left, right): + result = [] + l, r = 0, 0 + while l < len(left) and r < len(right): + if left[l] <= right[r]: + result.append(left[l]) + l += 1 + else: + result.append(right[r]) + r += 1 + if left: + result.extend(left[l:]) + if 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:])) + +if __name__ == '__main__': + import sys + print(merge_sort(list(map(int, sys.argv[1:])))) +else: + from algorithms.algorithm import SortingAlgorithm + _ALGORITHMS = [ + SortingAlgorithm('merge_sort', 'Merge sort', merge_sort), + ] diff --git a/algorithms/impl/quicksort.py b/algorithms/impl/quicksort.py new file mode 100644 index 0000000..32100b0 --- /dev/null +++ b/algorithms/impl/quicksort.py @@ -0,0 +1,74 @@ +# Copyright 2015 Egor Tensin +# This file is licensed under the terms of the MIT License. +# See LICENSE.txt for details. + +from random import randrange + +def _partition(xs, beg, end, select_pivot): + pivot = select_pivot(xs, beg, end) + xs[pivot], xs[end] = xs[end], xs[pivot] + for i in range(beg, end): + if xs[i] <= xs[end]: + xs[i], xs[beg] = xs[beg], xs[i] + beg += 1 + 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 + +if __name__ == '__main__': + import sys + xs = list(map(int, sys.argv[1:])) + print(quicksort_first(list(xs))) + print(quicksort_second(list(xs))) + print(quicksort_middle(list(xs))) + print(quicksort_last(list(xs))) + print(quicksort_random(list(xs))) +else: + from algorithms.algorithm import SortingAlgorithm + _ALGORITHMS = [ + SortingAlgorithm('quicksort_first', 'Quicksort (first element as pivot)', quicksort_first), + SortingAlgorithm('quicksort_second', 'Quicksort (second element as pivot)', quicksort_second), + SortingAlgorithm('quicksort_middle', 'Quicksort (middle element as pivot)', quicksort_middle), + SortingAlgorithm('quicksort_last', 'Quicksort (last element as pivot)', quicksort_last), + SortingAlgorithm('quicksort_random', 'Quicksort (random element as pivot)', quicksort_random), + ] diff --git a/algorithms/impl/selection_sort.py b/algorithms/impl/selection_sort.py new file mode 100644 index 0000000..d48c058 --- /dev/null +++ b/algorithms/impl/selection_sort.py @@ -0,0 +1,22 @@ +# Copyright 2015 Egor Tensin +# This file is licensed under the terms of the MIT License. +# See LICENSE.txt for details. + +def selection_sort(xs): + for i in range(len(xs) - 1): + min_i = i + for j in range(i + 1, len(xs)): + if xs[j] < xs[min_i]: + min_i = j + if min_i != i: + xs[i], xs[min_i] = xs[min_i], xs[i] + return xs + +if __name__ == '__main__': + import sys + print(selection_sort(list(map(int, sys.argv[1:])))) +else: + from algorithms.algorithm import SortingAlgorithm + _ALGORITHMS = [ + SortingAlgorithm('selection', 'Selection sort', selection_sort), + ] diff --git a/algorithms/registry.py b/algorithms/registry.py new file mode 100644 index 0000000..8f0469d --- /dev/null +++ b/algorithms/registry.py @@ -0,0 +1,17 @@ +# Copyright 2016 Egor Tensin +# This file is licensed under the terms of the MIT License. +# See LICENSE.txt for details. + +import algorithms.impl + +def refresh_algorithms(): + algorithms.impl._refresh_algorithms() + +def get_codenames(): + return algorithms.impl._ALL_ALGORITHMS.keys() + +def iter_algorithms(): + return iter(algorithms.impl._ALL_ALGORITHMS.values()) + +def get(codename): + return algorithms.impl._ALL_ALGORITHMS[codename] -- cgit v1.2.3