C++ Program to Perform Stooge Sort

«
»

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

Problem Description

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).

Problem Solution

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.

advertisement
Program/Source Code

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;
}
Program Explanation

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.

advertisement
Runtime Test Cases
 
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.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn