Table of Contents
Introduction
The stooge sort algorithm is the recursive algorithm. Our task is to sort the given array element using stooge sort.
Program
def sort(arr,first,last): if first >= last: return # Compare first and last element and swap if required if arr[first]>arr[last]: temp = arr[first] arr[first] = arr[last] arr[last] = temp if last-first+1 > 2: temp = (int)((last - first + 1)/ 3) # Sort first 2/3 elements sort(arr, first, (last - temp)) # Sort last 2/3 elements sort(arr, first + temp, (last)) # Sort first 2/3 elements sort(arr, first, (last - temp)) ip_arr = [9, 4, 1, 2] sort(ip_arr, 0, len(ip_arr)-1) print("The sorted array is :") for i in range(0, len(ip_arr)): print(ip_arr[i])
Output
Explanation
In stooge sort, the array is divided into 2/3 parts. The steps followed in the above program are:
- We take the first element of the array and compare it to the last element. If required the values are swapped.
- Recursively we are sorting the first 2/3 elements of the array.
- Then, recursively we will sort the last 2/3 elements of the array.
- At last again we will sort the first 2/3 elements to check the elements are sorted
- The sorted array is returned.
0 Comments