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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
# 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 enum import Enum
import gc
from time import clock
class InputKind(Enum):
SORTED, RANDOMIZED, REVERSED = 'sorted', 'randomized', 'reversed'
def __str__(self):
return self.value
class SortingAlgorithm(Enum):
BUBBLE = 'bubble'
BUBBLE_OPTIMIZED = 'bubble_optimized'
HEAP = 'heap'
INSERTION = 'insertion'
MERGE = 'merge'
QUICK_FIRST = 'quick_first'
QUICK_SECOND = 'quick_second'
QUICK_MIDDLE = 'quick_middle'
QUICK_LAST = 'quick_last'
QUICK_RANDOM = 'quick_random'
SELECTION = 'selection'
def __str__(self):
return self.value
def _get_context():
def natural_number(s):
n = int(s)
if n < 0:
raise argparse.ArgumentTypeError('cannot be negative')
return n
def positive_number(s):
n = int(s)
if n < 1:
raise argparse.ArgumentTypeError('must be positive')
return n
def input_kind(s):
try:
return InputKind(s)
except ValueError:
raise argparse.ArgumentError()
def sorting_algorithm(s):
try:
return SortingAlgorithm(s)
except ValueError:
raise argparse.ArgumentError()
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('--repetitions', '-r',
type=positive_number, default=1,
help='set number of sorting repetitions')
parser.add_argument('--input', '-i',
choices=tuple(x for x in InputKind),
type=input_kind, default=InputKind.RANDOMIZED,
help='choose initial input state')
parser.add_argument('--algorithm', '-l', required=True,
choices=tuple(x for x in SortingAlgorithm),
type=sorting_algorithm,
help='select sorting algorithm to use')
parser.add_argument('--min', '-a', type=natural_number,
required=True, dest='min_input_length',
help='set min input length')
parser.add_argument('--max', '-b', type=natural_number,
required=True, dest='max_input_length',
help='set max input length')
parser.add_argument('--output', '-o', dest='plot_path',
help='set plot output path')
args = parser.parse_args()
if args.max_input_length < args.min_input_length:
parser.error('max input length cannot be less than min input length')
return args
def get_timestamp():
return clock()
def init_clock():
get_timestamp()
def gen_input(args, n):
if args.input is InputKind.SORTED:
return list(range(n))
elif args.input is InputKind.REVERSED:
return sorted(range(n), reverse=True)
elif args.input is InputKind.RANDOMIZED:
from random import sample
return sample(range(n), n)
else:
raise NotImplementedError(
'invalid 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 is SortingAlgorithm.BUBBLE:
from bubble_sort import bubble_sort
plot_algorithm(ctx, bubble_sort)
elif ctx.algorithm is SortingAlgorithm.BUBBLE_OPTIMIZED:
from bubble_sort import bubble_sort_optimized
plot_algorithm(ctx, bubble_sort_optimized)
elif ctx.algorithm is SortingAlgorithm.HEAP:
from heapsort import heapsort
plot_algorithm(ctx, heapsort)
elif ctx.algorithm is SortingAlgorithm.INSERTION:
from insertion_sort import insertion_sort
plot_algorithm(ctx, insertion_sort)
elif ctx.algorithm is SortingAlgorithm.MERGE:
from merge_sort import merge_sort
plot_algorithm(ctx, merge_sort)
elif ctx.algorithm is SortingAlgorithm.QUICK_FIRST:
from quicksort import quicksort_first
plot_algorithm(ctx, quicksort_first)
elif ctx.algorithm is SortingAlgorithm.QUICK_SECOND:
from quicksort import quicksort_second
plot_algorithm(ctx, quicksort_second)
elif ctx.algorithm is SortingAlgorithm.QUICK_MIDDLE:
from quicksort import quicksort_middle
plot_algorithm(ctx, quicksort_middle)
elif ctx.algorithm is SortingAlgorithm.QUICK_LAST:
from quicksort import quicksort_last
plot_algorithm(ctx, quicksort_last)
elif ctx.algorithm is SortingAlgorithm.QUICK_RANDOM:
from quicksort import quicksort_random
plot_algorithm(ctx, quicksort_random)
elif ctx.algorithm is SortingAlgorithm.SELECTION:
from selection_sort import selection_sort
plot_algorithm(ctx, selection_sort)
else:
raise NotImplementedError(
'invalid sorting algorithm \'{}\''.format(ctx.algorithm))
if __name__ == '__main__':
ctx = _get_context()
init_clock()
plot(ctx)
|
