Last active
August 8, 2019 21:25
-
-
Save kajott/5a703e0f3f673da02d54ca95c09d1c29 to your computer and use it in GitHub Desktop.
visualization of various in-place sorting algorithms
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/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("&", "&").replace("<", "<").replace(">", ">") | |
| 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>© 2019 Martin J. Fiedler • | |
| <a href="https://gist.github.com/kajott/5a703e0f3f673da02d54ca95c09d1c29">source code</a> | |
| • Special thanks to Uwe for nerd-sniping me into making this <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