aboutsummaryrefslogtreecommitdiffstatshomepage
diff options
context:
space:
mode:
authorEgor Tensin <Egor.Tensin@gmail.com>2016-03-09 01:03:07 +0300
committerEgor Tensin <Egor.Tensin@gmail.com>2016-03-09 01:03:07 +0300
commit3b0e74b175f597a65b29fa38ba4883c0cd7632a0 (patch)
treef72192eae2505a413e98123fe43fa45d64c718bc
parentrefactoring (diff)
downloadsorting-algorithms-3b0e74b175f597a65b29fa38ba4883c0cd7632a0.tar.gz
sorting-algorithms-3b0e74b175f597a65b29fa38ba4883c0cd7632a0.zip
README update
-rw-r--r--README.md68
1 files changed, 46 insertions, 22 deletions
diff --git a/README.md b/README.md
index 28c3a8d..001ffe9 100644
--- a/README.md
+++ b/README.md
@@ -4,43 +4,67 @@ Gettting the hang out of sorting algorithms.
Hosted on [GitHub Pages](https://pages.github.com) at
https://egor-tensin.github.io/sorting_algorithms/.
-## Algorithm implementations
+## Algorithms
-Sorting algorithms are implemented in separate Python scripts.
-You can test each of the implemented algorithms by passing a sequence of
-integer numbers to the corresponding script.
+Each of the implemented sorting algorithms resides in a separate Python module.
+Currently the following algorithms are implemented:
-Currently the following sorting algorithms are implemented:
* bubble sort (`bubble_sort.py`),
* heapsort (`heapsort.py`),
* insertion sort (`insertion_sort.py`),
* merge sort (`merge_sort.py`),
-* selection sort (`selection_sort.py`),
-* quicksort (`quicksort.py`).
+* quicksort (`quicksort.py`),
+* selection sort (`selection_sort.py`).
-Some scripts actually implement more than one version of a sorting algorithm.
-For example, a quicksort is implemented in multiple versions depending on the
-choice of the pivot element.
+You can test each of the algorithms above by passing a sequence of integer
+numbers to the corresponding script:
+
+ > heapsort.py 5 3 4 1 2
+ [1, 2, 3, 4, 5]
+
+Some algorithms actually come in different variants.
+For example, the implementation of quicksort includes a number of versions
+depending on how the pivot element is chosen, be it the first, the second, the
+middle, the last or a random element of the sequence.
+
+ > quicksort.py 5 3 4 1 2
+ [1, 2, 3, 4, 5]
+ [1, 2, 3, 4, 5]
+ [1, 2, 3, 4, 5]
+ [1, 2, 3, 4, 5]
+ [1, 2, 3, 4, 5]
## Plots
-Running time of the implemented sorting algorithms is measured and plotted.
-The plots are stored in the `plots/` directory.
+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).
-Each algorithm is provided with three lists:
-* a list of sorted numbers,
-* a reversed list of sorted numbers,
-* and a list of numbers in random order.
+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.
-## Usage
+I've made the measurements for each of the implemented algorithms and put the
+plots to the `plots/` directory.
+Both the hardware & the software that were used to produce the plots are listed
+below.
-### Prerequisites
+ | |
+-------------- | ------------------------------------------------------- |
+**CPU** | [Intel Atom N2800](http://ark.intel.com/products/58917) |
+**OS** | Windows 7 Professional Service Pack 1 |
+**Python** | 3.4.1 |
+**matplotlib** | 1.4.0 |
-To use this software, you need to be able to run Python 3 scripts.
+Each of the implemented algorithms was provided with three input sequences:
+* a list of *n* consecutive numbers sorted in ascending order ("sorted" input),
+* ... in descending order ("reversed" input),
+* ... in random order ("randomized" input).
-To plot a sorting algorithm, use `plot.py` (on Windows, you can also use
-`plot.bat`, which simply calls `plot.py` three times, providing the sorting
-algorithm with sorted, reversed, and randomized inputs).
+You can generate the plots using `plot.py`.
+Consult the output of `plot.py -h` to learn how to use the script.
## Licensing