diff options
56 files changed, 721 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..57510a2 --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +_site/ @@ -0,0 +1,4 @@ +source 'https://rubygems.org' +gem 'github-pages' +gem 'rouge' +gem 'wdm', '~> 0.1.0' if Gem.win_platform? diff --git a/Gemfile.lock b/Gemfile.lock new file mode 100644 index 0000000..10366ff --- /dev/null +++ b/Gemfile.lock @@ -0,0 +1,119 @@ +GEM + remote: https://rubygems.org/ + specs: + RedCloth (4.2.9-x86-mingw32) + activesupport (4.1.4) + i18n (~> 0.6, >= 0.6.9) + json (~> 1.7, >= 1.7.7) + minitest (~> 5.1) + thread_safe (~> 0.1) + tzinfo (~> 1.1) + blankslate (2.1.2.4) + celluloid (0.15.2) + timers (~> 1.1.0) + classifier (1.3.4) + fast-stemmer (>= 1.0.0) + coffee-script (2.3.0) + coffee-script-source + execjs + coffee-script-source (1.7.1) + colorator (0.1) + execjs (2.2.1) + fast-stemmer (1.0.2) + ffi (1.9.3-x86-mingw32) + gemoji (2.1.0) + github-pages (22) + RedCloth (= 4.2.9) + jekyll (= 2.2.0) + jekyll-coffeescript (= 1.0.0) + jekyll-mentions (= 0.1.3) + jekyll-redirect-from (= 0.4.0) + jekyll-sass-converter (= 1.2.0) + jekyll-sitemap (= 0.5.1) + jemoji (= 0.3.0) + kramdown (= 1.3.1) + liquid (= 2.6.1) + maruku (= 0.7.0) + pygments.rb (= 0.6.0) + rdiscount (= 2.1.7) + redcarpet (= 3.1.2) + html-pipeline (1.9.0) + activesupport (>= 2) + nokogiri (~> 1.4) + i18n (0.6.11) + jekyll (2.2.0) + classifier (~> 1.3) + colorator (~> 0.1) + jekyll-coffeescript (~> 1.0) + jekyll-gist (~> 1.0) + jekyll-paginate (~> 1.0) + jekyll-sass-converter (~> 1.0) + jekyll-watch (~> 1.0) + kramdown (~> 1.3) + liquid (~> 2.6.1) + mercenary (~> 0.3.3) + pygments.rb (~> 0.6.0) + redcarpet (~> 3.1) + safe_yaml (~> 1.0) + toml (~> 0.1.0) + jekyll-coffeescript (1.0.0) + coffee-script (~> 2.2) + jekyll-gist (1.1.0) + jekyll-mentions (0.1.3) + html-pipeline (~> 1.9.0) + jekyll (~> 2.0) + jekyll-paginate (1.0.0) + jekyll-redirect-from (0.4.0) + jekyll (~> 2.0) + jekyll-sass-converter (1.2.0) + sass (~> 3.2) + jekyll-sitemap (0.5.1) + jekyll-watch (1.1.0) + listen (~> 2.7) + jemoji (0.3.0) + gemoji (~> 2.0) + html-pipeline (~> 1.9) + jekyll (~> 2.0) + json (1.8.1) + kramdown (1.3.1) + liquid (2.6.1) + listen (2.7.9) + celluloid (>= 0.15.2) + rb-fsevent (>= 0.9.3) + rb-inotify (>= 0.9) + maruku (0.7.0) + mercenary (0.3.4) + mini_portile (0.6.0) + minitest (5.4.0) + nokogiri (1.6.3.1-x86-mingw32) + mini_portile (= 0.6.0) + parslet (1.5.0) + blankslate (~> 2.0) + posix-spawn (0.3.9) + pygments.rb (0.6.0) + posix-spawn (~> 0.3.6) + yajl-ruby (~> 1.1.0) + rb-fsevent (0.9.4) + rb-inotify (0.9.5) + ffi (>= 0.5.0) + rdiscount (2.1.7) + redcarpet (3.1.2) + rouge (1.8.0) + safe_yaml (1.0.3) + sass (3.3.14) + thread_safe (0.3.4) + timers (1.1.0) + toml (0.1.1) + parslet (~> 1.5.0) + tzinfo (1.2.2) + thread_safe (~> 0.1) + wdm (0.1.0) + yajl-ruby (1.1.0-x86-mingw32) + +PLATFORMS + x86-mingw32 + +DEPENDENCIES + github-pages + rouge + wdm (~> 0.1.0) diff --git a/LICENSE.txt b/LICENSE.txt new file mode 100644 index 0000000..fbbdd68 --- /dev/null +++ b/LICENSE.txt @@ -0,0 +1,21 @@ +The MIT License (MIT) + +Copyright (c) 2015 Egor Tensin <Egor.Tensin@gmail.com> + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. diff --git a/README.md b/README.md new file mode 100644 index 0000000..ec9d0f2 --- /dev/null +++ b/README.md @@ -0,0 +1,68 @@ +# Sorting algorithms + +Getting the hang out of sorting algorithms. +Hosted on [GitHub Pages](https://pages.github.com) at https://egor-tensin.github.io/sorting_algorithms/. + +## Installation + +[Jekyll](http://jekyllrb.com/) is used to build a set of static HTML pages from a collection of templates and resources. +Jekyll doesn't support Windows, however at the moment of writing one can get it to work using the excellent tutorial at http://jekyll-windows.juthilo.com/. + +I'm using [Bundler](http://bundler.io/) to set up a development environment. +After the `bundler` gem is installed, project dependencies can be installed by running + + bundle install + +in the project's root directory. + +## Development + +To run a local web server, run + + bundle exec jekyll serve --baseurl '' --watch --drafts + +from the project's root directory. +You can then review your changes at http://localhost:4000/. + +To exclude the comments section, include the `_config-exclude-comments.yml` configuration file using + + bundle exec jekyll serve --baseurl '' --watch --drafts --config _config.yml,_config-exclude-comments.yml + +Please note that the support for `--watch`ing for modification on Windows is kind of iffy at the moment of writing. +One possible workaround is to add `--force_polling` to `jekyll`s options: + + bundle exec jekyll serve --baseurl '' --watch --force_polling --drafts --config _config.yml,_config-exclude-comments.yml + +It might still not work though, so you might end up having to re-run `jekyll` manually. +For details, refer to http://jekyll-windows.juthilo.com/4-wdm-gem/. + +I'm also using the `rouge` gem for syntax highlighting during development instead of [Pygments](http://pygments.org/). +The reason for this was that Pygments required Python 2 to be installed, while I'm trying to switch to Python 3 completely. +The downside is that at the moment of writing GitHub Pages only supported Pygments, so I had to include a separate configuration file `_config-rouge.yml` during development. + +To sum up, on Linux use + + bundle exec jekyll serve \ + --baseurl '' \ + --watch \ + --drafts \ + --config _config.yml,_config-exclude-comments.yml,_config-rouge.yml + +and on Windows (hoping for the best) use + + bundle exec jekyll serve ^ + --baseurl '' ^ + --watch --force_polling ^ + --drafts ^ + --config _config.yml,_config-exclude-comments.yml,_config-rouge.yml + +to run a local web server. + +## Licensing + +This project, including all of the files and their contents, is licensed under the terms of the MIT License. +See LICENSE.txt for details. + +This website is build upon the Twitter Bootstrap framework, which is also MIT Licensed and copyright 2015 Twitter. + +A MIT Licensed CSS style sheet from https://github.com/mojombo/tpw/blob/master/css/syntax.css created by Tom Preston-Werner is used for syntax highlighting. diff --git a/_config-exclude-comments.yml b/_config-exclude-comments.yml new file mode 100644 index 0000000..7f0c6d2 --- /dev/null +++ b/_config-exclude-comments.yml @@ -0,0 +1 @@ +include_comments: false diff --git a/_config-rouge.yml b/_config-rouge.yml new file mode 100644 index 0000000..c8ec22c --- /dev/null +++ b/_config-rouge.yml @@ -0,0 +1 @@ +highlighter: rouge diff --git a/_config.yml b/_config.yml new file mode 100644 index 0000000..9dab5e6 --- /dev/null +++ b/_config.yml @@ -0,0 +1,3 @@ +baseurl: /sorting_algorithms +paginate: 10 +include_comments: true diff --git a/_includes/footer.html b/_includes/footer.html new file mode 100644 index 0000000..3bfc5a2 --- /dev/null +++ b/_includes/footer.html @@ -0,0 +1,23 @@ + </div> + </div> + <div class="block"> + <footer class="navbar-default"> + <div class="container"> + <div style="display: table; width: 100%;"> + <div style="display: table-row;"> + <div style="display: table-cell;"> + <div class="text-mutex"><small>This project is licensed under the terms of the MIT License. See <a href="https://github.com/egor-tensin/egor-tensin.github.io#licensing">Licensing</a> for details.</small></div> + </div> + <div style="display: table-cell;"> + <div class="text-right text-muted"><small>This blog was last updated on: {{ site.time | date_to_long_string }}.</small></div> + </div> + </div> + </div> + </div> + </footer> + </div> + </div> + <script src="//code.jquery.com/jquery-1.11.0.js"></script> + <script src="//maxcdn.bootstrapcdn.com/bootstrap/3.2.0/js/bootstrap.js"></script> + </body> +</html> diff --git a/_includes/header.html b/_includes/header.html new file mode 100644 index 0000000..67f0bb3 --- /dev/null +++ b/_includes/header.html @@ -0,0 +1,28 @@ +<!DOCTYPE html> +<html lang="en"> + <head> + <meta charset="utf-8"> + <meta http-equiv="X-UA-Compatible" content="IE=edge"> + <meta name="viewport" content="width=device-width, initial-scale=1.0"> + <title>{{ page.title }}</title> + <link rel="stylesheet" href="//maxcdn.bootstrapcdn.com/bootstrap/3.2.0/css/bootstrap.css"> + + <link rel="stylesheet" href="{{ site.baseurl }}/css/syntax.css"> + <link rel="stylesheet" href="{{ site.baseurl }}/css/footer.css"> + <link rel="stylesheet" href="{{ site.baseurl }}/css/plots.css"> + + <!-- HTML5 shim and Respond.js IE8 support of HTML5 elements and media queries --> + <!--[if lt IE 9]> + <script src="//oss.maxcdn.com/html5shiv/3.7.2/html5shiv.js"></script> + <script src="//oss.maxcdn.com/respond/1.4.2/respond.js"></script> + <![endif]--> + </head> + <body> + <script src="{{ site.baseurl }}/js/common.js"></script> + + <div class="wrapper"> + <div class="block"> + {% include navbar.html %} + </div> + <div class="block push"> + <div class="container"> diff --git a/_includes/links.html b/_includes/links.html new file mode 100644 index 0000000..70e643b --- /dev/null +++ b/_includes/links.html @@ -0,0 +1,11 @@ +{% for node in page_list %} + {% if group == null or group == node.group %} + {% if page.url == node.url %} + <li class="active"><a href="{{ site.baseurl }}{{ node.url }}" class="active">{{ node.title }}</a></li> + {% else %} + <li><a href="{{ site.baseurl }}{{ node.url }}">{{ node.title }}</a></li> + {% endif %} + {% endif %} +{% endfor %} +{% assign page_list = nil %} +{% assign group = nil %} diff --git a/_includes/navbar.html b/_includes/navbar.html new file mode 100644 index 0000000..f052baa --- /dev/null +++ b/_includes/navbar.html @@ -0,0 +1,20 @@ +<nav class="navbar navbar-default navbar-static-top" role="navigation"> + <div class="container"> + <div class="navbar-header"> + <button type="button" class="navbar-toggle" data-toggle="collapse" data-target=".navbar-collapse"> + <span class="sr-only">Toggle navigation</span> + <span class="icon-bar"></span> + <span class="icon-bar"></span> + <span class="icon-bar"></span> + </button> + <a class="navbar-brand" href="/">Egor Tensin</a> + </div> + <div class="navbar-collapse collapse"> + <ul class="nav navbar-nav"> + {% assign page_list = site.pages %} + {% assign group = 'navigation' %} + {% include links.html %} + </ul> + </div> + </div> +</nav> diff --git a/_includes/pagination.html b/_includes/pagination.html new file mode 100644 index 0000000..aa2f034 --- /dev/null +++ b/_includes/pagination.html @@ -0,0 +1,30 @@ +{% if site.posts.size != 0 %} +<ul class="pagination"> + {% if paginator.previous_page %} + {% if paginator.previous_page == 1 %} + <li><a href="{{ site.baseurl }}/"><span class="glyphicon glyphicon-chevron-left"></span> Prev</a></li> + {% else %} + <li><a href="{{ site.baseurl }}/page{{ paginator.previous_page }}"><span class="glyphicon glyphicon-chevron-left"></span> Prev</a></li> + {% endif %} + {% else %} + <li class="disabled"><a href="#"><span class="glyphicon glyphicon-chevron-left"></span> Prev</a></li> + {% endif %} + {% if paginator.page == 1 %} + <li class="active"><a href="{{ site.baseurl }}/">1</a></li> + {% else %} + <li><a href="{{ site.baseurl }}/">1</a></li> + {% endif %} + {% for count in (2..paginator.total_pages) %} + {% if count == paginator.page %} + <li class="active"><a href="{{ site.baseurl }}/page{{ count }}">{{ count }}</a></li> + {% else %} + <li><a href="{{ site.baseurl }}/page{{ count }}">{{ count }}</a></li> + {% endif %} + {% endfor %} + {% if paginator.next_page %} + <li><a href="{{ site.baseurl }}/page{{ paginator.next_page }}">Next <span class="glyphicon glyphicon-chevron-right"></span></a></li> + {% else %} + <li class="disabled"><a href="#">Next <span class="glyphicon glyphicon-chevron-right"></span></a></li> + {% endif %} +</ul> +{% endif %} diff --git a/_includes/sidebar.html b/_includes/sidebar.html new file mode 100644 index 0000000..cb5b538 --- /dev/null +++ b/_includes/sidebar.html @@ -0,0 +1,16 @@ +<h4>About the project</h4> +<p>Getting the hang out of the sorting algorithms. Feel free to contribute or contact me.</p> +<div class="list-group" style="max-width: 400px;"> + <a class="list-group-item" href="//github.com/egor-tensin/sorting_algorithms"><span class="glyphicon glyphicon-home"></span> GitHub repository</a> + <a class="list-group-item" href="mailto:Egor.Tensin@gmail.com"><span class="glyphicon glyphicon-envelope"></span> Egor.Tensin@gmail.com</a> +</div> +<h4>Latest posts</h4> +{% if site.posts.size == 0 %} + <p>Sorry, there're no posts yet.</p> +{% else %} + <div class="list-group"> + {% for post in site.posts limit: 5 %} + <a class="list-group-item" href="{{ site.baseurl }}{{ post.url }}"><span class="badge"><span class="glyphicon glyphicon-time"></span> {{ post.date | date_to_string }}</span><span class="glyphicon glyphicon-file"></span> {{ post.title }}</a> + {% endfor %} + </div> +{% endif %} diff --git a/_layouts/plots.html b/_layouts/plots.html new file mode 100644 index 0000000..9a6a620 --- /dev/null +++ b/_layouts/plots.html @@ -0,0 +1,7 @@ +{% include header.html %} +<div class="row"> + <div class="col-md-12"> + {{ content }} + </div> +</div> +{% include footer.html %} diff --git a/_layouts/post.html b/_layouts/post.html new file mode 100644 index 0000000..4b05318 --- /dev/null +++ b/_layouts/post.html @@ -0,0 +1,14 @@ +{% include header.html %} +<div class="row"> + <div class="col-md-8"> + <h1>{{ page.title }}</h1> + <p class="text-muted"><span class="glyphicon glyphicon-time"></span> Posted on {{ page.date | date_to_long_string }}</p> + {{ content }} + <hr/> + {% include comments.html %} + </div> + <div class="col-md-4"> + {% include sidebar.html %} + </div> +</div> +{% include footer.html %} diff --git a/_layouts/posts.html b/_layouts/posts.html new file mode 100644 index 0000000..920cbd9 --- /dev/null +++ b/_layouts/posts.html @@ -0,0 +1,10 @@ +{% include header.html %} +<div class="row"> + <div class="col-md-8"> + {{ content }} + </div> + <div class="col-md-4"> + {% include sidebar.html %} + </div> +</div> +{% include footer.html %} diff --git a/css/footer.css b/css/footer.css new file mode 100644 index 0000000..f8896b5 --- /dev/null +++ b/css/footer.css @@ -0,0 +1,22 @@ +html, body { + height: 100%; + width: 100%; +} +.wrapper { + height: 100%; + width: 100%; + display: table; +} +.block { + display: table-row; + height: 1px; +} +.push { + height: auto; +} +footer { + margin-top: 20px; + padding: 15px 0 15px; + border-width: 1px 0; + border-style: solid; +} diff --git a/css/plots.css b/css/plots.css new file mode 100644 index 0000000..ad4f244 --- /dev/null +++ b/css/plots.css @@ -0,0 +1,3 @@ +#plots a.thumbnail { + margin-bottom: 0; +} diff --git a/css/syntax.css b/css/syntax.css new file mode 100644 index 0000000..dc60655 --- /dev/null +++ b/css/syntax.css @@ -0,0 +1,61 @@ +.hll { background-color: #ffffcc } +.c { color: #999988; font-style: italic } /* Comment */ +.err { color: #a61717; background-color: #e3d2d2 } /* Error */ +.k { color: #000000; font-weight: bold } /* Keyword */ +.o { color: #000000; font-weight: bold } /* Operator */ +.cm { color: #999988; font-style: italic } /* Comment.Multiline */ +.cp { color: #999999; font-weight: bold; font-style: italic } /* Comment.Preproc */ +.c1 { color: #999988; font-style: italic } /* Comment.Single */ +.cs { color: #999999; font-weight: bold; font-style: italic } /* Comment.Special */ +.gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */ +.ge { color: #000000; font-style: italic } /* Generic.Emph */ +.gr { color: #aa0000 } /* Generic.Error */ +.gh { color: #999999 } /* Generic.Heading */ +.gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */ +.go { color: #888888 } /* Generic.Output */ +.gp { color: #555555 } /* Generic.Prompt */ +.gs { font-weight: bold } /* Generic.Strong */ +.gu { color: #aaaaaa } /* Generic.Subheading */ +.gt { color: #aa0000 } /* Generic.Traceback */ +.kc { color: #000000; font-weight: bold } /* Keyword.Constant */ +.kd { color: #000000; font-weight: bold } /* Keyword.Declaration */ +.kn { color: #000000; font-weight: bold } /* Keyword.Namespace */ +.kp { color: #000000; font-weight: bold } /* Keyword.Pseudo */ +.kr { color: #000000; font-weight: bold } /* Keyword.Reserved */ +.kt { color: #445588; font-weight: bold } /* Keyword.Type */ +.m { color: #009999 } /* Literal.Number */ +.s { color: #d01040 } /* Literal.String */ +.na { color: #008080 } /* Name.Attribute */ +.nb { color: #0086B3 } /* Name.Builtin */ +.nc { color: #445588; font-weight: bold } /* Name.Class */ +.no { color: #008080 } /* Name.Constant */ +.nd { color: #3c5d5d; font-weight: bold } /* Name.Decorator */ +.ni { color: #800080 } /* Name.Entity */ +.ne { color: #990000; font-weight: bold } /* Name.Exception */ +.nf { color: #990000; font-weight: bold } /* Name.Function */ +.nl { color: #990000; font-weight: bold } /* Name.Label */ +.nn { color: #555555 } /* Name.Namespace */ +.nt { color: #000080 } /* Name.Tag */ +.nv { color: #008080 } /* Name.Variable */ +.ow { color: #000000; font-weight: bold } /* Operator.Word */ +.w { color: #bbbbbb } /* Text.Whitespace */ +.mf { color: #009999 } /* Literal.Number.Float */ +.mh { color: #009999 } /* Literal.Number.Hex */ +.mi { color: #009999 } /* Literal.Number.Integer */ +.mo { color: #009999 } /* Literal.Number.Oct */ +.sb { color: #d01040 } /* Literal.String.Backtick */ +.sc { color: #d01040 } /* Literal.String.Char */ +.sd { color: #d01040 } /* Literal.String.Doc */ +.s2 { color: #d01040 } /* Literal.String.Double */ +.se { color: #d01040 } /* Literal.String.Escape */ +.sh { color: #d01040 } /* Literal.String.Heredoc */ +.si { color: #d01040 } /* Literal.String.Interpol */ +.sx { color: #d01040 } /* Literal.String.Other */ +.sr { color: #009926 } /* Literal.String.Regex */ +.s1 { color: #d01040 } /* Literal.String.Single */ +.ss { color: #990073 } /* Literal.String.Symbol */ +.bp { color: #999999 } /* Name.Builtin.Pseudo */ +.vc { color: #008080 } /* Name.Variable.Class */ +.vg { color: #008080 } /* Name.Variable.Global */ +.vi { color: #008080 } /* Name.Variable.Instance */ +.il { color: #009999 } /* Literal.Number.Integer.Long */ diff --git a/img/previews/bubble_1000_sorted_0_200.jpg b/img/previews/bubble_1000_sorted_0_200.jpg Binary files differnew file mode 100644 index 0000000..a7b37fd --- /dev/null +++ b/img/previews/bubble_1000_sorted_0_200.jpg diff --git a/img/previews/bubble_100_randomized_0_200.jpg b/img/previews/bubble_100_randomized_0_200.jpg Binary files differnew file mode 100644 index 0000000..15620a5 --- /dev/null +++ b/img/previews/bubble_100_randomized_0_200.jpg diff --git a/img/previews/bubble_100_reversed_0_200.jpg b/img/previews/bubble_100_reversed_0_200.jpg Binary files differnew file mode 100644 index 0000000..5faff6f --- /dev/null +++ b/img/previews/bubble_100_reversed_0_200.jpg diff --git a/img/previews/bubble_optimized_1000_sorted_0_200.jpg b/img/previews/bubble_optimized_1000_sorted_0_200.jpg Binary files differnew file mode 100644 index 0000000..3f4deef --- /dev/null +++ b/img/previews/bubble_optimized_1000_sorted_0_200.jpg diff --git a/img/previews/bubble_optimized_100_randomized_0_200.jpg b/img/previews/bubble_optimized_100_randomized_0_200.jpg Binary files differnew file mode 100644 index 0000000..62fc92d --- /dev/null +++ b/img/previews/bubble_optimized_100_randomized_0_200.jpg diff --git a/img/previews/bubble_optimized_100_reversed_0_200.jpg b/img/previews/bubble_optimized_100_reversed_0_200.jpg Binary files differnew file mode 100644 index 0000000..9b8e7ff --- /dev/null +++ b/img/previews/bubble_optimized_100_reversed_0_200.jpg diff --git a/img/previews/heap_100_randomized_0_200.jpg b/img/previews/heap_100_randomized_0_200.jpg Binary files differnew file mode 100644 index 0000000..a775a56 --- /dev/null +++ b/img/previews/heap_100_randomized_0_200.jpg diff --git a/img/previews/heap_100_reversed_0_200.jpg b/img/previews/heap_100_reversed_0_200.jpg Binary files differnew file mode 100644 index 0000000..3777bf8 --- /dev/null +++ b/img/previews/heap_100_reversed_0_200.jpg diff --git a/img/previews/heap_100_sorted_0_200.jpg b/img/previews/heap_100_sorted_0_200.jpg Binary files differnew file mode 100644 index 0000000..bf27f1c --- /dev/null +++ b/img/previews/heap_100_sorted_0_200.jpg diff --git a/img/previews/insertion_1000_sorted_0_200.jpg b/img/previews/insertion_1000_sorted_0_200.jpg Binary files differnew file mode 100644 index 0000000..8edb4be --- /dev/null +++ b/img/previews/insertion_1000_sorted_0_200.jpg diff --git a/img/previews/insertion_100_randomized_0_200.jpg b/img/previews/insertion_100_randomized_0_200.jpg Binary files differnew file mode 100644 index 0000000..8de27a4 --- /dev/null +++ b/img/previews/insertion_100_randomized_0_200.jpg diff --git a/img/previews/insertion_100_reversed_0_200.jpg b/img/previews/insertion_100_reversed_0_200.jpg Binary files differnew file mode 100644 index 0000000..309901c --- /dev/null +++ b/img/previews/insertion_100_reversed_0_200.jpg diff --git a/img/previews/merge_100_randomized_0_200.jpg b/img/previews/merge_100_randomized_0_200.jpg Binary files differnew file mode 100644 index 0000000..5b5f20f --- /dev/null +++ b/img/previews/merge_100_randomized_0_200.jpg diff --git a/img/previews/merge_100_reversed_0_200.jpg b/img/previews/merge_100_reversed_0_200.jpg Binary files differnew file mode 100644 index 0000000..7c8c1b7 --- /dev/null +++ b/img/previews/merge_100_reversed_0_200.jpg diff --git a/img/previews/merge_100_sorted_0_200.jpg b/img/previews/merge_100_sorted_0_200.jpg Binary files differnew file mode 100644 index 0000000..8d38a25 --- /dev/null +++ b/img/previews/merge_100_sorted_0_200.jpg diff --git a/img/previews/quick_first_100_randomized_0_200.jpg b/img/previews/quick_first_100_randomized_0_200.jpg Binary files differnew file mode 100644 index 0000000..c622207 --- /dev/null +++ b/img/previews/quick_first_100_randomized_0_200.jpg diff --git a/img/previews/quick_first_100_reversed_0_200.jpg b/img/previews/quick_first_100_reversed_0_200.jpg Binary files differnew file mode 100644 index 0000000..5dfe1e1 --- /dev/null +++ b/img/previews/quick_first_100_reversed_0_200.jpg diff --git a/img/previews/quick_first_100_sorted_0_200.jpg b/img/previews/quick_first_100_sorted_0_200.jpg Binary files differnew file mode 100644 index 0000000..af7a423 --- /dev/null +++ b/img/previews/quick_first_100_sorted_0_200.jpg diff --git a/img/previews/quick_last_100_randomized_0_200.jpg b/img/previews/quick_last_100_randomized_0_200.jpg Binary files differnew file mode 100644 index 0000000..cf51c98 --- /dev/null +++ b/img/previews/quick_last_100_randomized_0_200.jpg diff --git a/img/previews/quick_last_100_reversed_0_200.jpg b/img/previews/quick_last_100_reversed_0_200.jpg Binary files differnew file mode 100644 index 0000000..720c9c0 --- /dev/null +++ b/img/previews/quick_last_100_reversed_0_200.jpg diff --git a/img/previews/quick_last_100_sorted_0_200.jpg b/img/previews/quick_last_100_sorted_0_200.jpg Binary files differnew file mode 100644 index 0000000..94e0286 --- /dev/null +++ b/img/previews/quick_last_100_sorted_0_200.jpg diff --git a/img/previews/quick_middle_100_randomized_0_200.jpg b/img/previews/quick_middle_100_randomized_0_200.jpg Binary files differnew file mode 100644 index 0000000..78e0804 --- /dev/null +++ b/img/previews/quick_middle_100_randomized_0_200.jpg diff --git a/img/previews/quick_middle_100_reversed_0_200.jpg b/img/previews/quick_middle_100_reversed_0_200.jpg Binary files differnew file mode 100644 index 0000000..b9e8547 --- /dev/null +++ b/img/previews/quick_middle_100_reversed_0_200.jpg diff --git a/img/previews/quick_middle_100_sorted_0_200.jpg b/img/previews/quick_middle_100_sorted_0_200.jpg Binary files differnew file mode 100644 index 0000000..4018807 --- /dev/null +++ b/img/previews/quick_middle_100_sorted_0_200.jpg diff --git a/img/previews/quick_random_100_randomized_0_200.jpg b/img/previews/quick_random_100_randomized_0_200.jpg Binary files differnew file mode 100644 index 0000000..9de66f5 --- /dev/null +++ b/img/previews/quick_random_100_randomized_0_200.jpg diff --git a/img/previews/quick_random_100_reversed_0_200.jpg b/img/previews/quick_random_100_reversed_0_200.jpg Binary files differnew file mode 100644 index 0000000..a5e4d12 --- /dev/null +++ b/img/previews/quick_random_100_reversed_0_200.jpg diff --git a/img/previews/quick_random_100_sorted_0_200.jpg b/img/previews/quick_random_100_sorted_0_200.jpg Binary files differnew file mode 100644 index 0000000..b6fc410 --- /dev/null +++ b/img/previews/quick_random_100_sorted_0_200.jpg diff --git a/img/previews/quick_second_100_randomized_0_200.jpg b/img/previews/quick_second_100_randomized_0_200.jpg Binary files differnew file mode 100644 index 0000000..3b511cd --- /dev/null +++ b/img/previews/quick_second_100_randomized_0_200.jpg diff --git a/img/previews/quick_second_100_reversed_0_200.jpg b/img/previews/quick_second_100_reversed_0_200.jpg Binary files differnew file mode 100644 index 0000000..41cd75b --- /dev/null +++ b/img/previews/quick_second_100_reversed_0_200.jpg diff --git a/img/previews/quick_second_100_sorted_0_200.jpg b/img/previews/quick_second_100_sorted_0_200.jpg Binary files differnew file mode 100644 index 0000000..f46e68f --- /dev/null +++ b/img/previews/quick_second_100_sorted_0_200.jpg diff --git a/img/previews/selection_100_randomized_0_200.jpg b/img/previews/selection_100_randomized_0_200.jpg Binary files differnew file mode 100644 index 0000000..b0e4628 --- /dev/null +++ b/img/previews/selection_100_randomized_0_200.jpg diff --git a/img/previews/selection_100_reversed_0_200.jpg b/img/previews/selection_100_reversed_0_200.jpg Binary files differnew file mode 100644 index 0000000..1cfbffc --- /dev/null +++ b/img/previews/selection_100_reversed_0_200.jpg diff --git a/img/previews/selection_100_sorted_0_200.jpg b/img/previews/selection_100_sorted_0_200.jpg Binary files differnew file mode 100644 index 0000000..e6d3e50 --- /dev/null +++ b/img/previews/selection_100_sorted_0_200.jpg diff --git a/index.html b/index.html new file mode 100644 index 0000000..778ee5e --- /dev/null +++ b/index.html @@ -0,0 +1,20 @@ +--- +title: Posts +layout: posts +group: "navigation" +--- +{% if site.posts.size == 0 %} + <h3>Sorry, there're no posts yet.</h3> + <p class="text-muted">But I've made quite a few <a href="{{ site.baseurl }}/plots.html">plots</a> which you might want to check out.</p> + <hr/> +{% else %} + {% for post in paginator.posts %} + <h2>{{ post.title }}</h2> + <p class="text-muted"><span class="glyphicon glyphicon-time"></span> Posted on {{ post.date | date_to_long_string }}</p> + <a class="btn btn-primary" href="{{ site.baseurl }}{{ post.url }}">Read More <span class="glyphicon glyphicon-chevron-right"></span></a> + <hr/> + {% endfor %} + <div class="text-center"> + {% include pagination.html %} + </div> +{% endif %} diff --git a/js/common.js b/js/common.js new file mode 100644 index 0000000..07268f4 --- /dev/null +++ b/js/common.js @@ -0,0 +1,23 @@ +// Copyright 2015 Egor Tensin <Egor.Tensin@gmail.com> +// This file is licensed under the terms of the MIT License. +// See LICENSE.txt for details. + +if (!String.prototype.format) { + String.prototype.format = function() { + var str = this.toString(); + if (!arguments.length) + return str; + switch (typeof arguments[0]) { + case 'string': + case 'number': + var args = arguments; + break; + default: + var args = arguments[0]; + break; + } + for (var arg in args) + str = str.replace(new RegExp('\\{' + arg + '\\}', 'gi'), args[arg]); + return str; + } +} diff --git a/plots.html b/plots.html new file mode 100644 index 0000000..7ff245f --- /dev/null +++ b/plots.html @@ -0,0 +1,215 @@ +--- +title: Plots +layout: plots +group: "navigation" +--- +<h1>Plots</h1> +<p><strong>Disclaimer:</strong> for info about the platform used to generate the plots below, visit the <a href="{{ site.baseurl }}/about.html">About</a> section.</p> +<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 = '//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', + '… 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)', + '… second element…', 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)', + '… middle element…', 0, 200, + 100, 'O(<var>n</var> log <var>n</var>)'), + new Algorithm('quick_last', 'Quicksort (last element as pivot)', + '… last element…', 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)', + '… random element…', 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> |
