C++ Program to Perform Stooge Sort

This is a C++ program to sort the given data using Stooge Sort.

1. Stooge sort is a recursive sorting algorithm.
2. It divides the array into two overlapping parts, 2/3 each.
3. Sort the array in three steps by sorting I then II and again I part.
4. It is fairly inefficient algorithm with worst case time complexity O(n^2.7095).

1. Recursively divide the divide the array into two parts of size 2/3 of array length.
2. Sort the first part.
3. Sort second part.
4. Again sort the first part.
5. Display the result.
6. Exit.

C++ program to implement Shaker Sort.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#include<iostream>
 
using namespace std;
 
// A function implementing stooge sort.
void StoogeSort(int a[],int start, int end)
{
	int temp;
	// Further breaking the array if the Subpart's length is more than 2. 
	if(end-start+1 > 2)
	{
		temp = (end-start+1)/3;
		StoogeSort(a, start, end-temp);
		StoogeSort(a, start+temp, end);
		StoogeSort(a, start, end-temp);
	}
 
	// swapping the element at start and end. 
	if(a[end] < a[start])
	{
		temp = a[start];
		a[start] = a[end];
		a[end] = temp;
	}
}
 
int main()
{	
	int n, i;
	cout<<"\nEnter the number of data element to be sorted: ";
	cin>>n;
 
	int arr[n];
	for(i = 0; i < n; i++)
	{
		cout<<"Enter element "<<i+1<<": ";
		cin>>arr[i];
	}
 
	StoogeSort(arr, 0, n-1);
 
	// Printing the sorted data.
	cout<<"\nSorted Data ";
	for (i = 0; i < n; i++)
		cout<<"->"<<arr[i];
 
	return 0;
}

1. Take input of data.
2. Call StoogeSort() function with ‘arr’ the array of data and ‘n’ the number of values, in the argument list.
3. Implement Sorting using recursive approach.
4. Divide the array into first 2/3 element as part I and last 2/3 as part II.
5. Send the first, second and again first part into StoogeSort().
6. If the length is not further breakable then swap element at the start and end if a[end] < a[start].
7. Return to main and display the result.
8. Exit.

 
Case 1:(average case)
 
Enter the number of data element to be sorted: 5
Enter element 1: 99
Enter element 2: 45
Enter element 3: 2
Enter element 4: 35
Enter element 5: 121
 
Sorted Data ->2->35->45->99->121
 
 
Case 2:(best case)
 
Enter the number of data element to be sorted: 5
Enter element 1: 2
Enter element 2: 33
Enter element 3: 45
Enter element 4: 102
Enter element 5: 165
 
Sorted Data ->2->33->45->102->165
 
 
case 3: (worst case)
 
Enter the number of data element to be sorted: 5
Enter element 1: 998
Enter element 2: 564
Enter element 3: 32
Enter element 4: 8
Enter element 5: 1
 
Sorted Data ->1->8->32->564->998

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.