Stooge Sort in Python - Step-By-Step Implementation in Python

Hey folks! In this tutorial, we will discuss the Stooge sort algorithm and learn how to implement in the Python Programming Language.

Let’s Begin with an introduction to the Stooge sort.

Introduction to Stooge Sort

Stooge sort is a recursive sorting which is known for its bad time complexity. The running time of the algorithm is slower than the Bubble sort. However, it is more efficient than slow sorting.

The algorithm is briefly defined as shown below:

If the value at the beginning position is larger than the value at the ending position, then swap them.
If there are 3 or more elements in the list, then,
- Firstly, Stooge sort the initial 2/3 of the list
- Secondly, Stooge sort the final 2/3 of the list
- Finally, Stooge sorts the initial 2/3 of the list again.

Steps Included in Stooge Sort Algorithm

There are a number of steps involved when it comes to the Stooge sorting Algorithm.

Firstly, the array is passed to the function and compare the first and the last element and swap them if the first element is smaller.

Next, we consider the size of the array, if the size>2 then the parts of the array are called recursively to sort the first, last, and again the first 2/3rd part of the array.

Finally, just display the sorted array on the screen. Now let’s look at the code implementation of this sorting algorithm.

Implementing Stooge Sort in Python

With the theory out of the way, let’s learn how to implement stooge sort in Python. This example is documented to help you understand each step of this algorithm well.

def stoogesort(arr, start, end): 
    
    # Check if there are elements in the array
    if start >= end: 
        return
    
    # Check first element with the last element
    if arr[start]>arr[end]: 
        temp = arr[start] 
        arr[start] = arr[end] 
        arr[end] = temp 
    
    # Check if the number of elements are more than 2
    if end-start+1 > 2: 
        temp = (int)((end-start+1)/3) 
        # Recursively call the parts of array to be sorted
        stoogesort(arr, start, (end-temp)) 
        stoogesort(arr, start+temp, (end)) 
        stoogesort(arr, start, (end-temp)) 

# Take Input of the Unorted Array
arr = list(map(int,input("Enter all the numbers of array separated by a space: ").split()))
n = len(arr)
          
# Print the Unsorted Array
print("The original unsorted array is: ")
for i in range(0, n): 
    print(arr[i], end = ' ')

stoogesort(arr, 0, n-1) 
          
# Print the Sorted Array
print("\nThe sorted array is: ")
for i in range(0, n): 
    print(arr[i], end = ' ')

Example outputs

Enter all the numbers of array separated by a space: 23 2 9 -3 0 34 1
The original unsorted array is: 
23 2 9 -3 0 34 1 
The sorted array is: 
-3 0 1 2 9 23 34

Enter all the numbers of array separated by a space: 9 4 -2 -2 4 67 100
The original unsorted array is: 
9 4 -2 -2 4 67 100 
The sorted array is: 
-2 -2 4 4 9 67 100

Conclusion

I hope you liked and understood the sorting algorithm and its implementation. Try it by yourself!

You can also read:

Happy Learning! 😇