diff options
| -rwxr-xr-x | .ci/plot.sh | 46 | ||||
| -rw-r--r-- | .gitattributes | 4 | ||||
| -rw-r--r-- | .github/workflows/ci.yml | 28 | ||||
| -rw-r--r-- | .gitignore | 3 | ||||
| -rw-r--r-- | .pylintrc | 3 | ||||
| -rw-r--r-- | LICENSE.txt | 21 | ||||
| -rw-r--r-- | README.md | 107 | ||||
| -rw-r--r-- | algorithms/__init__.py | 0 | ||||
| -rw-r--r-- | algorithms/algorithm.py | 23 | ||||
| -rw-r--r-- | algorithms/impl/__init__.py | 30 | ||||
| -rw-r--r-- | algorithms/impl/bubble_sort.py | 56 | ||||
| -rw-r--r-- | algorithms/impl/heapsort.py | 82 | ||||
| -rw-r--r-- | algorithms/impl/insertion_sort.py | 37 | ||||
| -rw-r--r-- | algorithms/impl/median.py | 67 | ||||
| -rw-r--r-- | algorithms/impl/merge_sort.py | 52 | ||||
| -rw-r--r-- | algorithms/impl/quicksort.py | 103 | ||||
| -rw-r--r-- | algorithms/impl/selection_sort.py | 39 | ||||
| -rw-r--r-- | algorithms/input_kind.py | 34 | ||||
| -rw-r--r-- | algorithms/params.py | 142 | ||||
| -rw-r--r-- | algorithms/plotter.py | 25 | ||||
| -rw-r--r-- | algorithms/registry.py | 17 | ||||
| -rw-r--r-- | algorithms/timer.py | 27 | ||||
| -rw-r--r-- | index.html | 13 | ||||
| -rw-r--r-- | plot.bat | 46 | ||||
| -rwxr-xr-x | plot.py | 119 | ||||
| -rwxr-xr-x | plot.sh | 49 | ||||
| -rw-r--r-- | requirements.txt | 1 | ||||
| -rwxr-xr-x | test.py | 93 |
28 files changed, 1254 insertions, 13 deletions
diff --git a/.ci/plot.sh b/.ci/plot.sh new file mode 100755 index 0000000..fee1166 --- /dev/null +++ b/.ci/plot.sh @@ -0,0 +1,46 @@ +#!/usr/bin/env bash + +# Copyright (c) 2019 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +set -o errexit -o nounset -o pipefail +shopt -s inherit_errexit lastpipe + +script_dir="$( dirname -- "${BASH_SOURCE[0]}" )" +script_dir="$( cd -- "$script_dir" && pwd )" +readonly script_dir + +declare -a algorithm_list=( + bubble_sort + bubble_sort_optimized + heapsort + insertion_sort + merge_sort + quicksort_first + quicksort_last + quicksort_middle + quicksort_random + quicksort_second + selection_sort +) + +fix_matplotlib() { + # Get rid of: + # tkinter.TclError: no display name and no $DISPLAY environment variable + mkdir -p -- ~/.config/matplotlib + echo 'backend: Agg' > ~/.config/matplotlib/matplotlibrc +} + +main() { + fix_matplotlib + + local algorithm + for algorithm in ${algorithm_list[@]+"${algorithm_list[@]}"}; do + echo "Plotting algorithm $algorithm..." + "$script_dir/../plot.sh" "$algorithm" + done +} + +main "$@" diff --git a/.gitattributes b/.gitattributes index 176a458..8cdb1e0 100644 --- a/.gitattributes +++ b/.gitattributes @@ -1 +1,5 @@ * text=auto + +*.sh text eol=lf + +*.bat text eol=crlf diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml new file mode 100644 index 0000000..b071fbe --- /dev/null +++ b/.github/workflows/ci.yml @@ -0,0 +1,28 @@ +name: CI + +on: + push: + pull_request: + workflow_dispatch: + +jobs: + test: + strategy: + matrix: + python-version: ['3.7', '3.8', '3.9', '3.10', '3.11', 3.x] + runs-on: ubuntu-latest + name: 'Python ${{ matrix.python-version }}' + env: + PIP_DISABLE_PIP_VERSION_CHECK: 1 + PIP_NO_PYTHON_VERSION_WARNING: 1 + steps: + - name: Checkout + uses: actions/checkout@v4 + - name: Set up Python + uses: actions/setup-python@v5 + with: + python-version: '${{ matrix.python-version }}' + - name: Install dependencies + run: pip install -r requirements.txt + - name: Run tests + run: ./.ci/plot.sh diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..d8fb1a6 --- /dev/null +++ b/.gitignore @@ -0,0 +1,3 @@ +__pycache__/ +*.png +/img/ diff --git a/.pylintrc b/.pylintrc new file mode 100644 index 0000000..bccfc70 --- /dev/null +++ b/.pylintrc @@ -0,0 +1,3 @@ +[MESSAGES CONTROL] + +disable=invalid-name,missing-docstring diff --git a/LICENSE.txt b/LICENSE.txt new file mode 100644 index 0000000..62c44fd --- /dev/null +++ b/LICENSE.txt @@ -0,0 +1,21 @@ +MIT License + +Copyright (c) 2015 Egor Tensin <Egor.Tensin@gmail.com> + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/README.md b/README.md new file mode 100644 index 0000000..74b5c19 --- /dev/null +++ b/README.md @@ -0,0 +1,107 @@ +Sorting algorithms +================== + +[](https://github.com/egor-tensin/sorting-algorithms/actions/workflows/ci.yml) + +Getting the hang out of (sorting) algorithms. +See also https://tensin.name/sorting-algorithms/. + +Prerequisites +------------- + +* Python 3.4 or higher +* [matplotlib] +* [numpy] (required by [matplotlib]) + +[matplotlib]: http://matplotlib.org/ +[numpy]: http://www.numpy.org/ + +Algorithms +---------- + +Each of the implemented sorting algorithms resides in a separate Python module +(in the `algorithms.impl` package). +The implemented algorithms are listed below. + +| Module name | Description +| ---------------- | -------------- +| `bubble_sort` | Bubble sort +| `heapsort` | Heapsort +| `insertion_sort` | Insertion sort +| `median` | Median value +| `merge_sort` | Merge sort +| `quicksort` | Quicksort +| `selection_sort` | Selection sort + +Some algorithms actually come in different variants. +For example, the implementation of quicksort includes a number of versions +depending on how the pivot element is chosen, be it the first, the second, the +middle, the last or a random element of the sequence. + +Testing +------- + +You can test each of the algorithms above by passing a sequence of integer +numbers to the corresponding script. + +``` +> python -m algorithms.impl.heapsort 5 3 4 1 2 +[1, 2, 3, 4, 5] +``` + +``` +> python -m algorithms.impl.quicksort 5 3 4 1 2 +[1, 2, 3, 4, 5] +[1, 2, 3, 4, 5] +[1, 2, 3, 4, 5] +[1, 2, 3, 4, 5] +[1, 2, 3, 4, 5] +``` + +You can use "test.py" to quickly generate an input list of some kind and +display the result of executing one of the implemented algorithms. +Consult the output of `test.py --help` to learn how to use the script. + +``` +> ./test.py --input best --length 1000 median_heaps +499.5 +``` + +``` +> ./test.py --input worst --length 10 quicksort_random +[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] +``` + +Plotting +-------- + +You can generate similar plots you might've seen at +https://tensin.name/sorting-algorithms/ using "plot.py". +Consult the output of `plot.py --help` to learn how to use the script. + +``` +> ./plot.py merge_sort --min 0 --max 200 --input best --iterations 1000 +``` + +``` +> ./plot.py median_sorting --min 0 --max 200 --input average --iterations 100 --output median_sorting.png +``` + +If you're having problems using the script (like having excessive noise in the +measurement results), try minimizing background activity of your OS and +applications. +For example, on Windows 8.1 I got very reasonable plots after booting into Safe +Mode and running the script with a higher priority while also setting its CPU +affinity: + +``` +> start /affinity 1 /realtime plot.py ... +``` + +License +------- + +Distributed under the MIT License. +See [LICENSE.txt] for details. + +[LICENSE.txt]: LICENSE.txt diff --git a/algorithms/__init__.py b/algorithms/__init__.py new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/algorithms/__init__.py diff --git a/algorithms/algorithm.py b/algorithms/algorithm.py new file mode 100644 index 0000000..66f8724 --- /dev/null +++ b/algorithms/algorithm.py @@ -0,0 +1,23 @@ +# Copyright (c) 2016 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +from . import input_kind + + +class Algorithm: + def __init__(self, codename, display_name, f): + self.codename = codename + self.display_name = display_name + self.function = f + + @staticmethod + def gen_input(n, case=input_kind.InputKind.AVERAGE): + #raise NotImplementedError('input generation is not defined for a generic algorithm') + return input_kind.gen_input_for_sorting(n, case) + + +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 new file mode 100644 index 0000000..84bd702 --- /dev/null +++ b/algorithms/impl/__init__.py @@ -0,0 +1,30 @@ +# Copyright (c) 2016 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +from importlib import import_module +import os.path +from pkgutil import iter_modules + +from .. import algorithm + + +_ALGORITHMS_NAME = '_ALGORITHMS' + + +def refresh_algorithms(): + all_algorithms = {} + + 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 descr in module_algorithms: + assert isinstance(descr, algorithm.Algorithm) + assert descr.codename not in all_algorithms + all_algorithms[descr.codename] = descr + + return all_algorithms diff --git a/algorithms/impl/bubble_sort.py b/algorithms/impl/bubble_sort.py new file mode 100644 index 0000000..0ea66bb --- /dev/null +++ b/algorithms/impl/bubble_sort.py @@ -0,0 +1,56 @@ +# Copyright (c) 2015 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +import sys + +from ..algorithm import SortingAlgorithm + + +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 + + +_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 new file mode 100644 index 0000000..81bea20 --- /dev/null +++ b/algorithms/impl/heapsort.py @@ -0,0 +1,82 @@ +# Copyright (c) 2015 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +import sys + +from ..algorithm import SortingAlgorithm + +# 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 + + +_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 new file mode 100644 index 0000000..13f16a0 --- /dev/null +++ b/algorithms/impl/insertion_sort.py @@ -0,0 +1,37 @@ +# Copyright (c) 2015 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +import sys + +from ..algorithm import SortingAlgorithm + + +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 + + +_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 new file mode 100644 index 0000000..a754cdb --- /dev/null +++ b/algorithms/impl/median.py @@ -0,0 +1,67 @@ +# Copyright (c) 2016 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +from heapq import heappush, heappop +import sys + +from ..algorithm import Algorithm +from .quicksort import quicksort_random + + +def calc_median_heaps(xs): + cur_median = 0.0 + min_heap, max_heap = [], [] + for x in xs: + if x < cur_median: + heappush(max_heap, -x) + elif x > cur_median or len(max_heap) > len(min_heap): + heappush(min_heap, x) + else: + heappush(max_heap, -x) + + if len(max_heap) > len(min_heap) + 1: + heappush(min_heap, -heappop(max_heap)) + elif len(min_heap) > len(max_heap) + 1: + heappush(max_heap, -heappop(min_heap)) + + if len(max_heap) > len(min_heap): + cur_median = -max_heap[0] + elif len(max_heap) == len(min_heap): + cur_median = -max_heap[0] / 2 + min_heap[0] / 2 + else: + cur_median = min_heap[0] + return cur_median + + +def calc_median_sorting(xs): + if not xs: + return 0.0 + quicksort_random(xs) + if len(xs) % 2: + return xs[len(xs) // 2] + 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 new file mode 100644 index 0000000..fecdf78 --- /dev/null +++ b/algorithms/impl/merge_sort.py @@ -0,0 +1,52 @@ +# Copyright (c) 2015 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +import sys + +from ..algorithm import SortingAlgorithm + + +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:])) + + +_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 new file mode 100644 index 0000000..dd0c92b --- /dev/null +++ b/algorithms/impl/quicksort.py @@ -0,0 +1,103 @@ +# Copyright (c) 2015 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +from random import randrange, seed +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] + 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 + + +_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), +] + + +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))) + print(quicksort_second(list(xs))) + print(quicksort_middle(list(xs))) + 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 new file mode 100644 index 0000000..e9a5a09 --- /dev/null +++ b/algorithms/impl/selection_sort.py @@ -0,0 +1,39 @@ +# Copyright (c) 2015 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +import sys + +from ..algorithm import SortingAlgorithm + + +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 + + +_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 new file mode 100644 index 0000000..08e1c9e --- /dev/null +++ b/algorithms/input_kind.py @@ -0,0 +1,34 @@ +# Copyright (c) 2016 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +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)) + if case is InputKind.AVERAGE: + return _gen_input_from(sample(range(n), n)) + if case is InputKind.WORST: + return _gen_input_from(range(n - 1, -1, -1)) + raise NotImplementedError('invalid input kind: ' + str(case)) diff --git a/algorithms/params.py b/algorithms/params.py new file mode 100644 index 0000000..486cb0e --- /dev/null +++ b/algorithms/params.py @@ -0,0 +1,142 @@ +# Copyright (c) 2016 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +from enum import Enum +from numbers import Integral + +from .input_kind import InputKind +from .plotter import PlotBuilder +from . import registry +from .timer import Timer + + +class TimeUnits(Enum): + SECONDS = 'seconds' + MILLISECONDS = 'milliseconds' + MICROSECONDS = 'microseconds' + + def get_factor(self): + if self is TimeUnits.SECONDS: + return 1. + if self is TimeUnits.MILLISECONDS: + return 1000. + if self is TimeUnits.MICROSECONDS: + return 1000000. + 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): + + if isinstance(algorithm, str): + algorithm = registry.get(algorithm) + self.algorithm = algorithm + + self.input_kind = input_kind + + self._min_len = None + self._max_len = None + self.min_len = min_len + self.max_len = max_len + + self._iterations = None + self.iterations = iterations + + @property + def min_len(self): + return self._min_len + + @min_len.setter + def min_len(self, val): + if not isinstance(val, Integral): + raise TypeError('must be an integral value') + val = int(val) + if val < 0: + raise ValueError('must be non-negative') + if self.max_len is not None and self.max_len < val: + raise ValueError('must not be greater than the maximum length') + self._min_len = val + + @property + def max_len(self): + return self._max_len + + @max_len.setter + def max_len(self, val): + if not isinstance(val, Integral): + raise TypeError('must be an integral value') + val = int(val) + if val < 0: + raise ValueError('must be non-negative') + if self.min_len is not None and self.min_len > val: + raise ValueError('must not be lesser than the minimum length') + self._max_len = val + + @property + def iterations(self): + return self._iterations + + @iterations.setter + def iterations(self, val): + if not isinstance(val, Integral): + raise TypeError('must be an integral value') + val = int(val) + if val < 1: + raise ValueError('must be positive') + self._iterations = val + + def measure_running_time(self): + input_len_range = list(range(self.min_len, self.max_len + 1)) + running_time = [] + for input_len in input_len_range: + input_sample = self.algorithm.gen_input(input_len, self.input_kind) + input_copies = [list(input_sample) for _ in range(self.iterations)] + with Timer(running_time, self.iterations): + for i in range(self.iterations): + self.algorithm.function(input_copies[i]) + return input_len_range, running_time + + @staticmethod + def _format_plot_xlabel(): + return 'Input length' + + @staticmethod + def _format_plot_ylabel(units): + return 'Running time ({})'.format(units) + + def _format_plot_title(self): + return '{}, {} case'.format( + self.algorithm.display_name, self.input_kind) + + def _format_plot_suptitle(self): + return self.algorithm.display_name + + @staticmethod + def _derive_time_units(ys): + max_y = max(ys) + if max_y > 0.1: + return TimeUnits.SECONDS + if max_y > 0.0001: + return TimeUnits.MILLISECONDS + return TimeUnits.MICROSECONDS + + def plot_running_time(self, output_path=None): + xs, ys = self.measure_running_time() + units = self._derive_time_units(ys) + ys = [y * units.get_factor() for y in ys] + + plot_builder = PlotBuilder() + title = self._format_plot_title() + xlabel = self._format_plot_xlabel() + ylabel = self._format_plot_ylabel(units) + plot_builder.plot(title, xlabel, ylabel, xs, ys) + if output_path is None: + plot_builder.show() + else: + plot_builder.save(output_path) diff --git a/algorithms/plotter.py b/algorithms/plotter.py new file mode 100644 index 0000000..d3e4ee4 --- /dev/null +++ b/algorithms/plotter.py @@ -0,0 +1,25 @@ +# Copyright (c) 2016 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +import matplotlib.pyplot as plt + + +class PlotBuilder: + def __init__(self): + self._fig, self._ax = plt.subplots(figsize=(8, 6), dpi=200) + self._ax.grid(alpha=0.8, linestyle=':') + + def plot(self, title, xlabel, ylabel, xs, ys): + self._ax.set_title(title) + self._ax.set_xlabel(xlabel) + self._ax.set_ylabel(ylabel) + self._ax.plot(xs, ys) + + @staticmethod + def show(): + plt.show() + + def save(self, output_path): + self._fig.savefig(output_path) diff --git a/algorithms/registry.py b/algorithms/registry.py new file mode 100644 index 0000000..3bc6495 --- /dev/null +++ b/algorithms/registry.py @@ -0,0 +1,17 @@ +# Copyright (c) 2016 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +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 new file mode 100644 index 0000000..c567a3f --- /dev/null +++ b/algorithms/timer.py @@ -0,0 +1,27 @@ +# Copyright (c) 2016 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +import gc +import time + + +def get_timestamp(): + return time.perf_counter() + + +class Timer: + def __init__(self, dest, iterations=1): + self._dest = dest + self._iterations = iterations + + def __enter__(self): + gc.disable() + self._start = get_timestamp() + return self + + def __exit__(self, *args): + end = get_timestamp() + gc.enable() + self._dest.append((end - self._start) / self._iterations) diff --git a/index.html b/index.html deleted file mode 100644 index b6eb1ae..0000000 --- a/index.html +++ /dev/null @@ -1,13 +0,0 @@ -<!DOCTYPE html> -<html lang="en"> - <head> - <meta charset="UTF-8"> - <meta name="viewport" content="width=device-width, initial-scale=1.0"> - <title>Moved to egort.name</title> - <meta http-equiv="refresh" content="1; URL=https://egort.name/sorting-algorithms/"> - <link rel="canonical" href="https://egort.name/sorting-algorithms/"> - </head> - <body> - <p>Moved to <a href="https://egort.name/sorting-algorithms/">egort.name/sorting-algorithms/</a>. Redirecting...</p> - </body> -</html> diff --git a/plot.bat b/plot.bat new file mode 100644 index 0000000..3a2f22d --- /dev/null +++ b/plot.bat @@ -0,0 +1,46 @@ +@rem Copyright (c) 2015 Egor Tensin <Egor.Tensin@gmail.com> +@rem This file is part of the "Sorting algorithms" project. +@rem For details, see https://github.com/egor-tensin/sorting-algorithms. +@rem Distributed under the MIT License. + +@setlocal enabledelayedexpansion +@echo off + +set default_iterations=100 +set default_min=0 +set default_max=200 + +if "%~1" == "" goto :exit_with_usage +set "algorithm=%~1" + +if "%~2" == "" ( + set "iterations=%default_iterations%" +) else ( + set "iterations=%~2" +) +if "%~3" == "" ( + set "min=%default_min%" +) else ( + set "min=%~3" +) +if "%~4" == "" ( + set "max=%default_max%" +) else ( + set "max=%~4" +) + +mkdir /p img + +for %%i in (best average worst) do ( + plot.py "%algorithm%" ^ + --input "%%i" ^ + --min "%min%" --max "%max%" ^ + --iterations "%iterations%" ^ + --output "img\%algorithm%_%iterations%_%%i_%min%_%max%.png" || exit /b !errorlevel! +) + +exit /b 0 + +:exit_with_usage: +echo Usage: %~nx0 ALGORITHM [ITERATIONS [MIN_VALUE [MAX_VALUE]]] +exit /b 1 @@ -0,0 +1,119 @@ +#!/usr/bin/env python3 + +# Copyright (c) 2015 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +import argparse +import sys + +from algorithms.input_kind import InputKind +from algorithms.params import AlgorithmParameters +import algorithms.registry as registry + + +_DEFAULT_ITERATIONS = 100 +_DEFAULT_INPUT_KIND = InputKind.AVERAGE +_DEFAULT_MIN_LENGTH = 0 +_DEFAULT_MAX_LENGTH = 200 + + +def plot_algorithm(algorithm, input_kind=_DEFAULT_INPUT_KIND, + min_len=_DEFAULT_MIN_LENGTH, + max_len=_DEFAULT_MAX_LENGTH, + iterations=_DEFAULT_ITERATIONS, + output_path=None): + + if isinstance(algorithm, str): + algorithm = registry.get(algorithm) + + params = AlgorithmParameters(algorithm, min_len, max_len, + input_kind=input_kind, + iterations=iterations) + params.plot_running_time(output_path) + + +def _parse_non_negative_integer(s): + try: + n = int(s) + except ValueError: + raise argparse.ArgumentTypeError('must be a non-negative integer: ' + str(s)) + if n < 0: + raise argparse.ArgumentTypeError('must be a non-negative integer') + return n + + +def _parse_positive_integer(s): + try: + n = int(s) + except ValueError: + raise argparse.ArgumentTypeError('must be a positive integer: ' + str(s)) + if n < 1: + raise argparse.ArgumentTypeError('must be a positive integer') + return n + + +def _parse_input_kind(s): + try: + return InputKind(s) + except ValueError: + raise argparse.ArgumentTypeError('invalid input kind: ' + str(s)) + + +def _format_algorithm(codename): + return '* {}: {}'.format(codename, registry.get(codename).display_name) + + +def _format_available_algorithms(): + descr = 'available algorithms (in the CODENAME: DISPLAY_NAME format):\n' + return descr + '\n'.join(map( + _format_algorithm, sorted(registry.get_codenames()))) + + +def _format_description(): + return _format_available_algorithms() + + +def _create_argument_parser(): + return argparse.ArgumentParser( + description=_format_description(), + formatter_class=argparse.RawDescriptionHelpFormatter) + + +def _parse_args(args=None): + if args is None: + args = sys.argv[1:] + parser = _create_argument_parser() + + parser.add_argument('algorithm', metavar='CODENAME', + choices=registry.get_codenames(), + help='algorithm codename') + parser.add_argument('--iterations', '-r', metavar='N', + type=_parse_positive_integer, + default=_DEFAULT_ITERATIONS, + help='set number of algorithm iterations') + parser.add_argument('--input', '-i', dest='input_kind', + choices=InputKind, + type=_parse_input_kind, default=_DEFAULT_INPUT_KIND, + help='specify input kind') + parser.add_argument('--min', '-a', metavar='N', dest='min_len', + type=_parse_non_negative_integer, + default=_DEFAULT_MIN_LENGTH, + help='set min input length') + parser.add_argument('--max', '-b', metavar='N', dest='max_len', + type=_parse_non_negative_integer, + default=_DEFAULT_MAX_LENGTH, + help='set max input length') + parser.add_argument('--output', '-o', metavar='PATH', dest='output_path', + help='set plot file path') + + return parser.parse_args(args) + + +def main(args=None): + plot_algorithm(**vars(_parse_args(args))) + + +if __name__ == '__main__': + main() @@ -0,0 +1,49 @@ +#!/usr/bin/env bash + +# Copyright (c) 2019 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +set -o errexit -o nounset -o pipefail +shopt -s inherit_errexit lastpipe + +script_dir="$( dirname -- "${BASH_SOURCE[0]}" )" +script_dir="$( cd -- "$script_dir" && pwd )" +readonly script_dir +script_name="$( basename -- "${BASH_SOURCE[0]}" )" +readonly script_name + +readonly default_iterations=100 +readonly default_min=0 +readonly default_max=200 + +main() { + if [ "$#" -lt 1 ] || [ "$#" -gt 4 ]; then + echo "usage: $script_name ALGORITHM [ITERATIONS [MIN_VALUE [MAX_VALUE]]]" >&2 + exit 1 + fi + + local algorithm="$1" + local iterations="$default_iterations" + [ "$#" -ge 2 ] && iterations="$2" + local min="$default_min" + [ "$#" -ge 3 ] && min="$3" + local max="$default_max" + [ "$#" -ge 4 ] && max="$4" + + mkdir -p -- "$script_dir/img" + + local input_kind + for input_kind in best average worst; do + local output_name="${algorithm}_${iterations}_${input_kind}_${min}_${max}.png" + python "$script_dir/plot.py" \ + "$algorithm" \ + --input "$input_kind" \ + --min "$min" --max "$max" \ + --iterations "$iterations" \ + --output "$script_dir/img/$output_name" + done +} + +main "$@" diff --git a/requirements.txt b/requirements.txt new file mode 100644 index 0000000..6ccafc3 --- /dev/null +++ b/requirements.txt @@ -0,0 +1 @@ +matplotlib @@ -0,0 +1,93 @@ +#!/usr/bin/env python3 + +# Copyright (c) 2016 Egor Tensin <Egor.Tensin@gmail.com> +# This file is part of the "Sorting algorithms" project. +# For details, see https://github.com/egor-tensin/sorting-algorithms. +# Distributed under the MIT License. + +from array import array +import argparse +import sys + +from algorithms.input_kind import InputKind +import algorithms.registry as registry + + +_DEFAULT_INPUT_KIND = InputKind.AVERAGE +_DEFAULT_LENGTH = 100 + + +def test(algorithm, input_kind=_DEFAULT_INPUT_KIND, length=_DEFAULT_LENGTH): + if isinstance(algorithm, str): + algorithm = registry.get(algorithm) + xs = algorithm.gen_input(length, input_kind) + output = algorithm.function(xs) + if isinstance(output, array): + output = output.tolist() + print(output) + + +def _parse_non_negative_integer(s): + try: + n = int(s) + except ValueError: + raise argparse.ArgumentTypeError('must be a non-negative integer: ' + str(s)) + if n < 0: + raise argparse.ArgumentTypeError('must be a non-negative integer') + return n + + +def _parse_input_kind(s): + try: + return InputKind(s) + except ValueError: + raise argparse.ArgumentTypeError('invalid input kind: ' + str(s)) + + +def _format_algorithm(codename): + return '* {}: {}'.format(codename, registry.get(codename).display_name) + + +def _format_available_algorithms(): + descr = 'available algorithms (in the CODENAME: DISPLAY_NAME format):\n' + return descr + '\n'.join(map( + _format_algorithm, sorted(registry.get_codenames()))) + + +def _format_description(): + return _format_available_algorithms() + + +def _create_argument_parser(): + return argparse.ArgumentParser( + description=_format_description(), + formatter_class=argparse.RawDescriptionHelpFormatter) + + +def _parse_args(args=None): + if args is None: + args = sys.argv[1:] + parser = _create_argument_parser() + + parser.add_argument('algorithm', metavar='CODENAME', + choices=registry.get_codenames(), + help='algorithm codename') + parser.add_argument('--input', '-i', dest='input_kind', + choices=InputKind, + type=_parse_input_kind, + default=_DEFAULT_INPUT_KIND, + help='specify input kind') + parser.add_argument('--length', '-l', '-n', metavar='N', + type=_parse_non_negative_integer, + default=_DEFAULT_LENGTH, + help='set input length') + + return parser.parse_args(args) + + +def main(args=None): + test(**vars(_parse_args(args))) + + +if __name__ == '__main__': + main() |