diff options
| -rw-r--r-- | README.md | 3 | ||||
| -rw-r--r-- | algorithms/impl/median.py | 50 |
2 files changed, 52 insertions, 1 deletions
@@ -15,7 +15,8 @@ Currently the following algorithms are implemented: * insertion sort (`insertion_sort.py`), * merge sort (`merge_sort.py`), * quicksort (`quicksort.py`), -* selection sort (`selection_sort.py`). +* selection sort (`selection_sort.py`), +* calculating the median of a list (`median.py`). You can test each of the algorithms above by passing a sequence of integer numbers to the corresponding script: diff --git a/algorithms/impl/median.py b/algorithms/impl/median.py new file mode 100644 index 0000000..7bcce76 --- /dev/null +++ b/algorithms/impl/median.py @@ -0,0 +1,50 @@ +# Copyright 2016 Egor Tensin <Egor.Tensin@gmail.com> +# This file is licensed under the terms of the MIT License. +# See LICENSE.txt for details. + +from heapq import * + +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_sort_first(xs): + if not xs: + return 0.0 + xs.sort() + if len(xs) % 2: + return xs[len(xs) // 2] + else: + return xs[len(xs) // 2 - 1] / 2 + xs[len(xs) // 2] / 2 + +if __name__ == '__main__': + import sys + xs = list(map(int, sys.argv[1:])) + print(calc_median_sort_first(list(xs))) + print(calc_median_heaps(list(xs))) +else: + from algorithms.algorithm import Algorithm + _ALGORITHMS = [ + Algorithm('median_sort_first', 'Median (input is sorted first)', calc_median_sort_first), + Algorithm('median_heaps', 'Median (using heaps)', calc_median_heaps), + ] |