Ashwin Sharma P
Ashwin Sharma P

Ashwin Sharma P

Say no to these algorithms in practice

Say no to these algorithms in practice

Ashwin Sharma P's photo
Ashwin Sharma P

Published on Dec 6, 2020

3 min read

So here we will be discussing briefly Bogosort and Bogobogosort, which are two inefficient algorithms.

NOTE: These are just for educational purposes. Never use these in real-life applications. ☠☠

Bogosort:

Bogosort first checks whether the list is already sorted. It checks over the entire list by checking if the adjacent pair is correctly ordered. If it is not in order, then it shuffles all the list in random order and again starts over. This process goes on till the list is sorted.

When we get into the time complexity of this algorithm, we get to know why it is an inefficient algorithm.

The logic of Bogsort is as follows:

import random
from random import shuffle
def sequence_sorted(data):
    return (data[i]<=data[i+1] for i in range (len(data)-1))

def bogosort(data):
    while not sequence_sorted(data):
        shuffle(data)
    return data

The best-case time complexity is achieved when the list or sequence is already sorted. Best case complexity is O(n).

The average case complexity is O(n*n!)=O((n+1)!).

The worst case is when the list takes forever to get sorted. We have no guarantee that this algorithm will return a sorted output as it randomly shuffles all the entries each time. The worst-case time complexity is O(∞).

Bogobogosort:

We also have an algorithm called Bogobogosort, which checks the first 2 elements of the list and bogosorts them. In the next round, it checks the first 3 elements and bogosorts them and this process continues till it reaches the end. If it finds that the list is not in order, it starts the process again by bogosorting the first 2 elements.

The average time complexity of this algorithm is O(N! 1! 2! 3! .... * N!).

Hope you learnt some new concepts. Thank you for reading.😊

 
Share this

Impressum

Feel free to share your feedback and suggestions 😊

Connect with me 👇👇

💙Twitter

💼LinkedIn Page

BuyMeACoffee