A Python package with the most common sorting algorithms.
All algorithms are based on the book: Introduction to algorithms by Cormen.
algo is based on the repo: Algorithms from course TDT4120
| Algorithm | WC | AC/E | Stable? |
|---|---|---|---|
| INSERTION-Sort | Θ(n^2) | Θ(n^2) | Yes |
| MERGE-Sort | Θ(n lg n) | Θ(n lg n) | Yes |
| Binary search | Θ(lg n) | Θ(lg n) | - |
| Quicksort | Θ(n^2) | Θ(n lg n)* | Usually not*** |
| Randomized-Quicksort | O(n lg n) | O(n lg n) | Usually not*** |
| Counting-Sort | Θ(n+k) | Θ(n+k) | Yes |
| Radix-Sort | Θ(d(n+k)) | Θ(d(n+k)) | Yes**** |
| Bucket-Sort | Θ(n^2) | Θ(n)** | Yes |
| Heap-Sort | O(n lg n) | O(n lg n) | No |
*Expected, Randomized-Quicksort
**Average-case
***Most quicksort implementations are not stable, though stable implementations do exist.
****LSD requires stability, MSD does not
https://jesperbry.github.io/algo/
pip install algo
# -*- coding: utf-8 -*-
import algo.algo as algo
algo.help()
A = [27, 4, 15, 9, 110, 0, 13, 25, 1, 17, 802, 66, 25, 45, 97, 9]
algo.mergeSort(A, 0, len(A)-1)
print(A)Result:
-- List of function arguments --
A = list/array
p = start index (0)
r = end index (len(A) - 1)
B = min value of A (min(A))
radix = Base of the number system or max value of A
v = search value (bisect)
All algorithms are based on the book; Introduction to algorithms by Cormen
[0, 1, 4, 9, 9, 13, 15, 17, 25, 25, 27, 45, 66, 97, 110, 802]
# List all methods:
help(algo) or dir(algo)