On Leave

When quick sort is too quick

When you hear of sorting algorithm, which one pops up first in your head? Quick sort? Merge sort? Bubble Sort?

Back in university, one of my professors always told the class that quick sort is like the Apple of sorting world because they are very good at marketing. By naming itself “quick,” people associate them with being the fastest sorting algorithm even when merge sort is actually faster for average cases.

Setting that false advertising aside, I am pretty sure you have heard of those algorithms. Let’s move on to more recent ones.

Python uses Timsort, a hybrid algorithm derived from merge sort and insertion sort. The name Timsort comes from the author, Tim Peter, who created it back in 2002 for Python.

For specifically positive numbers, we have Radix sort. It is a combination of counting sort and black magic to manage a complexity of O(d*(n+b)), where d is the number of digits in the list, n is the number of elements in the list, and b is the base used which is normally base 10.

More recently in 2020, a new algorithm called Quadsort emerges. It is a 1500 lines implementation of a hyper-optimized merge sort that is capable of beating Timsort in multiple cases. The author is kind enough to provide visualizations and benchmark for us mere mortals.

You might think we will dive deep into the 1500 lines for Quadsort, but you will be mistaken. We are here to take a look into sorting algorithms that are more… interesting.

esoteric · ɛsəˈtɛrɪk
very unusual and understood or liked by only a small number of people, especially those with special knowledge (source)

Complexity: O(n * n!)

The classic sorting algorithm that has many aliases, among which are Permutation Sort, Stupid Sort, Slow Sort, and Monkey Sort.

Main idea of this algorithm is to randomly shuffle the elements inside the list until it is sorted. Thanks to Python’s built-in random module, we can implement it in just a few lines. Definitely much easier compared to implementing quick sort or merge sort.

This means there are n! possible combinations, and because for every iteration we will spend O(n) time to shuffle the list and another O(n) time to check if the list is sorted, we end up with O(n * n!) for the complexity.

Complexity: O(my God)

An advanced variation of the Bogosort. Bogobogosort thinks that the original Bogosort algorithm was far too efficient, that’s why it introduces extra steps to make the algorithm more…

Continue reading: https://towardsdatascience.com/esoteric-sort-algorithms-and-how-to-implement-them-in-python-96c663fa6ae5?source=rss—-7f60cf5620c9—4

Source: towardsdatascience.com