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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
# Copyright 2015 Egor Tensin <Egor.Tensin@gmail.com>
# This file is licensed under the terms of the MIT License.
# See LICENSE.txt for details.
from time import clock
import gc
_ALGORITHMS = (
'bubble',
'bubble_optimized',
'heap',
'insertion',
'merge',
'quick_first',
'quick_second',
'quick_middle',
'quick_last',
'quick_random',
'selection',
)
def _get_context():
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('--repetitions', '-r', type=int, default=1,
help='set number of sorting repetitions')
parser.add_argument('--input', '-i',
default='randomized', metavar='INPUT',
choices=('sorted', 'randomized', 'reversed'),
help='choose initial input state')
parser.add_argument('--algorithm', '-l', metavar='ALGORITHM',
choices=_ALGORITHMS, required=True,
help='select sorting algorithm to use')
parser.add_argument('--min', '-a', type=int, required=True,
help='set min input length',
dest='min_input_length')
parser.add_argument('--max', '-b', type=int, required=True,
help='set max input length',
dest='max_input_length')
parser.add_argument('--output', '-o', dest='plot_path',
help='set plot output path')
args = parser.parse_args()
if args.repetitions < 1:
parser.error('number of repetitions must be > 0')
if args.min_input_length < 0:
parser.error('min sequence length must be >= 0')
if args.max_input_length < 0:
parser.error('max sequence length must be >= 0')
if args.max_input_length < args.min_input_length:
parser.error('max sequence length cannot be less than min sequence length')
return args
def get_timestamp():
return clock()
def init_clock():
get_timestamp()
def gen_input(args, n):
if args.input == 'sorted':
return list(range(n))
elif args.input == 'reversed':
return sorted(range(n), reverse=True)
elif args.input == 'randomized':
from random import sample
return sample(range(n), n)
else:
raise NotImplementedError(
'unimplemented 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 == 'bubble':
from bubble_sort import bubble_sort
plot_algorithm(ctx, bubble_sort)
elif ctx.algorithm == 'bubble_optimized':
from bubble_sort import bubble_sort_optimized
plot_algorithm(ctx, bubble_sort_optimized)
elif ctx.algorithm == 'heap':
from heapsort import heapsort
plot_algorithm(ctx, heapsort)
elif ctx.algorithm == 'insertion':
from insertion_sort import insertion_sort
plot_algorithm(ctx, insertion_sort)
elif ctx.algorithm == 'merge':
from merge_sort import merge_sort
plot_algorithm(ctx, merge_sort)
elif ctx.algorithm == 'quick_first':
from quicksort import quicksort_first
plot_algorithm(ctx, quicksort_first)
elif ctx.algorithm == 'quick_second':
from quicksort import quicksort_second
plot_algorithm(ctx, quicksort_second)
elif ctx.algorithm == 'quick_middle':
from quicksort import quicksort_middle
plot_algorithm(ctx, quicksort_middle)
elif ctx.algorithm == 'quick_last':
from quicksort import quicksort_last
plot_algorithm(ctx, quicksort_last)
elif ctx.algorithm == 'quick_random':
from quicksort import quicksort_random
plot_algorithm(ctx, quicksort_random)
elif ctx.algorithm == 'selection':
from selection_sort import selection_sort
plot_algorithm(ctx, selection_sort)
else:
raise NotImplementedError(
'unknown algorithm \'{}\''.format(ctx.algorithm))
if __name__ == '__main__':
ctx = _get_context()
init_clock()
plot(ctx)
|
