Python Program for Stooge Sort
Last Updated :
28 Aug, 2023
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
def stoogesort(arr, l, h):
if l >= h:
return
if arr[l]>arr[h]:
t = arr[l]
arr[l] = arr[h]
arr[h] = t
if h-l+1 > 2:
t = (int)((h-l+1)/3)
stoogesort(arr, l, (h-t))
stoogesort(arr, l+t, (h))
stoogesort(arr, l, (h-t))
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
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!
Please Login to comment...