From e556d45c040054abc3cd92589d9c0364d8ac54fe Mon Sep 17 00:00:00 2001 From: Egor Tensin Date: Tue, 30 May 2017 03:48:01 +0300 Subject: "Plots" is now the landing page --- index.html | 237 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 222 insertions(+), 15 deletions(-) (limited to 'index.html') diff --git a/index.html b/index.html index eb52770..f48380d 100644 --- a/index.html +++ b/index.html @@ -1,22 +1,229 @@ --- -title: Main page -layout: sidebar +title: Plots +layout: plain groups: - navbar -navbar_link:  Main page +navbar_link:  Plots +custom_css: + - plots.css +input_kind: + - best + - average + - worst +plots: + - codename: bubble_sort + brief_name: Bubble sort + display_name: Bubble sort + min_length: 0 + max_length: 200 + iterations: 100 + complexity: + best: O(n) + average: O(n2) + worst: O(n2) + - codename: bubble_sort_optimized + brief_name: "… \"optimized\"" + display_name: "\"Optimized\" bubble sort" + min_length: 0 + max_length: 200 + iterations: 100 + complexity: + best: O(n) + average: O(n2) + worst: O(n2) + - codename: heapsort + brief_name: Heapsort + display_name: Heapsort + min_length: 0 + max_length: 200 + iterations: 100 + complexity: O(n log n) + - codename: insertion_sort + brief_name: Insertion sort + display_name: Insertion sort + min_length: 0 + max_length: 200 + iterations: 100 + complexity: + best: O(n) + average: O(n2) + worst: O(n2) + - codename: merge_sort + brief_name: Merge sort + display_name: Merge sort + min_length: 0 + max_length: 200 + iterations: 100 + complexity: O(n log n) + - codename: quicksort_first + brief_name: Quicksort (first element as pivot) + display_name: Quicksort (first element as pivot) + min_length: 0 + max_length: 200 + iterations: 100 + complexity: + best: O(n2) + average: O(n log n) + worst: O(n2) + - codename: quicksort_second + brief_name: "… second element…" + display_name: Quicksort (second element as pivot) + min_length: 0 + max_length: 200 + iterations: 100 + complexity: + best: O(n2) + average: O(n log n) + worst: O(n2) + - codename: quicksort_middle + brief_name: "… middle element…" + display_name: Quicksort (middle element as pivot) + min_length: 0 + max_length: 200 + iterations: 100 + complexity: O(n log n) + - codename: quicksort_last + brief_name: "… last element…" + display_name: Quicksort (last element as pivot) + min_length: 0 + max_length: 200 + iterations: 100 + complexity: + best: O(n2) + average: O(n log n) + worst: O(n2) + - codename: quicksort_random + brief_name: "… random element…" + display_name: Quicksort (random element as pivot) + min_length: 0 + max_length: 200 + iterations: 100 + complexity: O(n log n) + - codename: selection_sort + brief_name: Selection sort + display_name: Selection sort + min_length: 0 + max_length: 200 + iterations: 100 + complexity: O(n2) --- -{% if site.posts.size == 0 %} -

Sorry, no posts have been added yet.

-

But I've made quite a few plots which you might want to check out.

-
-{% else %} - {% for post in paginator.posts %} -

{{ post.title }}

-

Posted on {{ post.date | date_to_long_string }}

-

{{ post.excerpt }}

-
+

{{ page.title }}

+ +
+
+

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

+ + + + + + + + + + + + + + + + + +
CPUIntel Core i3-5005U
OSWindows 8.1
Python3.5.1
matplotlib1.5.1
+
+
+ +{% 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 {{ site.github.repository_url }} for more details.

+ +

Each of the implemented algorithms was provided with three input +sequences:

+
    +
  • a list of n consecutive numbers sorted in ascending order,
    • +
  • … in descending order,
    • +
  • … in random order.
    • +
+

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

+ + + + + + + + + {% for input_kind in page.input_kind %} + + {% endfor %} + + + +{% for algorithm in page.plots %} + + + {% for input_kind in page.input_kind %} + {% if algorithm.complexity[input_kind] %} + {% assign complexity = algorithm.complexity[input_kind] %} + {% else %} + {% assign complexity = algorithm.complexity %} + {% endif %} + {% endfor %} -
- {% include common/pagination.html %} +
+{% endfor %} + +
AlgorithmComplexity
{{ input_kind | capitalize }}
{{ algorithm.brief_name }}{{ complexity }}
+
+ +{% for algorithm in page.plots %} + +

{{ algorithm.display_name }}

+
+ {% for input_kind in page.input_kind %} + {% if algorithm.iterations[input_kind] %} + {% assign iterations = algorithm.iterations[input_kind] %} + {% else %} + {% assign iterations = algorithm.iterations %} + {% endif %} + {% if algorithm.complexity[input_kind] %} + {% assign complexity = algorithm.complexity[input_kind] %} + {% else %} + {% assign complexity = algorithm.complexity %} + {% endif %} + {% capture stem %}{{ algorithm.codename }}_{{ iterations }}_{{ input_kind }}_{{ algorithm.min_length }}_{{ algorithm.max_length }}{% endcapture %} +
+
+ + {{ algorithm.display_name | escape }}, {{ iterations }} iterations, {{ input_kind }} case + +
+ {{ algorithm.display_name }}
+ {{ input_kind | capitalize }} case, {{ complexity }} +
+
+
+ {% endfor %} +
+{% endfor %} + +{% else %} +

Sorry, not plots have been added yet.

+
{% endif %} -- cgit v1.2.3