This project is a quick review of:
- Python's 3.12 new features
- Python's native unit testing module
unittest - Python's type hint system
- Measuring the running time of a function
- Six basic sorting algorithms
This project also serves as the notes of said review. You'll find some theory in the comments, docstrings, and readme.
The six basic sorting algorithms reviewed:
- Selection Sort
- Bubble Sort
- Insertion Sort
- Merge Sort
- Heap Sort
- Quick Sort
Only one version of each algorithm is chosen and implemented.
Installation is required to run this program. Once you clone this repository, install the dependencies with:
python -m pip install -r requirements.txtThe main functionality of the program is to measure and compare the running time of different sorting algorithms. To run using default values use:
python main.pyIf you want to provide your own values, the program accepts two command line arguments: the size of the list to be sorted, and the number of times that the measurement will be repeated and accumulated:
python main.py 20 50The above will sort arrays of size 20, 50 different times, and the results added together.
Note that mypy might not yet support type aliases, but pyright already does.
python -m pyright .
python -m mypy .python -m black .
python -m flake8 .This project uses the unittest native Python module to write and run unit testing.
To run tests use either:
python sort_test.py
python -m unittest sort_test.py| algorithm | time complexity (best avg worst) | space complexity (total aux) |
|---|---|---|
| selection sort | O(n^2) O(n^2) O(n^2) | O(n) O(1) |
| bubble sort | O(n) O(n^2) O(n^2) | O(n) O(1) |
| insertion sort | O(n) O(n^2) O(n^2) | O(n) O(1) |
| merge sort | O(n log n) O(n log n) O(n log n) | O(n) O(n) |
| heap sort | O(n log n) O(n log n) O(n log n) | O(n) O(1) |
| quick sort | O(n log n) O(n log n) O(n^2) | O(n) O(n) |
Found a bug, typo, or mistake? Want to refactor, optimize, or improve something in this repository? Send a pull request! Pull requests are always welcome!
There's no need to create an issue. Just use a descriptive commit message and I'll format it adequately when accepting the pull request. Contributing here is as simple as commiting your changes and sending a pull request!
- https://docs.python.org/3/whatsnew/3.12.html
- https://realpython.com/python312-new-features/
- https://blog.jetbrains.com/pycharm/2023/11/python-3-12/
- https://www.bigocheatsheet.com/
- https://rosettacode.org/wiki/Sorting
- https://rosettacode.org/wiki/Category:Sorting_Algorithms
- https://en.wikipedia.org/wiki/selection_sort
- https://rosettacode.org/wiki/Sorting_algorithms/Selection_sort
- https://www.programiz.com/dsa/selection-sort
- https://en.wikipedia.org/wiki/bubble_sort
- https://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort
- https://www.programiz.com/dsa/bubble-sort
- https://en.wikipedia.org/wiki/insertion_sort
- https://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort
- https://www.programiz.com/dsa/insertion-sort
- https://en.wikipedia.org/wiki/merge_sort
- https://rosettacode.org/wiki/Sorting_algorithms/Merge_sort
- https://www.programiz.com/dsa/merge-sort
- https://en.wikipedia.org/wiki/heap_sort
- https://rosettacode.org/wiki/Sorting_algorithms/Heapsort
- https://www.programiz.com/dsa/heap-sort
- https://en.wikipedia.org/wiki/quick_sort
- https://rosettacode.org/wiki/Sorting_algorithms/Quicksort
- https://www.programiz.com/dsa/quick-sort