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 = ' ')
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
I hope you liked and understood the sorting algorithm and its implementation. Try it by yourself!
You can also read:
- Brick Sort Algorithm in Python [Easily Implemented]
- Selection Sort in Python
- Insertion Sort in Python
- How to Implement QuickSort in Python?
Happy Learning! 😇