Friday, May 22, 2020

Why Bogo Sort and Cocktail Shaker Sort algorithms are not so popular ?



In this blog, we are going to discuss and learn about two of the easiest sorting algorithms available that are Bogo Sort and Cocktail Sort.
Things you'll learn or get to know after reading this article.
  • What is Bogo Sort and What is Cocktail Shaker Sort
  • How to implement these two sorting algorithms
  • Time Complexity of these sorting algorithms
  • More in-depth knowledge of some uncommon sorting algorithms
The primary language that I'll use to explain these sorting algorithms is C++.
Let's start with the explanation of these algorithms one by one.

1. Bogo Sort

Bogo sort is referred to as permutation sort, stupid sort, slow sort, shotgun sort, or monkey sort, in fact, it is one of the most ineffective algorithms present out there. The approach followed by this algorithm is to generate permutations of its input until a sorted permutation is generated or only until it finds one that is sorted.


For example, we have 10 cards numbered one to 10 arranged in the form of the deck and we want to sort it using Bogo Sort, we will continuously throw the cards up in the air and then form a deck by picking up cards randomly and repeat this until we get the deck of cards sorted.


The pseudo-code for the BogoSort is 

while not isInorder(deck);
    shuffle deck;
 
To explain this in simple words, let's consider an example.

We want to sort an array ( 1, 6, 7, 5, 2 )
on First Shuffle -  7, 1, 6, 5, 2 
on Second Shuffle - 7,6, 2, 5, 1 
.
.
.
.
on nth Shuffle - 1, 2, 5, 6, 7

The code for the BogoSort Algorithm is
Time Complexity
Worst Case: O(∞)(Since no upper bound is present)
Average Case: O(n*n!)
Best Case: O(n) (when an array is already sorted


2. Cocktail Shaker Sort

image credits: By Simpsons contributor - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14828123


Cocktail sort can be considered as another form of Bubble sort Algorithm. The main difference between the two is that Bubble sort is unidirectional, i.e. it traverses elements starting from left moves the element to correct position in the first iteration and then continues the next iterations whereas Cocktail Sort is bidirectional, i.e. it traverses the given array in both directions consecutively.

Algorithm
Each iteration in this type of sorting is divided into two parts.

Part 1: In the first part, looping of the array starts from left, and it moves towards the right, just like in bubble sort. The value of adjacent items are compared during the looping if the value on the left is greater than the right one, then the swapping of the two occurs. After the iteration ends, the value at the end is the greatest one.

Part 2: The second part of the looping starts from the item just before the item, which is most recently sorted. This looping will continue in the opposite direction with all the comparisons of the adjacent items with necessary swapping where ever it is required.


To explain it in more simple words, lets consider an example.

First Pass(Forward):
(6 2 5 3 9 1 3) ? (2 6 5 3 9 1 3),  since 6 > 2
(2 6 5 3 9 1 3) ? (2 5 6 3 9 1 3),  since 6 > 5
(2 5 6 3 9 1 3) ? (2 5 3 6 9 1 3),  since 6 > 3
(2 5 3 6 9 1 3) ? (2 5 3 6 9 1 3)
(2 5 3 6 9 1 3) ? (2 5 3 6 1 9 3),  since 9 > 1
(2 5 3 6 1 9 3) ? (2 5 3 6 0 3 9),  since 9 > 3

the greatest element is present at the last index

First Pass (Backward):
(2 5 3 6 1 3 9) ? (2 5 3 6 1 3 9)
(2 5 3 6 1 3 9) ? (2 5 3 1 6 3 9), since 6 > 1
(2 5 3 1 6 3 9) ? (2 5 1 3 6 3 9),since 3 > 1
(2 5 1 3 6 3 9) ? (2 1 5 3 6 3 9),since 5 > 1
(2 1 5 3 6 3 9) ? (1 2 5 3 6 3 9),since 2 > 1

the smallest element is present at the first index

Second Pass(Forward):
(1 2 5 3 6 3 9) ? (1 2 5 3 6 3 9)
(1 2 5 3 6 3 9) ? (1 2 3 5 6 3 9),  since 5 > 3
(1 2 3 5 6 3 9) ? (1 2 3 5 6 3 9)
(1 2 3 5 6 3 9) ? (1 2 3 5 3 6 9), since 6 > 3

Second Pass(Backward):

(1 2 3 5 3 6 9) ? (1 2 3 3 5 6 9), since 5 > 3

(1 2 3 3 5 6 9) ? (1 2 3 3 5 6 9)
(1 2 3 3 5 6 9) ? (1 2 3 3 5 6 9)

The array was already sorted after the first iteration of the second pass, but we need to complete so that our algorithm knows it in the next pass.

The code for the Cocktail sort is

Time Complexity

Worst and Average Case Time Complexity: O(n*n).

Best Case Time Complexity: O(n). The best-case occurs when an array is already sorted.


Conclusion
In this article, we discussed two amazing sorting algorithms i.e. Bogo Sort and Cocktail Shaker Sorting Algorithm in detail and also learned to code them  and I hope you got answers to all the questions like How we can use them, What are their time complexity ...etc

So, Which one was your personal favourite?      
Previous Post
Next Post

post written by:

Hi, Navjyot Singh is a coder, content maker and a freelance developer who's pursuing an undergraduate Engineering degree in Computer Science. He started out as a web developer but later picked up the mobile as his favourite platform to develop applications. A Writer by day and coder by night is loathed to discuss himself as the third person but can be persuaded to do so from time to time.

0 comments: