Top 6 the most important sorting algorithms in the world

Ho-ho-ho!

Today we are going to take a look at THE MOST IMPORTANT SORTING ALGORITHMS IN THE WORLD!!!!1 You know, it is really hard to underestimate sorting algorithms. They are that much important as the sorting hat in Hogwarts!

So, we will start from the famous BogoSort!

1. Bogosort

The algorithm consists of two steps:

1. Shuffle the array
2. Check if this permutation is sorted

So, I always imagine that this algorithm like a clown who put all the permutations in the box. Shake the box and take one of them. If the array is not sorted he is making over emotional ugly face, haha.

Let’s code and estimate the proposed idea.

import random

def bogosort(a):
    array = a
    
    while not is_sorted(array):
        array = random.shuffle(a)
    return array

def is_sorted(a):
    for i in range(0, len(a) - 1):
        if a[i + 1] <= a[i]:
            return False
    return True

This algorithm does not have an upper bound. In the worst case we can always shuffle the array without getting the right sorted permutation.

The middle case is much more interesting: we can approach the estimation from the probabilities theory. There are n! permutations of an array on size n. Among those permutations only one permutation is sorted, therefore the probability to take the sorted array is 1/n!. On expectation, that means that to see the sorted array n! of items will occur on average. Therefore, on average we will see n! permutations and we need additional n iterations to check if this permutation is sorted. The algorithm works for O(n * n!) on average.

The lower bound is the simplest case. The first permutation is already sorted therefore we need only n iterations to check it. The lower bound is O(n).

2. Bozosort

Bozosort is an “improved” version of the previous algorithm Bogosort. Was called after the famous clown as the algorithm is super simple and even child can understand it.

The algorithm:

1. We need to take a random pair in the array and shuffle it
2. Check if the resulted array is sorted otherwise return to the step one

Sounds simple! Let’s implement the code:

import random

def bozosort(a):
    array = a
    
    while not is_sorted(array):
        l = random.uniform(0, len(array))
        r = random.uniform(0, len(array))

        t = array[l]
        array[r] = array[l]
        array[l] = t

    return array

def is_sorted(a):
    for i in range(0, len(a) - 1):
        if a[i + 1] <= a[i]:
            return False
    return True

The complexity estimations are pretty much similar to BogoSort.

3. Sleep Sort

Sleep sort is also a quite classic algorithm of sorting. The idea is pretty simple we need to go through the array elements. For every element we need to start a new thread and block them for the same amount of time as the element’s value.

import _thread
from time import sleep

def tick(i):
    sleep(i)
    print(i)

def sleep_sort(a):
    for i in a:
        arg_tuple = (i,)
        _thread.start_new_thread(tick, arg_tuple)

The algorithm works exact the same amount of time as the maximum element of the array.

4. Gnome Sort

The algorithm has been called based on a concept of a Garden Gnome sorting his flowers pots. We can divide the algorithm into two steps:

1. A gnome is looking at 2 pots at the time. If the next pot is smaller than the previous one then they swap them and now are looking at the previous two pots (the previous pair)
2. If the next pot is bigger than the current one then they switch their attention to the next pair

The algorithm looks similar to the another famous algorithm Bubble Sort. Unfortunately, this algorithm is out of the current article’s scope.

Before start implementing something we need to discuss the boundary cases: if there are no more pairs then they stop sort the pots; empty arrays are already sorted.

def gnomesort(a):
    index = 1

    while index < len(a):
        if index == 0:
            index += 1
        elif a[index] < a[index - 1]:
            (a[index], a[index - 1]) = (a[index - 1], a[index])
            index -= 1
        else:
            index += 1

    return a

Sorted!!1!

5. Stalin Sort

This is a pretty fast algorithm it requires only linear amount of iterations. We need to iterate through the array and evict all the elements that breaks the sorting order (smaller than the previous elements).

def stalinsort(a):
    sorted = []

    sorted.append(a[0])

    for i in range(1, len(a)):
        if a[i] >= sorted[len(sorted) - 1]:
            sorted.append(a[i])

    return sorted

6. God Sort

There are n!-1 arrays that contains exact the same elements as ours but in different order. The probability to create exact the same array as ours is 1/n! (if the values are different). The idea of the algorithm is to accept that God have created this algorithm for a reason. No need to sort the array at all.

def godsort(a):
    return a

That was top six the most important algorithms in the world.

Happy Fool April subs!