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

To begin, Stooge sorts the first two-thirds of the list.
Second, Stooge sorts the final two-thirds of the list.
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]