Python Program for Stooge Sort
The Stooge sort is a recursive sorting algorithm. It is defined as below (for ascending order sorting).
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 sortdef 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)) # deriver arr = [2, 4, 5, 3, 1]n = len(arr)stoogesort(arr, 0, n-1) for i in range(0, n): print(arr[i], end = \' \')# |
Output:
1 2 3 4 5