path: root/plots.html

---
title: Plots
layout: plots
group: "navigation"
---
<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>