C++ Programming Code Examples

C++ > Sorting Searching Code Examples

C++ Program to Perform Stooge Sort



C++ Program to Perform Stooge Sort

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

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

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

#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;
}