aboutsummaryrefslogtreecommitdiffstatshomepage
diff options
context:
space:
mode:
-rw-r--r--README.md3
-rw-r--r--algorithms/impl/median.py50
2 files changed, 52 insertions, 1 deletions
diff --git a/README.md b/README.md
index 406e6c1..2be13bb 100644
--- a/README.md
+++ b/README.md
@@ -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),
+ ]