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

```#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].
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. 