Skip to content

Instantly share code, notes, and snippets.

@kajott

kajott/sortvis.py

Last active August 8, 2019 21:25
Show Gist options
  • Save kajott/5a703e0f3f673da02d54ca95c09d1c29 to your computer and use it in GitHub Desktop.
Save kajott/5a703e0f3f673da02d54ca95c09d1c29 to your computer and use it in GitHub Desktop.
Download ZIP
visualization of various in-place sorting algorithms
Raw
sortvis.py
#!/usr/bin/env python3
"""
Visualization of various in-place sorting algorithms.
Can generate a HTML page and video files to browse and display the results.
Note: requires FFmpeg to display and export the visualizations.
The code snippets in the HTML report are syntax highlighted if Pygments
is installed.
"""
import sys, os, random, subprocess, inspect, re, argparse
COLUMNS = 32
ROWS = 32
CELL_WIDTH = 16
CELL_HEIGHT = 16
DEFAULT_COLORMAP = "inferno"
DEFAULT_OUTDIR = "sortvis"
PERMANENT_MARGIN = 1
MARK_MARGIN = 2
BACKGROUND_COLOR = bytes([0,0,0])
MARK_CMP, MARK_SWAP, MARK_MOVE, MARK_DONE = range(4)
MARK_COLORS = {
MARK_CMP: bytes([0,0,0]),
MARK_SWAP: bytes([255,255,255]),
MARK_MOVE: bytes([255,255,255]),
MARK_DONE: bytes([255,255,255]),
}
PERMANENT_MARGIN_UL = PERMANENT_MARGIN // 2
PERMANENT_MARGIN_LR = PERMANENT_MARGIN - PERMANENT_MARGIN_UL
UNMARKED_WIDTH = CELL_WIDTH - PERMANENT_MARGIN
UNMARKED_HEIGHT = CELL_HEIGHT - PERMANENT_MARGIN
MARK_MARGIN_UL = MARK_MARGIN // 2
MARK_MARGIN_LR = MARK_MARGIN - MARK_MARGIN_UL
MARKED_WIDTH = UNMARKED_WIDTH - MARK_MARGIN
MARKED_HEIGHT = UNMARKED_HEIGHT - MARK_MARGIN
assert (MARKED_WIDTH >= 0) and (MARKED_HEIGHT >= 0)
PERMANENT_MARGIN_LINE = BACKGROUND_COLOR * CELL_WIDTH
PERMANENT_MARGIN_LR_DATA = BACKGROUND_COLOR * PERMANENT_MARGIN_LR
def _cmxform(raw): return list(zip(*(raw[::-1])))
COLORMAPS = {
"viridis": _cmxform([
( 0.2777273272234177, 0.005407344544966578, 0.3340998053353061),
( 0.1050930431085774, 1.404613529898575, 1.384590162594685),
(-0.3308618287255563, 0.214847559468213, 0.09509516302823659),
(-4.634230498983486, -5.799100973351585, -19.33244095627987),
( 6.228269936347081, 14.17993336680509, 56.69055260068105),
( 4.776384997670288, -13.74514537774601, -65.35303263337234),
(-5.435455855934631, 4.645852612178535, 26.3124352495832),
]),
"plasma": _cmxform([
(0.05873234392399702, 0.02333670892565664, 0.5433401826748754),
(2.176514634195958, 0.2383834171260182, 0.7539604599784036),
(-2.689460476458034, -7.455851135738909, 3.110799939717086),
(6.130348345893603, 42.3461881477227, -28.51885465332158),
(-11.10743619062271, -82.66631109428045, 60.13984767418263),
(10.02306557647065, 71.41361770095349, -54.07218655560067),
(-3.658713842777788, -22.93153465461149, 18.19190778539828),
]),
"magma": _cmxform([
(-0.002136485053939582, -0.000749655052795221, -0.005386127855323933),
(0.2516605407371642, 0.6775232436837668, 2.494026599312351),
(8.353717279216625, -3.577719514958484, 0.3144679030132573),
(-27.66873308576866, 14.26473078096533, -13.64921318813922),
(52.17613981234068, -27.94360607168351, 12.94416944238394),
(-50.76852536473588, 29.04658282127291, 4.23415299384598),
(18.65570506591883, -11.48977351997711, -5.601961508734096),
]),
"inferno": _cmxform([
(0.0002189403691192265, 0.001651004631001012, -0.01948089843709184),
(0.1065134194856116, 0.5639564367884091, 3.932712388889277),
(11.60249308247187, -3.972853965665698, -15.9423941062914),
(-41.70399613139459, 17.43639888205313, 44.35414519872813),
(77.162935699427, -33.40235894210092, -81.80730925738993),
(-71.31942824499214, 32.62606426397723, 73.20951985803202),
(25.13112622477341, -12.24266895238567, -23.07032500287172),
]),
}
COLORMAP = COLORMAPS[DEFAULT_COLORMAP]
g_fail_count = 0
###############################################################################
def lerp(a, b, t):
return a + (b - a) * t
def GenerateVariableRandomness(n, r):
rev = 1.0 if (r > 0.5) else 0.0
r = 1.0 - 2.0 * abs(r - 0.5)
x = list(range(n))
w = [lerp(abs(rev - i / (n - 1)), random.random(), r) for i in x]
return sorted(x, key=lambda i: w[i])
def horner(poly, x):
y = 0.0
for c in poly:
y = (y * x) + c
return y
_cached_palettes = {}
def GetPalette(size):
global _cached_palettes
try:
return _cached_palettes[size]
except KeyError:
pass
pal = [bytes(max(0, min(255, int(horner(rgb, i / (size - 1)) * 255.0 + 0.5))) for rgb in COLORMAP)
for i in range(size)]
_cached_palettes[size] = pal
return pal
###############################################################################
class PhaseRow:
def __init__(self, seq, mark_type=0, mark_indexes=[]):
self.seq = list(seq)
self.mark_color = MARK_COLORS.get(mark_type, bytes([0,0,0]))
self.mark_indexes = set(mark_indexes)
def render(self, minval=0, maxval=None):
if not maxval:
maxval = max(self.seq)
palette = GetPalette(maxval - minval + 1)
for y in range(PERMANENT_MARGIN_UL):
yield PERMANENT_MARGIN_LINE * len(self.seq)
for y in range(UNMARKED_HEIGHT):
line = bytearray()
for i, v in enumerate(self.seq):
color = palette[min(maxval, max(minval, v)) - minval]
if not(i in self.mark_indexes):
line.extend(UNMARKED_WIDTH * color)
elif MARK_MARGIN_UL <= y < (MARK_MARGIN_UL + MARKED_HEIGHT):
line.extend(MARK_MARGIN_UL * self.mark_color + MARKED_WIDTH * color + MARK_MARGIN_LR * self.mark_color)
else:
line.extend(UNMARKED_WIDTH * self.mark_color)
line.extend(PERMANENT_MARGIN_LR_DATA)
yield bytes(line)
for y in range(PERMANENT_MARGIN_LR):
yield PERMANENT_MARGIN_LINE * len(self.seq)
def _frame_to_ppm(filename, src):
linesize = None
data = bytearray()
for line in src:
if linesize:
assert linesize == len(line)
else:
linesize = len(line)
data.extend(line)
assert linesize
assert not(linesize % 3)
with open(filename, 'wb') as f:
f.write(b'P6\n%d %d\n255\n' % (linesize / 3, len(data) / linesize))
f.write(data)
class SortVisualizer:
def __init__(self, initial_seq, algorithm=None):
self.initial_seq = list(initial_seq)
self.size = len(self.initial_seq)
self.phases = []
if algorithm:
self.run(algorithm)
def run(self, algorithm, name=None):
self.alg_name = name or algorithm.__name__
self.phases = []
self.seq = list(self.initial_seq)
self.mark()
algorithm(self)
if self.seq != sorted(self.seq):
print("===== SELF-TEST FAILED =====")
print("Algorithm: ", self.alg_name)
print("Input: ", " ".join(str(x).rjust(2) for x in self.initial_seq))
print("Output: ", " ".join(str(x).rjust(2) for x in self.seq))
print("Expected: ", " ".join(str(x).rjust(2) for x in sorted(self.seq)))
global g_fail_count
g_fail_count += 1
self.mark(MARK_DONE, range(self.size))
self.mark()
self.steps = len(self.phases) - 3
return self.steps
def mark(self, mark_type=0, mark_indexes=[]):
self.phases.append(PhaseRow(self.seq, mark_type, mark_indexes))
def cmp(self, a, b):
"""
primitive operation: compare values at two indices 'a' and 'b',
return -1 if seq[a] < seq[b], 0 if seq[a] == seq[b], +1 if seq[a] > seq[b]
"""
if a == b: return 0
self.mark(MARK_CMP, (a,b))
a = self.seq[a]
b = self.seq[b]
if a < b: return -1
if a > b: return +1
return 0
def cmp_with_value(self, a, v):
"""
primitive operation: compare value at index a with value v
return -1 if seq[a] < v, 0 if seq[a] == v, +1 if seq[a] > v
"""
self.mark(MARK_CMP, [a])
a = self.seq[a]
if a < v: return -1
if a > v: return +1
return 0
def swap(self, a, b):
"""
primitive operation: swap items at indices 'a' and 'b'
"""
if a == b: return
self.seq[a], self.seq[b] = self.seq[b], self.seq[a]
self.mark(MARK_SWAP, (a,b))
def swap_with_value(self, a, v):
"""
primitive operation: set item at index 'a' to value 'v',
and return old value of index 'a'
"""
self.seq[a], v = v, self.seq[a]
self.mark(MARK_SWAP, [a])
return v
def move(self, a, b):
"""
primitive operation: move item from index a to index b
"""
self.seq.insert(b - (b > a), self.seq.pop(a))
self.mark(MARK_MOVE, [b])
def render_phase(self, phase, minval=0, maxval=None):
yield from self.phases[min(phase, len(self.phases) - 1)].render(minval, maxval)
def render(self, minval=0, maxval=None):
for phase in self.phases:
yield from phase.render(minval, maxval)
def phases_save(self, filename, minval=0, maxval=None):
_frame_to_ppm(filename, self.render(minval, maxval))
@property
def width(self):
return CELL_WIDTH * self.size
@property
def height(self):
return CELL_HEIGHT * self.frames
@property
def frames(self):
return len(self.phases)
class MultiSortVisualizer:
stat_header_printed = False
def __init__(self, initial_seqs, algorithm=None):
self.seqs = list(map(SortVisualizer, initial_seqs))
assert len(set(len(s.initial_seq) for s in self.seqs)) == 1
self.alg_name = None
if algorithm:
self.run(algorithm)
def run(self, algorithm, name=None):
self.alg_name = name or algorithm.__name__
for seq in self.seqs:
seq.run(algorithm)
def print_stats(self):
if not self.__class__.stat_header_printed:
self.__class__.stat_header_printed = True
print("algorithm | min | avg | med | max")
print("---------------------+-------+-------+-------+------")
steps = [seq.steps for seq in self.seqs]
print("{name:<20} | {min:5} | {avg:5} | {med:5} | {max:5}".format(
name=self.alg_name,
min=min(steps), max=max(steps),
avg=(sum(steps)+len(steps)//2)//len(steps),
med=steps[len(steps)//2],
))
def render_frame(self, frame, minval=0, maxval=None):
for seq in self.seqs:
yield from seq.render_phase(frame, minval, maxval)
def render_all(self, minval=0, maxval=None):
for frame in range(self.frames):
yield b''.join(self.render_frame(frame, minval, maxval))
def frame_save(self, filename, frame=0, minval=0, maxval=None):
_frame_to_ppm(filename, self.render_frame(frame, minval, maxval))
def _ffmpeg_in_opts(self, fps=30):
return
def _send_to_ffmpeg(self, pre_args, post_args, fps=30, minval=0, maxval=None):
cmdline = pre_args + [
"-f", "rawvideo",
"-pixel_format", "rgb24",
"-video_size", "{}x{}".format(self.width, self.height),
"-framerate", str(fps),
] + post_args
print(os.getenv("PS4", "+ ") + " ".join(('"'+arg+'"' if (' ' in arg) else arg) for arg in cmdline))
proc = subprocess.Popen(cmdline, stdin=subprocess.PIPE)
for frame in self.render_all(minval, maxval):
try:
proc.stdin.write(frame)
except EnvironmentError as e:
print("output cancelled by user:", e)
break
proc.stdin.close()
proc.wait()
def video_show(self, fps=60, minval=0, maxval=None):
self._send_to_ffmpeg(["ffplay", "-loglevel", "warning"], ["-",
"-window_title", "Sort Visualization: " + self.alg_name
], fps=fps, minval=minval, maxval=maxval)
def video_save(self, outfile, fps=60, crf=18, minval=0, maxval=None):
self._send_to_ffmpeg(["ffmpeg", "-y"], ["-i", "-", "-an", "-sn",
"-vf", "format=yuv420p",
"-c:v", "libx264",
"-preset:v", "veryslow",
"-profile:v", "main",
"-crf:v", str(crf),
outfile], fps=fps, minval=minval, maxval=maxval)
@property
def width(self):
return self.seqs[0].width
@property
def height(self):
return CELL_HEIGHT * len(self.seqs)
@property
def frames(self):
return max(s.frames for s in self.seqs)
###############################################################################
algorithms = []
def algorithm(alg):
algorithms.append(alg)
return alg
@algorithm
def SlowSort(data):
"""
Slow sort.
An artificially slow recursive sorting algorithm.
https://en.wikipedia.org/wiki/Slowsort
"""
def partition(a, b):
if a >= b: return
m = (a + b) // 2
partition(a, m)
partition(m+1, b)
if data.cmp(m, b) > 0:
data.swap(m, b)
partition(a, b-1)
partition(0, data.size - 1)
@algorithm
def SlowSort2(data):
"""
Slightly optimized slow sort.
Shrinks the unsorted area in both directions.
"""
def partition(a, b):
if a >= b: return
m = (a + b) // 2
partition(a, m)
partition(m+1, b)
if data.cmp(m, b) > 0:
data.swap(m, b)
if (m > a) and ((m + 1) < b):
if data.cmp(a, m+1) > 0:
data.swap(a, m+1)
a += 1
partition(a, b-1)
partition(0, data.size - 1)
@algorithm
def StoogeSort(data):
"""
Stooge sort.
An inefficient recursive algorithm of O(n^2.7).
https://en.wikipedia.org/wiki/Stooge_sort
"""
def partition(a, b):
if data.cmp(a, b) > 0:
data.swap(a, b)
if (a + 1) >= b: return
p = (b - a + 1) // 3
partition(a, b-p)
partition(a+p, b)
partition(a, b-p)
partition(0, data.size - 1)
@algorithm
def InsertionSort(data):
"""
Insertion sort.
For each new element, insert it at the appropriate position inside the
already-sorted list on the left.
Since this means that everything right of the insertion location needs to
be moved one position upwards, this looks and behaves very much like
bubble sort.
"""
for i in range(1, data.size):
for j in range(i, 0, -1):
if data.cmp(j-1, j) <= 0:
break
data.swap(j-1, j)
@algorithm
def GnomeSort(data):
"""
Gnome sort.
Similar to insertion sort, but slower,
and very simple: it doesn't even need nested loops.
https://en.wikipedia.org/wiki/Gnome_sort
"""
i = 0
while i < data.size:
if (i == 0) or (data.cmp(i-1, i) <= 0):
i += 1
else:
data.swap(i, i-1)
i -= 1
@algorithm
def BubbleSort(data):
"""
Naive bubble sort.
Sorts adjacent elements and repeats until fully sorted.
https://en.wikipedia.org/wiki/Bubble_sort#Pseudocode_implementation
"""
swapped = True
while swapped:
swapped = False
for i in range(data.size - 1):
if data.cmp(i, i+1) > 0:
data.swap(i, i+1)
swapped = True
@algorithm
def BubbleSort2(data):
"""
Optimized bubble sort.
Exploits the fact that the highest element is moved into its proper place
in each bubble round.
https://en.wikipedia.org/wiki/Bubble_sort#Optimizing_bubble_sort
"""
for n in range(data.size - 1, 0, -1):
for i in range(n):
if data.cmp(i, i+1) > 0:
data.swap(i, i+1)
@algorithm
def BubbleSort3(data):
"""
Further optimized bubble sort.
As BubbleSort2, but detects if more than one highest element is moved into
the proper place.
https://en.wikipedia.org/wiki/Bubble_sort#Optimizing_bubble_sort
"""
n = data.size
while n > 1:
next_n = 1
for i in range(n - 1):
if data.cmp(i, i+1) > 0:
data.swap(i, i+1)
next_n = i + 1
n = next_n
@algorithm
def BubbleSort4(data):
"""
Bubble sort / selection sort hybrid.
Technically still a bubble sort variant, but constructs the result
in opposite order, like selection sort.
"""
for i in range(data.size - 1):
for j in range(i + 1, data.size):
if data.cmp(i, j) > 0:
data.swap(i, j)
@algorithm
def ShakerSort(data):
"""
Cocktail shaker sort.
A bi-directional variant of bubble sort.
https://en.wikipedia.org/wiki/Cocktail_shaker_sort
"""
swapped = True
reverse = False
while swapped:
swapped = False
for i in (range(data.size - 2, -1, -1) if reverse else range(data.size - 1)):
if data.cmp(i, i+1) > 0:
data.swap(i, i+1)
swapped = True
reverse = not(reverse)
@algorithm
def ShakerSort2(data):
"""
Optimized cocktail shaker sort.
Reduces the sortable range dynamically to speed things up.
https://en.wikipedia.org/wiki/Cocktail_shaker_sort
"""
a, b = 0, data.size - 2
while a <= b:
next_a, next_b = b, a
for i in range(a, b+1):
if data.cmp(i, i+1) > 0:
data.swap(i, i+1)
next_b = i
b = next_b - 1
for i in range(b, a-1, -1):
if data.cmp(i, i+1) > 0:
data.swap(i, i+1)
next_a = i
a = next_a + 1
@algorithm
def OddEvenSort(data):
"""
Odd-even sort.
An unconventional bubblesort variant.
https://en.wikipedia.org/wiki/Odd-even_sort
"""
done = False
while not done:
done = True
for phase in (0, 1):
for i in range(phase, data.size - 1, 2):
if data.cmp(i, i+1) > 0:
data.swap(i, i+1)
done = False
@algorithm
def SelectionSort(data):
"""
Selection sort.
Find the lowest element of the unsorted list and move it into position;
rinse and repeat.
"""
for i in range(data.size - 1):
smallest = i
for j in range(i, data.size):
if data.cmp(j, smallest) < 0:
smallest = j
data.swap(smallest, i)
@algorithm
def ShellSort(data):
"""
Sorting method by Donald Shell.
Insertion sort variant that operates over larger gaps first,
moving items roughly into their proper position,
before refining with lower gap sizes.
Using a gap sequence by Marcin Ciura.
https://en.wikipedia.org/wiki/Shellsort
"""
for gap in (701, 301, 132, 57, 23, 10, 4, 1):
for i in range(gap, data.size):
for j in range(i, gap-1, -gap):
if data.cmp(j-gap, j) <= 0:
break
data.swap(j-gap, j)
@algorithm
def CombSort(data):
"""
Comb sort.
An algorithm similar to shell sort,
but slightly less effective.
https://en.wikipedia.org/wiki/Comb_sort
"""
gap = data.size
done = False
while not done:
gap = max(1, int(gap / 1.3))
done = (gap == 1)
for i in range(data.size - gap):
if data.cmp(i, i+gap) > 0:
data.swap(i, i+gap)
done = False
@algorithm
def QuickSort(data):
"""
In-place quicksort by Nico Lomuto, with pivot at end of list.
https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme
"""
def partition(a, b):
if a >= b: return
i, p = a, b
for j in range(a, b):
if data.cmp(j, p) < 0:
data.swap(i, j)
if i == p: p = i # we may have moved the pivot around,
elif j == p: p = j # so adjust for that
i += 1
data.swap(i, b)
partition(a, i - 1)
partition(i + 1, b)
partition(0, data.size - 1)
@algorithm
def QuickSort2(data, maxdepth=None, fallback=None):
"""
In-place quicksort by C.A.R. Hoare, with centered pivot.
https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme
"""
# the implementation has been extended to cater for hybrid sorts
def partition(a, b, depth):
if a >= b: return
if maxdepth and (depth >= maxdepth):
return fallback(data, a, b)
orig_a, orig_b = a, b
p = (a + b) // 2
while True:
while data.cmp(a, p) < 0: a += 1
while data.cmp(b, p) > 0: b -= 1
if a >= b: break
oldp = data.seq[p]
data.swap(a, b)
if a == p: p = b # we may have moved the pivot around,
elif b == p: p = a # so adjust for that
a += 1
b -= 1
partition(orig_a, b, depth + 1)
partition(b + 1, orig_b, depth + 1)
partition(0, data.size - 1, 0)
@algorithm
def HeapSort(data, start=0, end=None):
"""
Sift-up heap sort.
https://en.wikipedia.org/wiki/Heapsort
"""
# the implementation has been extended to cater for hybrid sorts;
# specifically, it has been made possible to sort only a subrange
if not end:
end = data.size - 1
n = end - start
def fix_heap(root):
while 2 * root < n:
child = 2 * root + 1
swap = root
if data.cmp(start + swap, start + child) < 0:
swap = child
if (child < n) and (data.cmp(start + swap, start + child + 1) < 0):
swap = child + 1
if swap == root:
return
data.swap(start + root, start + swap)
root = swap
for i in range(n // 2, -1, -1):
fix_heap(i)
while n > 0:
data.swap(start, start + n)
n -= 1
fix_heap(0)
@algorithm
def IntroSort(data):
"""
A quicksort/heapsort hybrid.
Uses quicksort up to a certain recursion level,
and heapsort for deeper partitions.
https://en.wikipedia.org/wiki/Introsort
"""
# compute recursion limit first: floor(log2(size)) * 2
n = data.size - 1
bits = 0
while n:
bits += 1
n >>= 1
return QuickSort2(data, bits * 2, HeapSort)
@algorithm
def MergeSort(data):
"""
In-place simulation of bottom-up merge sort.
Merge sort isn't possible in-place, so we're cheating a bit here:
inserting a value into the sorted list (thereby possibly shifting
the remaining unsorted list's items around) is counted as a
constant-time operation, which it would be if we used extra memory.
https://en.wikipedia.org/wiki/Merge_sort
"""
block = 2
while block <= (data.size * 2 - 1):
for start in range(0, data.size, block):
a = start
b = start + block // 2
end = min(start + block, data.size)
while (a < b) and (b < end):
if data.cmp(a, b) <= 0:
data.move(a, a)
else:
data.move(b, a)
b += 1
a += 1
block *= 2
@algorithm
def CycleSort(data):
"""
Cycle sort.
A sorting method that minimizes the number of write operations,
at the expense of significantly more read operations.
https://en.wikipedia.org/wiki/Cycle_sort
"""
for start in range(data.size - 1):
item = data.seq[start]
pos = start
for i in range(start + 1, data.size):
if data.cmp_with_value(i, item) < 0: pos += 1
if pos == start: continue
while data.cmp_with_value(pos, item) == 0: pos += 1
item = data.swap_with_value(pos, item)
while pos != start:
pos = start
for i in range(start + 1, data.size):
if data.cmp_with_value(i, item) < 0: pos += 1
while data.cmp_with_value(pos, item) == 0: pos += 1
item = data.swap_with_value(pos, item)
"""
Not implemented due to high complexity:
- https://en.wikipedia.org/wiki/Timsort
- https://en.wikipedia.org/wiki/Cubesort
- https://en.wikipedia.org/wiki/Smoothsort
- https://en.wikipedia.org/wiki/Block_sort
"""
###############################################################################
class AlgorithmResults:
def __init__(self, vis, alg, rerender=False):
self.name = alg.__name__
self.video = self.name + ".mp4"
if rerender or not(os.path.isfile(self.video)):
vis.video_save(self.video)
self.width = vis.width
self.height = vis.height
# gather statistics
times = [seq.steps for seq in vis.seqs]
self.t_min = min(times)
self.t_avg = (sum(times) + len(times) // 2) // len(times)
self.t_max = max(times)
times = [(t,i) for i,t in enumerate(times)]
self.s_min = self.get_scenario(min(times)[1], len(vis.seqs[0].initial_seq))
self.s_max = self.get_scenario(max(times)[1], len(vis.seqs[0].initial_seq))
# extract the raw docstring and source code, then
# - strip unneccessary stuff from the source by
# - detecting where the docstring is located in the source,
# cutting the surrounding """ / ''' markers and associated
# whitespace off, and reassembling the halves
# - removing decorator line(s)
# - split the docstring by paragraphs
doc = alg.__doc__
src = inspect.getsource(alg)
pos = src.find(doc)
assert pos >= 0
src = src[:pos].expandtabs(8).rstrip("'\"").rstrip() \
+ src[pos+len(doc):].expandtabs(8).lstrip("'\"").lstrip(" ")
while src.startswith('@'):
src = src[src.find('\n')+1:]
doc = list(map(str.strip, re.sub(r'\.\s*$', '.\x00', doc, flags=re.M).split('\x00')))
self.doc = doc
self.src = src
@staticmethod
def get_scenario(pos, total):
if pos <= 0: return "fully sorted"
if pos <= total // 4: return "almost sorted"
if pos >= total - 1: return "fully reversed"
if pos >= (total * 3 + 2) // 4: return "almost reversed"
return "random"
def T(x): return x.replace("{", "{{").replace("}", "}}").replace("$[", "{").replace("]$", "}")
def H(x): return x.replace("&", "&amp;").replace("<", "&lt;").replace(">", "&gt;")
def L(x): return re.sub(r'(https?://[^ ]+)', r'<a href="\1">\1</a>', x)
try:
import pygments
from pygments.lexers import PythonLexer
from pygments.formatters import HtmlFormatter
def C(code):
return pygments.highlight(code, PythonLexer(), HtmlFormatter())
except ImportError:
def C(code):
return "<pre>" + H(code) + "</pre>"
def ExportWebsite(vis, alg_functions, outdir="sortvis", rerender=False):
if not os.path.isdir(outdir):
os.makedirs(outdir)
os.chdir(outdir)
def import_alg(alg):
vis.run(alg)
if g_fail_count: sys.exit(1)
return AlgorithmResults(vis, alg, rerender=rerender)
algs = list(map(import_alg, alg_functions))
html = open("index.html", 'w', encoding="utf-8")
html.write(T("""<!DOCTYPE html>
<html><head>
<meta charset="utf-8">
<title>Sorting Algorithm Visualizations</title>
<style type="text/css">
p, h1, h2, div, footer, table * { font-family:"Fira Sans","Myriad Pro","Segoe UI","Noto Sans","DejaVu Sans",Verdana,Helvetica,sans-serif; }
body { background: #eee; }
table { border-collapse: collapse; }
th, td { border: 1px solid #666; padding: 0.15em 0.3em 0.15em 0.3em; margin: 0; text-align:right; }
tr { background: #ddd; }
th { background: #cde; }
.caption { text-align: center; }
.name { text-align: left; }
.scenario { text-align: center; }
.clickable { cursor: pointer; }
.clickable:hover { background-color: #def; }
video {
float: left; margin: 0 1em 0 0;
border-left: 1px solid black; border-top:1px solid black;
}
.alg {
margin: 1.5em 0 0 0; display: none;
}
.clear { clear: both; padding: 0.5em 0 0 0; }
pre {
font-family:"Fira Code",Inconsolata,Consolas,"Lucida Console",monospace;
background: #ddd; border: 1px solid #666; padding: 0.5em;
}
footer {
margin: 1em 0 0 0; padding: 0.5em 0 0 0;
border-top: 1px solid #ddd;
font-size: 80%; font-style: italic;
}
footer, footer a {
color: #ccc;
}
pre .k, pre .ow, pre .bp, pre .nb { font-weight: 500; color: #600; }
pre .c1 { color: #888; }
pre .n { color: #023; }
pre .nf { color: #a50; }
</style>
<script type="text/javascript">
var activeAlg = null;
function select(alg) {
if (activeAlg) {
document.getElementById("A_" + activeAlg).style.display = "none";
var vid = document.getElementById("V_" + activeAlg);
vid.pause();
vid.currentTime = 0;
}
document.getElementById("A_" + alg).style.display = "block";
var vid = document.getElementById("V_" + alg);
vid.currentTime = 0;
vid.play();
location.hash = "#" + alg;
activeAlg = alg;
}
function init() {
var hash = location.hash;
if (hash && (hash.substr(0, 1) == '#')) {
select(hash.substr(1));
}
}
</script>
</head><body onload="init()">
<h1>Sorting Algorithm Visualizations</h1>
<p>$[rows]$ sets of $[cols]$ numbers, with differing degrees of randomness
(from fully sorted, over fully random, to perfectly reversed), have been
sorted with $[count]$ different in-place sorting algorithms.</p>
<p>Click on one of the algorithms in the table to see a visualization
of the sorting process and the Python code that implements it.</p>
<noscript><p>(I'm afraid you need to enable JavaScript for that, though.)</p></noscript>
<table>
<tr>
<th rowspan="2" class="name">Algorithm</th>
<th colspan="3" class="caption">Complexity (compares + swaps)</th>
<th rowspan="2" class="scenario">best case<br>scenario</th>
<th rowspan="2" class="scenario">worst case<br>scenario</th>
</tr><tr>
<th>best case</th>
<th>average case</th>
<th>worst case</th>
</tr>
""").format(
cols = COLUMNS, rows = ROWS, count = len(algs),
))
for a in sorted(algs, key=lambda a: (-a.t_max, -a.t_avg, -a.t_min)):
html.write(T("""<tr class="clickable" onclick="select('$[name]$')">
<td class="name">$[name]$</td>
<td>$[min]$</td>
<td>$[avg]$</td>
<td>$[max]$</td>
<td class="scenario">$[best]$</td>
<td class="scenario">$[worst]$</td>
</tr>\n""").format(
name = a.name,
min = a.t_min,
avg = a.t_avg,
max = a.t_max,
best = a.s_min,
worst = a.s_max,
))
html.write('</table>\n')
for a in algs:
html.write(T("""<div id="A_$[name]$" class="alg">
<video id="V_$[name]$" src="$[video]$" width="$[width]$" height="$[height]$"></video>
<h2>$[name]$</h2>
$[desc]$
<div class="clear">$[src]$</div>
</div>\n""").format(
name = a.name,
video = a.video, width = a.width, height = a.height,
desc = "".join("<p>"+L(H(line))+"</p>" for line in a.doc),
src = C(a.src),
))
html.write("""
<footer>&copy; 2019 Martin J. Fiedler &bull;
<a href="https://gist.github.com/kajott/5a703e0f3f673da02d54ca95c09d1c29">source code</a>
&bull; Special thanks to Uwe for nerd-sniping me into making this &lt;3</footer>
<body></html>
""")
html.close()
###############################################################################
if __name__ == "__main__":
parser = argparse.ArgumentParser()
modes = parser.add_argument_group("processing modes")
modes.add_argument("-o", "--outdir", metavar="DIR", nargs='?', const=DEFAULT_OUTDIR,
help="output HTML page and videos into DIR (or '%(const)s' if DIR is omitted)")
modes.add_argument("-f", "--force", action='store_true',
help="always re-create all visualization video files when generating HTML")
modes.add_argument("-t", "--test", action='store_true',
help="test all algorithms")
modes.add_argument("-p", "--preview", metavar="ALG", nargs='?', const=True,
help="preview visualization of ALG (or the last algorithm if ALG is omitted)")
opts = parser.add_argument_group("visualization options")
opts.add_argument("-s", "--seed", metavar="X",
help="set random seed to X [can be any string; default: random]")
opts.add_argument("-r", "--rows", metavar="N", type=int, default=ROWS,
help="set number of rows to simulate [default: %(default)d]")
opts.add_argument("-c", "--cols", metavar="N", type=int, default=COLUMNS,
help="set number of values per row to simulate [default: %(default)d]")
opts.add_argument("-m", "--colormap", metavar="NAME", default=DEFAULT_COLORMAP,
help="set visualization color map [supported values: {}, default: %(default)s]" \
.format(" ".join(sorted(COLORMAPS.keys()))))
args = parser.parse_args()
if not(args.outdir) and not(args.test) and not(args.preview):
parser.print_help()
sys.exit(0)
if args.preview and not(args.preview is True):
preview_alg = [a for a in algorithms if a.__name__.lower() == args.preview.lower()]
if len(preview_alg) != 1:
parser.error("unrecognized algorithm '{}'".format(args.preview))
preview_alg = preview_alg.pop()
else:
preview_alg = algorithms[-1]
ROWS = args.rows
COLUMNS = args.cols
if args.seed:
random.seed(args.seed)
try:
COLORMAP = COLORMAPS[args.colormap]
except KeyError:
parser.error("unrecognized colormap '{}'".format(args.colormap))
vis = MultiSortVisualizer(GenerateVariableRandomness(COLUMNS, i / (ROWS - 1)) for i in range(ROWS))
if args.test:
for alg in algorithms:
vis.run(alg)
if g_fail_count: sys.exit(1)
vis.print_stats()
if args.outdir:
ExportWebsite(vis, algorithms, outdir=args.outdir, rerender=args.force)
if args.preview:
if preview_alg and (vis.alg_name != preview_alg.__name__):
vis.run(preview_alg)
if not g_fail_count:
vis.print_stats()
vis.video_show()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment