diff options
Diffstat (limited to 'README.md')
| -rw-r--r-- | README.md | 68 |
1 files changed, 46 insertions, 22 deletions
@@ -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 |