diff options
Diffstat (limited to '')
| -rw-r--r-- | plots.html | 215 |
1 files changed, 215 insertions, 0 deletions
diff --git a/plots.html b/plots.html new file mode 100644 index 0000000..7ff245f --- /dev/null +++ b/plots.html @@ -0,0 +1,215 @@ +--- +title: Plots +layout: plots +group: "navigation" +--- +<h1>Plots</h1> +<p><strong>Disclaimer:</strong> for info about the platform used to generate the plots below, visit the <a href="{{ site.baseurl }}/about.html">About</a> section.</p> +<div id="plots"> + <p class="text-muted">Javascript-generated plot table is supposed to appear here.</p> +</div> +<script type="text/javascript"> +var userName = 'egor-tensin'; +var repoName = 'sorting_algorithms'; + +var plotsUrl = '//github.com/{userName}/{repoName}/raw/master/plots/'.format({ + userName: userName, + repoName: repoName +}); + +var previewsPath = '{{ site.baseurl }}/img/previews/'; + +function Algorithm(codename, name, briefName, + minLength, maxLength, + repetitions, complexity) { + this.codename = codename; + this.name = name; + this.briefName = briefName; + this.minLength = minLength; + this.maxLength = maxLength; + this.repetitions = repetitions; + this.complexity = complexity; +} + +Algorithm.prototype.getRepetitions = function(input) { + switch (typeof this.repetitions) { + case 'number': + return this.repetitions; + case 'object': + return this.repetitions[input]; + } +} + +Algorithm.prototype.getComplexity = function(input) { + switch (typeof this.complexity) { + case 'string': + return this.complexity; + case 'object': + return this.complexity[input]; + } +} + +Algorithm.prototype.buildPlotStem = function(input) { + return '{codename}_{repetitions}_{input}_{minLength}_{maxLength}'.format({ + codename: this.codename, + input: input, + repetitions: this.getRepetitions(input), + minLength: this.minLength, + maxLength: this.maxLength + }); +} + +Algorithm.prototype.buildPlotFileName = function(input) { + return this.buildPlotStem(input) + '.png'; +} + +Algorithm.prototype.buildPreviewFileName = function(input) { + return this.buildPlotStem(input) + '.jpg'; +} + +Algorithm.prototype.buildPlotUrl = function(input) { + return plotsUrl + this.buildPlotFileName(input); +} + +Algorithm.prototype.buildPreviewPath = function(input) { + return previewsPath + this.buildPreviewFileName(input); +} + +Algorithm.prototype.buildPlotCaptionHtml = function(input) { + return '\ +<div class="caption">\n\ +<strong>{name}</strong><br/>\n\ +<strong>Input:</strong> {input}<br/>\n\ +<strong>Complexity:</strong> {complexity}<br/>\n\ +</div>\n'.format({name: this.name, + input: input, + complexity: this.getComplexity(input)}); +} + +Algorithm.prototype.buildPlotHtml = function(input) { + return '\ +<div class="col-xs-12 col-sm-6 col-md-4">\n\ + <div class="thumbnail">\ + <a class="thumbnail" href="{plotUrl}">\n\ + <img class="img-responsive" src="{previewPath}"/>\n\ + </a>\n\ + {captionHtml}\n\ + </div>\n\ +</div>\n'.format({previewPath: this.buildPreviewPath(input), + plotUrl: this.buildPlotUrl(input), + captionHtml: this.buildPlotCaptionHtml(input)}); +} + +var algorithms = [ + new Algorithm('bubble', 'Bubble sort', 'Bubble sort', 0, 200, + {sorted: 1000, randomized: 100, reversed: 100}, + {sorted: 'O(<var>n</var>)', + randomized: 'O(<var>n</var><sup>2</sup>)', + reversed: 'O(<var>n</var><sup>2</sup>)'}), + new Algorithm('bubble_optimized', 'Optimized bubble sort', + '… optimized', 0, 200, + {sorted: 1000, randomized: 100, reversed: 100}, + {sorted: 'O(<var>n</var>)', + randomized: 'O(<var>n</var><sup>2</sup>)', + reversed: 'O(<var>n</var><sup>2</sup>)'}), + new Algorithm('heap', 'Heapsort', 'Heapsort', 0, 200, + 100, 'O(<var>n</var> log <var>n</var>)'), + new Algorithm('insertion', 'Insertion sort', 'Insertion sort', 0, 200, + {sorted: 1000, randomized: 100, reversed: 100}, + {sorted: 'O(<var>n</var>)', + randomized: 'O(<var>n</var><sup>2</sup>)', + reversed: 'O(<var>n</var><sup>2</sup>)'}), + new Algorithm('merge', 'Merge sort', 'Merge sort', 0, 200, + 100, 'O(<var>n</var> log <var>n</var>)'), + new Algorithm('quick_first', 'Quicksort (first element as pivot)', + 'Quicksort (first element as pivot)', 0, 200, + 100, {sorted: 'O(<var>n</var><sup>2</sup>)', + randomized: 'O(<var>n</var> log <var>n</var>)', + reversed: 'O(<var>n</var><sup>2</sup>)'}), + new Algorithm('quick_second', 'Quicksort (second element as pivot)', + '… second element…', 0, 200, + 100, {sorted: 'O(<var>n</var><sup>2</sup>)', + randomized: 'O(<var>n</var> log <var>n</var>)', + reversed: 'O(<var>n</var><sup>2</sup>)'}), + new Algorithm('quick_middle', 'Quicksort (middle element as pivot)', + '… middle element…', 0, 200, + 100, 'O(<var>n</var> log <var>n</var>)'), + new Algorithm('quick_last', 'Quicksort (last element as pivot)', + '… last element…', 0, 200, + 100, {sorted: 'O(<var>n</var><sup>2</sup>)', + randomized: 'O(<var>n</var> log <var>n</var>)', + reversed: 'O(<var>n</var><sup>2</sup>)'}), + new Algorithm('quick_random', 'Quicksort (random element as pivot)', + '… random element…', 0, 200, + 100, 'O(<var>n</var> log <var>n</var>)'), + new Algorithm('selection', 'Selection sort', 'Selection sort', 0, 200, + 100, 'O(<var>n</var><sup>2</sup>)') +]; + +function buildPlotsAlgorithm(algorithm) { + return '\ +<a id="plots_{codename}"></a>\n\ +<h3>{name}</h3>\n\ +<div class="row">\n\ +{sorted}\ +{randomized}\ +{reversed}\n\ +</div>\n'.format({name: algorithm.name, + codename: algorithm.codename, + sorted: algorithm.buildPlotHtml('sorted'), + randomized: algorithm.buildPlotHtml('randomized'), + reversed: algorithm.buildPlotHtml('reversed')}); +} + +function buildPlotsAllAlgorithms() { + var html = ''; + for (var i = 0; i < algorithms.length; ++i) { + html += buildPlotsAlgorithm(algorithms[i]); + } + return html; +} + +function buildComplexityTableRow(algorithm) { + return '\ +<tr>\n\ + <td><a href="#plots_{codename}">{briefName}</a></td>\n\ + <td>{sorted}</td>\n\ + <td>{randomized}</td>\n\ + <td>{reversed}</td>\n\ +</tr>\n'.format({codename: algorithm.codename, + briefName: algorithm.briefName, + sorted: algorithm.getComplexity('sorted'), + randomized: algorithm.getComplexity('randomized'), + reversed: algorithm.getComplexity('reversed')}); +} + +function buildComplexityTable() { + var html = '\ +<div class="row">\n\ + <div class="col-xs-12 col-sm-10 col-md-8">\n\ + <table id="complexity_table" class="table table-bordered table-hover">\n\ + <thead>\n\ + <tr>\n\ + <th class="text-center" rowspan="2">Algorithm</th>\n\ + <th class="text-center" colspan="3">Complexity</th>\n\ + </tr>\n\ + <tr>\n\ + <th class="text-center">sorted</th>\n\ + <th class="text-center">randomized</th>\n\ + <th class="text-center">reversed</th>\n\ + </tr>\n\ + </thead>\n\ + <tbody>\n'; + for (var i = 0; i < algorithms.length; ++i) { + html += buildComplexityTableRow(algorithms[i]); + } + html += '\ + </tbody>\n\ + </table>\n\ + </div>\n\ +</div>\n'; + return html; +} + +document.getElementById('plots').innerHTML = buildComplexityTable() + buildPlotsAllAlgorithms(); +</script> |