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 ++++ bubble_sort.py | 33 ------- heapsort.py | 54 ----------- insertion_sort.py | 15 ---- merge_sort.py | 29 ------ plot.py | 184 +++++++++++++------------------------- quicksort.py | 65 -------------- selection_sort.py | 17 ---- test.py | 53 +++++++++++ 18 files changed, 435 insertions(+), 334 deletions(-) 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 delete mode 100644 bubble_sort.py delete mode 100644 heapsort.py delete mode 100644 insertion_sort.py delete mode 100644 merge_sort.py delete mode 100644 quicksort.py delete mode 100644 selection_sort.py create mode 100644 test.py 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] diff --git a/bubble_sort.py b/bubble_sort.py deleted file mode 100644 index 8309201..0000000 --- a/bubble_sort.py +++ /dev/null @@ -1,33 +0,0 @@ -# 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))) diff --git a/heapsort.py b/heapsort.py deleted file mode 100644 index 3f44e51..0000000 --- a/heapsort.py +++ /dev/null @@ -1,54 +0,0 @@ -# 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:])))) diff --git a/insertion_sort.py b/insertion_sort.py deleted file mode 100644 index 9e0912d..0000000 --- a/insertion_sort.py +++ /dev/null @@ -1,15 +0,0 @@ -# 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:])))) diff --git a/merge_sort.py b/merge_sort.py deleted file mode 100644 index 6d5403d..0000000 --- a/merge_sort.py +++ /dev/null @@ -1,29 +0,0 @@ -# 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:])))) diff --git a/plot.py b/plot.py index 99452c4..2771467 100644 --- a/plot.py +++ b/plot.py @@ -12,23 +12,59 @@ class InputKind(Enum): def __str__(self): return self.value -class SortingAlgorithm(Enum): - BUBBLE = 'bubble' - BUBBLE_OPTIMIZED = 'bubble_optimized' - HEAP = 'heap' - INSERTION = 'insertion' - MERGE = 'merge' - QUICK_FIRST = 'quick_first' - QUICK_SECOND = 'quick_second' - QUICK_MIDDLE = 'quick_middle' - QUICK_LAST = 'quick_last' - QUICK_RANDOM = 'quick_random' - SELECTION = 'selection' +def get_timestamp(): + return clock() - def __str__(self): - return self.value +def init_clock(): + get_timestamp() + +def gen_input(kind, n): + if kind is InputKind.SORTED: + return list(range(n)) + elif kind is InputKind.REVERSED: + return sorted(range(n), reverse=True) + elif kind is InputKind.RANDOMIZED: + from random import sample + return sample(range(n), n) + else: + raise NotImplementedError( + 'invalid initial input state \'{}\''.format(kind)) + +def measure_running_time(algorithm, kind, xs_len, repetitions): + xs = gen_input(kind, xs_len) + xss = [list(xs) for _ in range(repetitions)] + algorithm = algorithm.get_function() + gc.disable() + started_at = get_timestamp() + for i in range(repetitions): + algorithm(xss[i]) + finished_at = get_timestamp() + gc.enable() + return finished_at - started_at + +def _decorate_plot(algorithm, repetitions, kind, plt): + plt.grid() + plt.xlabel('Input length') + plt.ylabel('Running time (sec)') + plt.title('{}, {} repetition(s), {} input'.format( + algorithm.get_display_name(), repetitions, kind)) + +def plot_algorithm(algorithm, repetitions, kind, min_len, max_len, output_path=None): + import matplotlib.pyplot as plt + _decorate_plot(algorithm, repetitions, kind, plt) + xs_lengths = range(min_len, max_len + 1) + running_time = [] + for xs_len in xs_lengths: + running_time.append(measure_running_time(algorithm, kind, xs_len, repetitions)) + plt.plot(xs_lengths, running_time) + if output_path is None: + plt.show() + else: + plt.savefig(output_path) + +if __name__ == '__main__': + import algorithms.registry -def _get_context(): def natural_number(s): n = int(s) if n < 0: @@ -44,13 +80,12 @@ def _get_context(): return InputKind(s) except ValueError: raise argparse.ArgumentError() - def sorting_algorithm(s): - try: - return SortingAlgorithm(s) - except ValueError: - raise argparse.ArgumentError() + import argparse parser = argparse.ArgumentParser() + parser.add_argument('--algorithm', '-l', required=True, + choices=algorithms.registry.get_codenames(), + help='specify sorting algorithm to use') parser.add_argument('--repetitions', '-r', type=positive_number, default=1, help='set number of sorting repetitions') @@ -58,113 +93,20 @@ def _get_context(): choices=tuple(x for x in InputKind), type=input_kind, default=InputKind.RANDOMIZED, help='choose initial input state') - parser.add_argument('--algorithm', '-l', required=True, - choices=tuple(x for x in SortingAlgorithm), - type=sorting_algorithm, - help='select sorting algorithm to use') parser.add_argument('--min', '-a', type=natural_number, - required=True, dest='min_input_length', + required=True, dest='min_len', help='set min input length') parser.add_argument('--max', '-b', type=natural_number, - required=True, dest='max_input_length', + required=True, dest='max_len', help='set max input length') - parser.add_argument('--output', '-o', dest='plot_path', + parser.add_argument('--output', '-o', dest='output_path', help='set plot output path') args = parser.parse_args() - if args.max_input_length < args.min_input_length: + if args.max_len < args.min_len: parser.error('max input length cannot be less than min input length') - return args - -def get_timestamp(): - return clock() - -def init_clock(): - get_timestamp() -def gen_input(args, n): - if args.input is InputKind.SORTED: - return list(range(n)) - elif args.input is InputKind.REVERSED: - return sorted(range(n), reverse=True) - elif args.input is InputKind.RANDOMIZED: - from random import sample - return sample(range(n), n) - else: - raise NotImplementedError( - 'invalid initial input state \'{}\''.format(args.input)) - -def measure_running_time(ctx, algorithm, input_length): - xs = gen_input(ctx, input_length) - assert algorithm(list(xs)) == sorted(xs) - input_copies = [list(xs) for i in range(ctx.repetitions)] - gc.disable() - starting_time = get_timestamp() - for i in range(ctx.repetitions): - algorithm(input_copies[i]) - running_time = get_timestamp() - starting_time - gc.enable() - return running_time - -def _decorate_plot(ctx, plt): - plt.grid() - plt.xlabel('Input length') - plt.ylabel('Running time (sec)') - plt.title('{} sort, {} repetition(s), {} input'.format( - ctx.algorithm, ctx.repetitions, ctx.input)) - -def plot_algorithm(ctx, algorithm): - import matplotlib.pyplot as plt - _decorate_plot(ctx, plt) - input_length = range(ctx.min_input_length, - ctx.max_input_length + 1) - running_time = [] - for n in input_length: - running_time.append(measure_running_time(ctx, algorithm, n)) - plt.plot(input_length, running_time) - if ctx.plot_path is not None: - plt.savefig(ctx.plot_path) - else: - plt.show() - -def plot(ctx): - if ctx.algorithm is SortingAlgorithm.BUBBLE: - from bubble_sort import bubble_sort - plot_algorithm(ctx, bubble_sort) - elif ctx.algorithm is SortingAlgorithm.BUBBLE_OPTIMIZED: - from bubble_sort import bubble_sort_optimized - plot_algorithm(ctx, bubble_sort_optimized) - elif ctx.algorithm is SortingAlgorithm.HEAP: - from heapsort import heapsort - plot_algorithm(ctx, heapsort) - elif ctx.algorithm is SortingAlgorithm.INSERTION: - from insertion_sort import insertion_sort - plot_algorithm(ctx, insertion_sort) - elif ctx.algorithm is SortingAlgorithm.MERGE: - from merge_sort import merge_sort - plot_algorithm(ctx, merge_sort) - elif ctx.algorithm is SortingAlgorithm.QUICK_FIRST: - from quicksort import quicksort_first - plot_algorithm(ctx, quicksort_first) - elif ctx.algorithm is SortingAlgorithm.QUICK_SECOND: - from quicksort import quicksort_second - plot_algorithm(ctx, quicksort_second) - elif ctx.algorithm is SortingAlgorithm.QUICK_MIDDLE: - from quicksort import quicksort_middle - plot_algorithm(ctx, quicksort_middle) - elif ctx.algorithm is SortingAlgorithm.QUICK_LAST: - from quicksort import quicksort_last - plot_algorithm(ctx, quicksort_last) - elif ctx.algorithm is SortingAlgorithm.QUICK_RANDOM: - from quicksort import quicksort_random - plot_algorithm(ctx, quicksort_random) - elif ctx.algorithm is SortingAlgorithm.SELECTION: - from selection_sort import selection_sort - plot_algorithm(ctx, selection_sort) - else: - raise NotImplementedError( - 'invalid sorting algorithm \'{}\''.format(ctx.algorithm)) - -if __name__ == '__main__': - ctx = _get_context() init_clock() - plot(ctx) + plot_algorithm(algorithms.registry.get(args.algorithm), + args.repetitions, args.input, + args.min_len, args.max_len, + args.output_path) diff --git a/quicksort.py b/quicksort.py deleted file mode 100644 index b8ecc18..0000000 --- a/quicksort.py +++ /dev/null @@ -1,65 +0,0 @@ -# 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))) diff --git a/selection_sort.py b/selection_sort.py deleted file mode 100644 index c466bea..0000000 --- a/selection_sort.py +++ /dev/null @@ -1,17 +0,0 @@ -# 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:])))) diff --git a/test.py b/test.py new file mode 100644 index 0000000..b3d9dd3 --- /dev/null +++ b/test.py @@ -0,0 +1,53 @@ +# Copyright 2016 Egor Tensin +# This file is licensed under the terms of the MIT License. +# See LICENSE.txt for details. + +from enum import Enum + +class InputKind(Enum): + SORTED, RANDOMIZED, REVERSED = 'sorted', 'randomized', 'reversed' + + def __str__(self): + return self.value + +def gen_input(kind, n): + if kind is InputKind.SORTED: + return list(range(n)) + elif kind is InputKind.REVERSED: + return sorted(range(n), reverse=True) + elif kind is InputKind.RANDOMIZED: + from random import sample + return sample(range(n), n) + else: + raise NotImplementedError( + 'invalid initial input state \'{}\''.format(kind)) + +if __name__ == '__main__': + import algorithms.registry + + def natural_number(s): + n = int(s) + if n < 0: + raise argparse.ArgumentTypeError('cannot be negative') + return n + def input_kind(s): + try: + return InputKind(s) + except ValueError: + raise argparse.ArgumentError() + + import argparse + parser = argparse.ArgumentParser() + parser.add_argument('--algorithm', '-l', required=True, + choices=algorithms.registry.get_codenames(), + help='specify algorithm codename') + parser.add_argument('--input', '-i', + choices=tuple(x for x in InputKind), + type=input_kind, default=InputKind.RANDOMIZED, + help='set initial input state') + parser.add_argument('--length', '-n', + type=natural_number, default=100, + help='set input length') + args = parser.parse_args() + xs = gen_input(args.input, args.length) + print(algorithms.registry.get(args.algorithm).get_function()(xs)) -- cgit v1.2.3