# Python Program for Stooge Sort

Stooge Sort:

Stooge sort is a recursive sorting method with high time complexity. The algorithm’s execution time is longer than that of the Bubble sort. It is, though, more efficient than slow sorting.

Algorithm:

• If the value in the first place is greater than the value in the last position, swap them.
• If the list contains three or more elements, then
1. To begin, Stooge sorts the first two-thirds of the list.
2. Second, Stooge sorts the final two-thirds of the list.
3. Finally, Stooge sorts the first two-thirds of the list once more.

Steps:

The array is first given to the function, which compares the first and last elements and swaps them if the first element is smaller.

Next, we assess the array’s size; if the size is greater than two, the array’s sections are called recursively to sort the first, last, and first two-thirds(2/3) of the array.

Finally, simply show the sorted array on the window.

Examples:

Example1:

Input:

Given List = [80, 90, 20, -10, 36]

Output:

The given list after sorting =  [-10, 20, 36, 80, 90]

Example2:

Input:

Given List = [56, 43, -3, 100, 13]

Output:

The given list after sorting = [-3, 13, 43, 56, 100]

## Program for Stooge Sort in Python

### Method #1: Using Recursion (Static Input)

Approach:

• Give the list as static input and store it in a variable.
• Calculate the length of the given list using the len() function and store it in another variable.
• Take a variable and initialize it with the start value as 0.
• Take another variable and initialize it with the end value as the length of the list-1.
• Create a Recursive function say Stooge_Sorting() which accepts the given list, start value and end value as the arguments and returns the sorted list.
• Inside the function, check whether the list has any elements using the if conditional statement.
• If it is true then return.
• Check whether the element present at the start value of the list is greater than the element present at the end value using the if conditional statement.
• If it is true, then swap both of them.
• Check whether there are more than two elements using the if conditional statement.
• If it is true, then pass the (gvn_lst, strt_val, (end_val-tempry)) as the arguments to the function itself (Recursive Logic).
• Pass the (gvn_lst, strt_val+tempry, (end_val)) as the arguments to the function itself (Recursive Logic).
• Pass the (gvn_lst, strt_val, (end_val-tempry)) as the arguments to the function itself (Recursive Logic).
• Pass the given list, start value, and end value as the arguments to the Stooge_Sorting() function.
• Print the given list after sorting.
• The Exit of the Program.

Below is the implementation:

# Create a Recursive function say Stooge_Sorting() which accepts the given list,
# start value and end value as the arguments and returns the sorted list.

def Stooge_Sorting(gvn_lst, strt_val, end_val):
# Inside the function, check whether the list has any elements using the if
# conditional statement.
if strt_val >= end_val:
# If it is true then return.
return
# Check whether the element present at the start value of the list is greater
# than the element present at the end value using the if conditional statement.
if gvn_lst[strt_val] > gvn_lst[end_val]:
# If it is true, then swap both of them.
gvn_lst[strt_val], gvn_lst[end_val] = gvn_lst[end_val], gvn_lst[strt_val]
# Check whether there are more than two elements using the if conditional
# statement.
if end_val-strt_val+1 > 2:
tempry = (int)((end_val-strt_val+1)/3)
# If it is true, then pass the (gvn_lst, strt_val, (end_val-tempry)) as the
# arguments to the function itself (Recursive Logic).
Stooge_Sorting(gvn_lst, strt_val, (end_val-tempry))
# Pass the (gvn_lst, strt_val+tempry, (end_val)) as the arguments to the
# function itself (Recursive Logic).
Stooge_Sorting(gvn_lst, strt_val+tempry, (end_val))
# Pass the (gvn_lst, strt_val, (end_val-tempry)) as the
# arguments to the function itself (Recursive Logic).
Stooge_Sorting(gvn_lst, strt_val, (end_val-tempry))

# Give the list as static input and store it in a variable.
gvn_lst = [80, 90, 20, -10, 36]
# Calculate the length of the given list using the len() function and store
# it in another variable.
lst_len = len(gvn_lst)
# Take a variable and initialize it with the start value as 0.
strt_val = 0
# Take another variable and initialize it with the end value as length of the
# list-1.
end_val = lst_len-1
# Pass the given list, start value, and end value as the arguments to the
# Stooge_Sorting() function.
Stooge_Sorting(gvn_lst, strt_val, end_val)
# Print the given list after sorting.
print("The given list after sorting = ", gvn_lst)


Output:

The given list after sorting =  [-10, 20, 36, 80, 90]

### Method #2: Using Recursion (User Input)

Approach:

• Give the list as user input using list(),map(),input(),and split() functions.
• Store it in a variable.
• Calculate the length of the given list using the len() function and store it in another variable.
• Take a variable and initialize it with the start value as 0.
• Take another variable and initialize it with the end value as the length of the list-1.
• Create a Recursive function say Stooge_Sorting() which accepts the given list, start value and end value as the arguments and returns the sorted list.
• Inside the function, check whether the list has any elements using the if conditional statement.
• If it is true then return.
• Check whether the element present at the start value of the list is greater than the element present at the end value using the if conditional statement.
• If it is true, then swap both of them.
• Check whether there are more than two elements using the if conditional statement.
• If it is true, then pass the (gvn_lst, strt_val, (end_val-tempry)) as the arguments to the function itself (Recursive Logic).
• Pass the (gvn_lst, strt_val+tempry, (end_val)) as the arguments to the function itself (Recursive Logic).
• Pass the (gvn_lst, strt_val, (end_val-tempry)) as the arguments to the function itself (Recursive Logic).
• Pass the given list, start value, and end value as the arguments to the Stooge_Sorting() function.
• Print the given list after sorting.
• The Exit of the Program.

Below is the implementation:

# Create a Recursive function say Stooge_Sorting() which accepts the given list,
# start value and end value as the arguments and returns the sorted list.

def Stooge_Sorting(gvn_lst, strt_val, end_val):
# Inside the function, check whether the list has any elements using the if
# conditional statement.
if strt_val >= end_val:
# If it is true then return.
return
# Check whether the element present at the start value of the list is greater
# than the element present at the end value using the if conditional statement.
if gvn_lst[strt_val] > gvn_lst[end_val]:
# If it is true, then swap both of them.
gvn_lst[strt_val], gvn_lst[end_val] = gvn_lst[end_val], gvn_lst[strt_val]
# Check whether there are more than two elements using the if conditional
# statement.
if end_val-strt_val+1 > 2:
tempry = (int)((end_val-strt_val+1)/3)
# If it is true, then pass the (gvn_lst, strt_val, (end_val-tempry)) as the
# arguments to the function itself (Recursive Logic).
Stooge_Sorting(gvn_lst, strt_val, (end_val-tempry))
# Pass the (gvn_lst, strt_val+tempry, (end_val)) as the arguments to the
# function itself (Recursive Logic).
Stooge_Sorting(gvn_lst, strt_val+tempry, (end_val))
# Pass the (gvn_lst, strt_val, (end_val-tempry)) as the
# arguments to the function itself (Recursive Logic).
Stooge_Sorting(gvn_lst, strt_val, (end_val-tempry))

# Give the list as user input using list(),map(),input(),and split() functions.
# Store it in a variable.
gvn_lst = list(map(int, input(
'Enter some random List Elements separated by spaces = ').split()))

# Calculate the length of the given list using the len() function and store
# it in another variable.
lst_len = len(gvn_lst)
# Take a variable and initialize it with the start value as 0.
strt_val = 0
# Take another variable and initialize it with the end value as length of the
# list-1.
end_val = lst_len-1
# Pass the given list, start value, and end value as the arguments to the
# Stooge_Sorting() function.
Stooge_Sorting(gvn_lst, strt_val, end_val)
# Print the given list after sorting.
print("The given list after sorting = ", gvn_lst)


Output:

Enter some random List Elements separated by spaces = 56 43 -3 100 13
The given list after sorting = [-3, 13, 43, 56, 100]