The Stooge sort is a recursive sorting algorithm. It is defined as below (for ascending order sorting).
Python Program for Stooge Sort
The provided Python code implements the Stooge Sort algorithm, a relatively inefficient sorting algorithm. It recursively divides the array into three parts and sorts the outer thirds to bring the largest element into the correct position. It starts with comparing the first and last elements, swapping them if necessary. Then, it recursively sorts the initial two-thirds and the last two-thirds, ensuring the middle part is in its final position. This process repeats recursively until the array is sorted. The driver code initializes an array, applies Stooge Sort, and prints the sorted array. Stooge Sort’s time complexity is relatively high, making it inefficient for practical use.
Step 1 : If value at index 0 is greater than
value at last index, swap them.
Step 2: Recursively,
a) Stooge sort the initial 2/3rd of the array.
b) Stooge sort the last 2/3rd of the array.
c) Stooge sort the initial 2/3rd again to confirm.
Python3
# Python program to implement stooge sort def stoogesort(arr, l, h): if l >= h: return # If first element is smaller # than last,swap them if arr[l]>arr[h]: t = arr[l] arr[l] = arr[h] arr[h] = t # If there are more than 2 elements in # the array if h-l+1 > 2: t = (int)((h-l+1)/3) # Recursively sort first 2/3 elements stoogesort(arr, l, (h-t)) # Recursively sort last 2/3 elements stoogesort(arr, l+t, (h)) # Recursively sort first 2/3 elements # again to confirm stoogesort(arr, l, (h-t)) # driver arr = [2, 4, 5, 3, 1] n = len(arr) stoogesort(arr, 0, n-1) for i in range(0, n): print(arr[i], end = ' ') # Code Contributed by Mohit Gupta_OMG <(0_o)> |
Output:
1 2 3 4 5
Time Complexity:
The running time complexity of stooge sort can be written as,
T(n) = 3T(3n/2) + O(1)
Solution of above recurrence is O(n(log3/log1.5)) = O(n2.709), hence it is slower than even bubble sort(n2).
Auxiliary Space: O(n)
Please refer complete article on Stooge Sort for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
