--- title: Plots layout: plots groups: - navbar navbar_link: <span class="glyphicon glyphicon-th-large"></span> Plots custom_css: plots.css plot_kinds: - sorted - randomized - reversed plots: - codename: bubble brief_name: Bubble sort display_name: Bubble sort min_length: 0 max_length: 200 repetitions: sorted: 1000 randomized: 100 reversed: 100 complexity: sorted: O(<var>n</var>) randomized: O(<var>n</var><sup>2</sup>) reversed: O(<var>n</var><sup>2</sup>) - codename: bubble_optimized brief_name: "… \"optimized\"" display_name: "\"Optimized\" bubble sort" min_length: 0 max_length: 200 repetitions: sorted: 1000 randomized: 100 reversed: 100 complexity: sorted: O(<var>n</var>) randomized: O(<var>n</var><sup>2</sup>) reversed: O(<var>n</var><sup>2</sup>) - codename: heap brief_name: Heapsort display_name: Heapsort min_length: 0 max_length: 200 repetitions: 100 complexity: O(<var>n</var> log <var>n</var>) - codename: insertion brief_name: Insertion sort display_name: Insertion sort min_length: 0 max_length: 200 repetitions: sorted: 1000 randomized: 100 reversed: 100 complexity: sorted: O(<var>n</var>) randomized: O(<var>n</var><sup>2</sup>) reversed: O(<var>n</var><sup>2</sup>) - codename: merge brief_name: Merge sort display_name: Merge sort min_length: 0 max_length: 200 repetitions: 100 complexity: O(<var>n</var> log <var>n</var>) - codename: quick_first brief_name: Quicksort (first element as pivot) display_name: Quicksort (first element as pivot) min_length: 0 max_length: 200 repetitions: 100 complexity: 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>) - codename: quick_second brief_name: "… second element…" display_name: Quicksort (second element as pivot) min_length: 0 max_length: 200 repetitions: 100 complexity: 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>) - codename: quick_middle brief_name: "… middle element…" display_name: Quicksort (middle element as pivot) min_length: 0 max_length: 200 repetitions: 100 complexity: O(<var>n</var> log <var>n</var>) - codename: quick_last brief_name: "… last element…" display_name: Quicksort (last element as pivot) min_length: 0 max_length: 200 repetitions: 100 complexity: 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>) - codename: quick_random brief_name: "… random element…" display_name: Quicksort (random element as pivot) min_length: 0 max_length: 200 repetitions: 100 complexity: O(<var>n</var> log <var>n</var>) - codename: selection brief_name: Selection sort display_name: Selection sort min_length: 0 max_length: 200 repetitions: 100 complexity: O(<var>n</var><sup>2</sup>) --- <h1>Plots</h1> <div class="row"> <div class="col-xs-12 col-sm-9 col-md-6"> <p class="text-muted">The goals of this "project" include a) familiarizing myself with a few sorting algorithms by examining their (possibly, simplified) implementations and b) studying the way algorithm's running time changes in relation to the length of its input (a.k.a. identifying its time complexity).</p> <p class="text-muted">A simple way to visualize the way algorithm's running time changes would be to make appropriate measurements and plot them on a nice graph. The results of course are highly dependent on the hardware used, while the graph's look depends on the software used for rendering.</p> <p class="text-muted">Both the hardware & the software that were used to produce the plots are listed below.</p> <table class="table table-bordered"> <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> </div> {% if page.plots and page.plots != empty %} <div class="row"> <div class="col-xs-12 col-sm-10 col-md-8"> <p>The table & plots below are just an attempt to nicely lay out the data generated using the code from the project repository's <code>master</code> branch. Visit <a href="https://github.com/egor-tensin/sorting_algorithms/">https://github.com/egor-tensin/sorting_algorithms/</a> for more details.</p> <p>In short, each of the implemented algorithms was provided with three input sequences:</p> <ul> <li>a list of n consecutive numbers sorted in ascending order ("sorted" input),</li> <li>… in descending order ("reversed" input),</li> <li>… in random order ("randomized" input).</li> </ul> <p>Use the table below to quickly navigate to the plots for the corresponding algorithm.</p> <table class="table table-bordered table-hover"> <thead> <tr> <th class="text-center" rowspan="2">Algorithm</th> <th class="text-center" colspan="{{ page.plot_kinds.size }}">Complexity</th> </tr> <tr> {% for kind in page.plot_kinds %} <th class="text-center">{{ kind }}</th> {% endfor %} </tr> </thead> <tbody> {% for algorithm in page.plots %} <tr> <td><a href="#plots_{{ algorithm.codename }}">{{ algorithm.brief_name }}</a></td> {% for kind in page.plot_kinds %} <td>{% if algorithm.complexity[kind] %}{{ algorithm.complexity[kind] }}{% else %}{{ algorithm.complexity }}{% endif %}</td> {% endfor %} </tr> {% endfor %} </tbody> </table> </div> </div> {% for algorithm in page.plots %} <a id="plots_{{ algorithm.codename }}"></a> <h3>{{ algorithm.display_name }}</h3> <div class="row"> {% for kind in page.plot_kinds %} {% if algorithm.repetitions[kind] %} {% assign repetitions = algorithm.repetitions[kind] %} {% else %} {% assign repetitions = algorithm.repetitions %} {% endif %} {% capture stem %}{{ algorithm.codename }}_{{ repetitions }}_{{ kind }}_{{ algorithm.min_length }}_{{ algorithm.max_length }}{% endcapture %} <div class="col-xs-12 col-sm-6 col-md-4"> <div class="thumbnail"> <a class="thumbnail" href="{{ site.baseurl }}/img/plots/full_size/{{ stem }}.png"> <img class="img-responsive" src="{{ site.baseurl }}/img/plots/previews/{{ stem }}.jpg"/> </a> <div class="caption"> <strong>{{ algorithm.display_name }}</strong><br/> <strong>Input:</strong> {{ kind }}<br/> <strong>Complexity:</strong> {% if algorithm.complexity[kind] %}{{ algorithm.complexity[kind] }}{% else %}{{ algorithm.complexity }}{% endif %}<br/> </div> </div> </div> {% endfor %} </div> {% endfor %} {% else %} <h3>Sorry, not plots have been added yet.</h3> <hr/> {% endif %}