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. --- quicksort.py | 65 ------------------------------------------------------------ 1 file changed, 65 deletions(-) delete mode 100644 quicksort.py (limited to 'quicksort.py') 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))) -- cgit v1.2.3