Stooge Sort Algorithm
The Stooge Sort Algorithm is a highly inefficient and rarely-used sorting algorithm in computer science. It is a recursive algorithm that works by dividing the input list into three equal parts and recursively sorting the first two-thirds and the last two-thirds of the list, then finally sorting the first two-thirds once again. This process is repeated until the base case is reached, where the list contains only one or two elements. In the case of two elements, the algorithm swaps the elements if they are out of order.
Despite its inefficiency, with a time complexity of O(n^(log(3)/log(1.5))) which is approximately O(n^2.71), the Stooge Sort Algorithm serves as an interesting example of recursion and is sometimes utilized as a teaching tool for computer science students to learn about the concept of recursion and its application in sorting algorithms. The algorithm's simplicity and ease of implementation make it an accessible starting point for beginners, but it is not suitable for practical use in real-world scenarios due to its poor performance compared to more advanced sorting algorithms, such as Quick Sort or Merge Sort.
#include <stdio.h>
void stoogesort(int [], int, int);
void main()
{
int arr[100], i, n;
printf("How many elements do you want to sort: ");
scanf("%d", &n);
for (i = 0;i < n; i++)
scanf(" %d", &arr[i]);
stoogesort(arr, 0, n - 1);
printf("Sorted array : \n");
for (i = 0;i < n;i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
void stoogesort(int arr[], int i, int j)
{
int temp, k;
if (arr[i] > arr[j])
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
if ((i + 1) >= j)
return;
k = (int)((j - i + 1) / 3);
stoogesort(arr, i, j - k);
stoogesort(arr, i + k, j);
stoogesort(arr, i, j - k);
}
