All The Algorithms On Python

So yeah, just for educational purposes, I am trying to create by myself all the algorithms I can find (just reading their papers, without seeing the code). Since these are for demonstration purposes only, I advice to don't use them. There are many implementations of sorts in the Python standard library that are much better for performance reasons.

Sort Algorithms

Quicksort

From Wikipedia: Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order.

Properties:

• Worst case performance O(n^2)
• Best case performance O(n log n) or O(n) with three-way partition
• Average case performance O(n log n)

View it in action here

There are several partition schemes, currently I have implemented these ones:

• Lomuto partition scheme
• Hoare partition scheme

Merge Sort

From Wikipedia: In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

Properties

• Worst case performance O(n log n)
• Best case performance O(n)
• Average case performance O(n)

View it in action here

There are several implementations, currently I have implemented these ones:

• Binary Merge Sort

Bubble Sort

From Wikipedia: Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Properties

• Worst case performance O(n^2)
• Best case performance O(n)
• Average case performance O(n^2)

View it in action here

There are several implementations, currently I have implemented these ones:

• Basic Bubble Sort
• Optimized Bubble Sort (Soon)

Special Thanks

First, I want to say thank you to The Algorithms, because exploring GitHub, I found their repo, where they were doing something similar to this repo (you can check their repo here.

Also, I want to thank you to TopCoders, since I am providing the animations of the algorithms from their website.

And finally (but not less important), to all the informative websites where I am reading about those algorithms:

• Wikipedia