{"id":25872,"date":"2021-12-16T09:20:24","date_gmt":"2021-12-16T03:50:24","guid":{"rendered":"https:\/\/python-programs.com\/?p=25872"},"modified":"2021-12-16T09:20:24","modified_gmt":"2021-12-16T03:50:24","slug":"python-program-for-stooge-sort","status":"publish","type":"post","link":"https:\/\/python-programs.com\/python-program-for-stooge-sort\/","title":{"rendered":"Python Program for Stooge Sort"},"content":{"rendered":"
Stooge Sort:<\/strong><\/p>\n 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.<\/p>\n Algorithm:<\/strong><\/p>\n Steps:<\/strong><\/p>\n The array is first given to the function, which compares the first and last elements and swaps them if the first element is smaller.<\/p>\n 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.<\/p>\n Finally, simply show the sorted array on the window.<\/p>\n Examples:<\/strong><\/p>\n Example1:<\/strong><\/p>\n Input:<\/strong><\/p>\n Output:<\/strong><\/p>\n Example2:<\/strong><\/p>\n Input:<\/strong><\/p>\n Output:<\/strong><\/p>\n <\/p>\n Approach:<\/strong><\/p>\n Below is the implementation:<\/strong><\/p>\n Output:<\/strong><\/p>\n Approach:<\/strong><\/p>\n Below is the implementation:<\/strong><\/p>\n Output:<\/strong><\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" 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 …<\/p>\n\n
\n
Given List = [80, 90, 20, -10, 36]<\/pre>\n
The given list after sorting = [-10, 20, 36, 80, 90]<\/pre>\n
Given List = [56, 43, -3, 100, 13]<\/pre>\n
The given list after sorting = [-3, 13, 43, 56, 100]<\/pre>\n
Program for Stooge Sort in Python<\/h2>\n
Method #1: Using Recursion (Static Input)<\/h3>\n
\n
# Create a Recursive function say Stooge_Sorting() which accepts the given list,\r\n# start value and end value as the arguments and returns the sorted list.\r\n\r\n\r\ndef Stooge_Sorting(gvn_lst, strt_val, end_val):\r\n # Inside the function, check whether the list has any elements using the if\r\n # conditional statement.\r\n if strt_val >= end_val:\r\n # If it is true then return.\r\n return\r\n # Check whether the element present at the start value of the list is greater\r\n # than the element present at the end value using the if conditional statement.\r\n if gvn_lst[strt_val] > gvn_lst[end_val]:\r\n # If it is true, then swap both of them.\r\n gvn_lst[strt_val], gvn_lst[end_val] = gvn_lst[end_val], gvn_lst[strt_val]\r\n # Check whether there are more than two elements using the if conditional\r\n # statement.\r\n if end_val-strt_val+1 > 2:\r\n tempry = (int)((end_val-strt_val+1)\/3)\r\n # If it is true, then pass the (gvn_lst, strt_val, (end_val-tempry)) as the\r\n # arguments to the function itself (Recursive Logic).\r\n Stooge_Sorting(gvn_lst, strt_val, (end_val-tempry))\r\n # Pass the (gvn_lst, strt_val+tempry, (end_val)) as the arguments to the\r\n # function itself (Recursive Logic).\r\n Stooge_Sorting(gvn_lst, strt_val+tempry, (end_val))\r\n # Pass the (gvn_lst, strt_val, (end_val-tempry)) as the\r\n # arguments to the function itself (Recursive Logic).\r\n Stooge_Sorting(gvn_lst, strt_val, (end_val-tempry))\r\n\r\n\r\n# Give the list as static input and store it in a variable.\r\ngvn_lst = [80, 90, 20, -10, 36]\r\n# Calculate the length of the given list using the len() function and store\r\n# it in another variable.\r\nlst_len = len(gvn_lst)\r\n# Take a variable and initialize it with the start value as 0.\r\nstrt_val = 0\r\n# Take another variable and initialize it with the end value as length of the\r\n# list-1.\r\nend_val = lst_len-1\r\n# Pass the given list, start value, and end value as the arguments to the\r\n# Stooge_Sorting() function.\r\nStooge_Sorting(gvn_lst, strt_val, end_val)\r\n# Print the given list after sorting.\r\nprint(\"The given list after sorting = \", gvn_lst)\r\n<\/pre>\n
The given list after sorting = [-10, 20, 36, 80, 90]<\/pre>\n
Method #2: Using Recursion (User Input)<\/h3>\n
\n
# Create a Recursive function say Stooge_Sorting() which accepts the given list,\r\n# start value and end value as the arguments and returns the sorted list.\r\n\r\n\r\ndef Stooge_Sorting(gvn_lst, strt_val, end_val):\r\n # Inside the function, check whether the list has any elements using the if\r\n # conditional statement.\r\n if strt_val >= end_val:\r\n # If it is true then return.\r\n return\r\n # Check whether the element present at the start value of the list is greater\r\n # than the element present at the end value using the if conditional statement.\r\n if gvn_lst[strt_val] > gvn_lst[end_val]:\r\n # If it is true, then swap both of them.\r\n gvn_lst[strt_val], gvn_lst[end_val] = gvn_lst[end_val], gvn_lst[strt_val]\r\n # Check whether there are more than two elements using the if conditional\r\n # statement.\r\n if end_val-strt_val+1 > 2:\r\n tempry = (int)((end_val-strt_val+1)\/3)\r\n # If it is true, then pass the (gvn_lst, strt_val, (end_val-tempry)) as the\r\n # arguments to the function itself (Recursive Logic).\r\n Stooge_Sorting(gvn_lst, strt_val, (end_val-tempry))\r\n # Pass the (gvn_lst, strt_val+tempry, (end_val)) as the arguments to the\r\n # function itself (Recursive Logic).\r\n Stooge_Sorting(gvn_lst, strt_val+tempry, (end_val))\r\n # Pass the (gvn_lst, strt_val, (end_val-tempry)) as the\r\n # arguments to the function itself (Recursive Logic).\r\n Stooge_Sorting(gvn_lst, strt_val, (end_val-tempry))\r\n\r\n\r\n# Give the list as user input using list(),map(),input(),and split() functions.\r\n# Store it in a variable.\r\ngvn_lst = list(map(int, input(\r\n 'Enter some random List Elements separated by spaces = ').split()))\r\n \r\n# Calculate the length of the given list using the len() function and store\r\n# it in another variable.\r\nlst_len = len(gvn_lst)\r\n# Take a variable and initialize it with the start value as 0.\r\nstrt_val = 0\r\n# Take another variable and initialize it with the end value as length of the\r\n# list-1.\r\nend_val = lst_len-1\r\n# Pass the given list, start value, and end value as the arguments to the\r\n# Stooge_Sorting() function.\r\nStooge_Sorting(gvn_lst, strt_val, end_val)\r\n# Print the given list after sorting.\r\nprint(\"The given list after sorting = \", gvn_lst)\r\n<\/pre>\n
Enter some random List Elements separated by spaces = 56 43 -3 100 13\r\nThe given list after sorting = [-3, 13, 43, 56, 100]<\/pre>\n