path: root/plots.html

---
title: Plots
layout: plots
groups:
  - navbar
navbar_link: <span class="glyphicon glyphicon-th-large"></span>&nbsp;Plots
---
<h1>Plots</h1>

<p>The platform under which the plots were produced was:</p>

<table class="table table-bordered reasonable-width">
  <tr>
    <th>CPU</th>
    <td><a href="http://ark.intel.com/products/58917">Intel Atom N2800</a></td>
  </tr>
  <tr>
    <th>OS</th>
    <td>Windows 7 Professional Service Pack 1</td>
  </tr>
  <tr>
    <th>Python</th>
    <td>3.4.1</td>
  </tr>
  <tr>
    <th>matplotlib</th>
    <td>1.4.0</td>
  </tr>
</table>

<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 = 'https://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>