1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
# 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()
|
