--- title: Plots layout: plots groups: - navbar navbar_link:  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(n) randomized: O(n2) reversed: O(n2) - 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(n) randomized: O(n2) reversed: O(n2) - codename: heap brief_name: Heapsort display_name: Heapsort min_length: 0 max_length: 200 repetitions: 100 complexity: O(n log n) - 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(n) randomized: O(n2) reversed: O(n2) - codename: merge brief_name: Merge sort display_name: Merge sort min_length: 0 max_length: 200 repetitions: 100 complexity: O(n log n) - 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(n2) randomized: O(n log n) reversed: O(n2) - 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(n2) randomized: O(n log n) reversed: O(n2) - codename: quick_middle brief_name: "… middle element…" display_name: Quicksort (middle element as pivot) min_length: 0 max_length: 200 repetitions: 100 complexity: O(n log n) - 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(n2) randomized: O(n log n) reversed: O(n2) - codename: quick_random brief_name: "… random element…" display_name: Quicksort (random element as pivot) min_length: 0 max_length: 200 repetitions: 100 complexity: O(n log n) - codename: selection brief_name: Selection sort display_name: Selection sort min_length: 0 max_length: 200 repetitions: 100 complexity: O(n2) ---

Plots

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).

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.

Both the hardware & the software that were used to produce the plots are listed below.

CPU Intel Atom N2800
OS Windows 7 Professional Service Pack 1
Python 3.4.1
matplotlib 1.4.0
{% if page.plots and page.plots != empty %}

The table & plots below are just an attempt to nicely lay out the data generated using the code from the project repository's master branch. Visit https://github.com/egor-tensin/sorting_algorithms/ for more details.

In short, each of the implemented algorithms was provided with three input sequences:

Use the table below to quickly navigate to the plots for the corresponding algorithm.

{% for kind in page.plot_kinds %} {% endfor %} {% for algorithm in page.plots %} {% for kind in page.plot_kinds %} {% endfor %} {% endfor %}
Algorithm Complexity
{{ kind }}
{{ algorithm.brief_name }}{% if algorithm.complexity[kind] %}{{ algorithm.complexity[kind] }}{% else %}{{ algorithm.complexity }}{% endif %}
{% for algorithm in page.plots %}

{{ algorithm.display_name }}

{% 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 %}
{{ algorithm.display_name }}
Input: {{ kind }}
Complexity: {% if algorithm.complexity[kind] %}{{ algorithm.complexity[kind] }}{% else %}{{ algorithm.complexity }}{% endif %}
{% endfor %}
{% endfor %} {% else %}

Sorry, not plots have been added yet.


{% endif %}