initial commit

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',
+                '&hellip; 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)',
+                '&hellip; second element&hellip;', 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)',
+                '&hellip; middle element&hellip;', 0, 200,
+                100, 'O(<var>n</var> log <var>n</var>)'),
+  new Algorithm('quick_last', 'Quicksort (last element as pivot)',
+                '&hellip; last element&hellip;', 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)',
+                '&hellip; random element&hellip;', 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>