Python Program for Stooge Sort

In this article, let’s discuss few points about the Stooge sort algorithm and its implementation in Python.

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

The algorithm is defined as follows

  • 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.

Stooge Sort in Python

1. Initialize the array and pass through stoogesort function

2. Check if the first element is smaller than the last, if true swap them

3. If the size of the array is greater than 2 then

4. Recursively sort first 2/3 elements

5. Recursively sort last 2/3 elements

6. Recursively sort first 2/3 elements

7. print the sorted array.

def stoogesort(arr, start, end): 
    if start >= end: 
        return

    if arr[start]>arr[end]: 
        temp = arr[start] 
        arr[start] = arr[end] 
        arr[end] = temp 

    if end-start+1 > 2: 
        temp = (int)((end-start+1)/3) 

        stoogesort(arr, start, (end-temp)) 
        stoogesort(arr, start+temp, (end)) 
        stoogesort(arr, start, (end-temp)) 
   
  
  
arr = [2, 4, 5, 3, 1] 
n = len(arr) 
print("The original unsorted array is ")
for i in range(0, n): 
    print(arr[i], end = ' ')

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

Output

The original unsorted array is 
2 4 5 3 1 
The sorted array is 
1 2 3 4 5

Also, refer

Leave a Reply

Your email address will not be published. Required fields are marked *