C++ Program to Implement Stooge Sort Algorithm

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.

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.

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: ";
	int arr[n];
	for(i = 0; i < n; i++)
		cout<<"Enter element "<<i+1<<": ";
	StoogeSort(arr, 0, n-1);
	// Printing the sorted data.
	cout<<"\nSorted Data ";
	for (i = 0; i < n; 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.

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.

If you find any mistake above, kindly email to [email protected]

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.