Posted on by Kalkicode
Code Sorting

# Stooge Sort

Stooge Sort is a recursive sorting algorithm that sorts an array by recursively dividing the array into three parts and sorting the first two parts recursively, and then sorting the first and last parts recursively again. The algorithm gets its name from the Three Stooges comedy act, in which one of the characters would repeatedly hit the other two over the head in a repetitive pattern.

The algorithm works by comparing the first and last elements of the array, and swapping them if the first element is greater than the last element. Then, the algorithm recursively sorts the first two-thirds of the array, then the last two-thirds of the array, and finally the first two-thirds again.

The time complexity of Stooge Sort is O(n^(log 3/log 1.5)) ≈ O(n^2.7095), which is worse than most other sorting algorithms, including bubble sort, insertion sort, and quicksort. However, Stooge Sort is simple to implement and can be useful in educational settings to teach recursion and divide-and-conquer algorithms.

Here given code implementation process.

``````// C Program
// Sort array elements by using Stooge Sort
#include <stdio.h>

//Function which is display arr elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("  %d", arr[i]);
}
printf("\n");
}
// Swapping the array elements in given location
void swap_data(int arr[], int first, int second)
{
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
//Perform the stooge sort in given array
void stooge_sort(int arr[], int first, int last)
{
if (first <= last)
{
if (arr[first] > arr[last])
{
//When need to swap array elements
swap_data(arr, first, last);
}
if ((last - first + 1) >= 3)
{
int t = (last - first + 1) / 3;
//Recursively sort array elements
stooge_sort(arr, first, last - t);
stooge_sort(arr, first + t, last);
stooge_sort(arr, first, last - t);
}
}
}
int main()
{
//Define an sorted arr of integers
int arr[] = {
11 , 8 , 3 , 8 , 12 , -1 , -3 , 1 , 4 , 0 , 5
};
//Get the size of arr
int size = sizeof(arr) / sizeof(arr[0]);
//Before sort
printf("\n  Before Sort  :\n");
display(arr, size);
//Sort element
stooge_sort(arr, 0, size - 1);
//After sort
printf("\n  After Sort  :\n");
display(arr, size);
return 0;
}``````

#### Output

``````  Before Sort  :
11  8  3  8  12  -1  -3  1  4  0  5

After Sort  :
-3  -1  0  1  3  4  5  8  8  11  12``````
``````/*
Java Program
Sort array elements by using Stooge Sort
*/
class MySort
{
//Function which is display arr elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" " + arr[i] + "");
}
System.out.print("\n");
}
// Swapping the array elements in given location
public void swap_data(int[] arr, int first, int second)
{
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
// Perform the stooge sort in given array
public void stooge_sort(int[] arr, int first, int last)
{
if (first <= last)
{
if (arr[first] > arr[last])
{
//When need to swap array elements
swap_data(arr, first, last);
}
if ((last - first + 1) >= 3)
{
int t = (last - first + 1) / 3;
//Recursively sort array elements
stooge_sort(arr, first, last - t);
stooge_sort(arr, first + t, last);
stooge_sort(arr, first, last - t);
}
}
}
public static void main(String[] args)
{
MySort obj = new MySort();
//Define an sorted array of integers
int[] arr = {
11,
8,
3,
8,
12,
-1,
-3,
1,
4,
0,
5
};
//Get the size of array
int size = arr.length;
System.out.print("\n Before Sort :\n");
obj.display(arr, size);
//Sort element
obj.stooge_sort(arr, 0, size-1);
System.out.print("\n After Sort :\n");
obj.display(arr, size);
}
}``````

#### Output

`````` Before Sort :
11 8 3 8 12 -1 -3 1 4 0 5

After Sort :
-3 -1 0 1 3 4 5 8 8 11 12``````
``````//Include header file
#include <iostream>

using namespace std;
/*
C++ Program
Sort array elements by using Stooge Sort
*/
class MySort
{
public:
//Function which is display arr elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << arr[i] << "";
}
cout << "\n";
}
// Swapping the array elements in given location
void swap_data(int arr[], int first, int second)
{
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
// Perform the stooge sort in given array
void stooge_sort(int arr[], int first, int last)
{
if (first <= last)
{
if (arr[first] > arr[last])
{
//When need to swap array elements
this->swap_data(arr, first, last);
}
if ((last - first + 1) >= 3)
{
int t = (last - first + 1) / 3;
//Recursively sort array elements
this->stooge_sort(arr, first, last - t);
this->stooge_sort(arr, first + t, last);
this->stooge_sort(arr, first, last - t);
}
}
}
};
int main()
{
MySort obj = MySort();
int arr[] = {
11 , 8 , 3 , 8 , 12 , -1 , -3 , 1 , 4 , 0 , 5
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
cout << "\n Before Sort :\n";
obj.display(arr, size);
//Sort element
obj.stooge_sort(arr, 0, size - 1);
cout << "\n After Sort :\n";
obj.display(arr, size);
return 0;
}``````

#### Output

`````` Before Sort :
11 8 3 8 12 -1 -3 1 4 0 5

After Sort :
-3 -1 0 1 3 4 5 8 8 11 12``````
``````//Include namespace system
using System;
/*
C# Program
Sort array elements by using Stooge Sort
*/
class MySort
{
//Function which is display arr elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write(" " + arr[i] + "");
}
Console.Write("\n");
}
// Swapping the array elements in given location
public void swap_data(int[] arr, int first, int second)
{
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
// Perform the stooge sort in given array
public void stooge_sort(int[] arr, int first, int last)
{
if (first <= last)
{
if (arr[first] > arr[last])
{
//When need to swap array elements
swap_data(arr, first, last);
}
if ((last - first + 1) >= 3)
{
int t = (last - first + 1) / 3;
//Recursively sort array elements
stooge_sort(arr, first, last - t);
stooge_sort(arr, first + t, last);
stooge_sort(arr, first, last - t);
}
}
}
public static void Main(String[] args)
{
MySort obj = new MySort();
int[] arr = {
11 , 8 , 3 , 8 , 12 , -1 , -3 , 1 , 4 , 0 , 5
};
//Get the size of array
int size = arr.Length;
Console.Write("\n Before Sort :\n");
obj.display(arr, size);
//Sort element
obj.stooge_sort(arr, 0, size - 1);
Console.Write("\n After Sort :\n");
obj.display(arr, size);
}
}``````

#### Output

`````` Before Sort :
11 8 3 8 12 -1 -3 1 4 0 5

After Sort :
-3 -1 0 1 3 4 5 8 8 11 12``````
``````<?php
/*
Php Program
Sort array elements by using Stooge Sort
*/
class MySort
{
//Function which is display arr elements
public	function display( & \$arr, \$size)
{
for (\$i = 0; \$i < \$size; ++\$i)
{
echo " ". \$arr[\$i] ."";
}
echo "\n";
}
// Swapping the array elements in given location
public	function swap_data( & \$arr, \$first, \$second)
{
\$temp = \$arr[\$first];
\$arr[\$first] = \$arr[\$second];
\$arr[\$second] = \$temp;
}
// Perform the stooge sort in given array
public	function stooge_sort( & \$arr, \$first, \$last)
{
if (\$first <= \$last)
{
if (\$arr[\$first] > \$arr[\$last])
{
//When need to swap array elements
\$this->swap_data(\$arr, \$first, \$last);
}
if ((\$last - \$first + 1) >= 3)
{
\$t = intval((\$last - \$first + 1) / 3);
//Recursively sort array elements
\$this->stooge_sort(\$arr, \$first, \$last - \$t);
\$this->stooge_sort(\$arr, \$first + \$t, \$last);
\$this->stooge_sort(\$arr, \$first, \$last - \$t);
}
}
}
}

function main()
{
\$obj = new MySort();
//Define an sorted array of integers
\$arr = array(11, 8, 3, 8, 12, -1, -3, 1, 4, 0, 5);
//Get the size of array
\$size = count(\$arr);
echo "\n Before Sort :\n";
\$obj->display(\$arr, \$size);
//Sort element
\$obj->stooge_sort(\$arr, 0, \$size - 1);
echo "\n After Sort :\n";
\$obj->display(\$arr, \$size);
}
main();``````

#### Output

`````` Before Sort :
11 8 3 8 12 -1 -3 1 4 0 5

After Sort :
-3 -1 0 1 3 4 5 8 8 11 12``````
``````/*
Node Js Program
Sort array elements by using Stooge Sort
*/
class MySort
{
//Function which is display arr elements
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + arr[i] + "");
}
process.stdout.write("\n");
}
// Swapping the array elements in given location
swap_data(arr, first, second)
{
var temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
// Perform the stooge sort in given array
stooge_sort(arr, first, last)
{
if (first <= last)
{
if (arr[first] > arr[last])
{
//When need to swap array elements
this.swap_data(arr, first, last);
}
if ((last - first + 1) >= 3)
{
var t = parseInt((last - first + 1) / 3);
//Recursively sort array elements
this.stooge_sort(arr, first, last - t);
this.stooge_sort(arr, first + t, last);
this.stooge_sort(arr, first, last - t);
}
}
}
}

function main()
{
var obj = new MySort();
//Define an sorted array of integers
var arr = [11, 8, 3, 8, 12, -1, -3, 1, 4, 0, 5];
//Get the size of array
var size = arr.length;
process.stdout.write("\n Before Sort :\n");
obj.display(arr, size);
//Sort element
obj.stooge_sort(arr, 0, size - 1);
process.stdout.write("\n After Sort :\n");
obj.display(arr, size);
}
main();``````

#### Output

`````` Before Sort :
11 8 3 8 12 -1 -3 1 4 0 5

After Sort :
-3 -1 0 1 3 4 5 8 8 11 12``````
``````# 	Python 3 Program
# 	Sort array elements by using Stooge Sort

class MySort :
# Function which is display arr elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i] ,"", end = "")
i += 1

print("\n", end = "")

#  Swapping the array elements in given location
def swap_data(self, arr, first, second) :
temp = arr[first]
arr[first] = arr[second]
arr[second] = temp

#  Perform the stooge sort in given array
def stooge_sort(self, arr, first, last) :
if (first <= last) :
if (arr[first] > arr[last]) :
# When need to swap array elements
self.swap_data(arr, first, last)

if ((last - first + 1) >= 3) :
t = int((last - first + 1) / 3)
# Recursively sort array elements
self.stooge_sort(arr, first, last - t)
self.stooge_sort(arr, first + t, last)
self.stooge_sort(arr, first, last - t)

def main() :
obj = MySort()
# Define an sorted array of integers
arr = [11, 8, 3, 8, 12, -1, -3, 1, 4, 0, 5]
# Get the size of array
size = len(arr)
print("\n Before Sort :\n", end = "")
obj.display(arr, size)
# Sort element
obj.stooge_sort(arr, 0, size - 1)
print("\n After Sort :\n", end = "")
obj.display(arr, size)

if __name__ == "__main__": main()``````

#### Output

`````` Before Sort :
11   8   3   8   12   -1   -3   1   4   0   5

After Sort :
-3   -1   0   1   3   4   5   8   8   11   12``````
``````# 	Ruby Program
# 	Sort array elements by using Stooge Sort

class MySort

# Function which is display arr elements
def display(arr, size)

i = 0
while (i < size)

print(" ", arr[i] ,"")
i += 1
end
print("\n")
end
#  Swapping the array elements in given location
def swap_data(arr, first, second)

temp = arr[first]
arr[first] = arr[second]
arr[second] = temp
end
#  Perform the stooge sort in given array
def stooge_sort(arr, first, last)

if (first <= last)

if (arr[first] > arr[last])

# When need to swap array elements
self.swap_data(arr, first, last)
end
if ((last - first + 1) >= 3)

t = (last - first + 1) / 3
# Recursively sort array elements
self.stooge_sort(arr, first, last - t)
self.stooge_sort(arr, first + t, last)
self.stooge_sort(arr, first, last - t)
end
end
end
end
def main()

obj = MySort.new()
# Define an sorted array of integers
arr = [11, 8, 3, 8, 12, -1, -3, 1, 4, 0, 5]
# Get the size of array
size = arr.length
print("\n Before Sort :\n")
obj.display(arr, size)
# Sort element
obj.stooge_sort(arr, 0, size - 1)
print("\n After Sort :\n")
obj.display(arr, size)
end
main()``````

#### Output

`````` Before Sort :
11 8 3 8 12 -1 -3 1 4 0 5

After Sort :
-3 -1 0 1 3 4 5 8 8 11 12
``````
``````/*
Scala Program
Sort array elements by using Stooge Sort
*/
class MySort
{
//Function which is display arr elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + arr(i) + "");
i += 1;
}
print("\n");
}
// Swapping the array elements in given location
def swap_data(arr: Array[Int], first: Int, second: Int): Unit = {
var temp: Int = arr(first);
arr(first) = arr(second);
arr(second) = temp;
}
// Perform the stooge sort in given array
def stooge_sort(arr: Array[Int], first: Int, last: Int): Unit = {
if (first <= last)
{
if (arr(first) > arr(last))
{
//When need to swap array elements
swap_data(arr, first, last);
}
if ((last - first + 1) >= 3)
{
var t: Int = ((last - first + 1) / 3).toInt;
//Recursively sort array elements
stooge_sort(arr, first, last - t);
stooge_sort(arr, first + t, last);
stooge_sort(arr, first, last - t);
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MySort = new MySort();
//Define an sorted array of integers
var arr: Array[Int] = Array(11, 8, 3, 8, 12, -1, -3, 1, 4, 0, 5);
//Get the size of array
var size: Int = arr.length;
print("\n Before Sort :\n");
obj.display(arr, size);
//Sort element
obj.stooge_sort(arr, 0, size - 1);
print("\n After Sort :\n");
obj.display(arr, size);
}
}``````

#### Output

`````` Before Sort :
11 8 3 8 12 -1 -3 1 4 0 5

After Sort :
-3 -1 0 1 3 4 5 8 8 11 12``````
``````/*
Swift Program
Sort array elements by using Stooge Sort
*/
class MySort
{
//Function which is display arr elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", arr[i] ,"", terminator: "");
i += 1;
}
print("\n", terminator: "");
}
// Swapping the array elements in given location
func swap_data(_ arr: inout[Int], _ first: Int, _ second: Int)
{
let temp: Int = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}
// Perform the stooge sort in given array
func stooge_sort(_ arr: inout[Int], _ first: Int, _ last: Int)
{
if (first <= last)
{
if (arr[first] > arr[last])
{
//When need to swap array elements
self.swap_data(&arr, first, last);
}
if ((last - first + 1) >= 3)
{
let t: Int = (last - first + 1) / 3;
//Recursively sort array elements
self.stooge_sort(&arr, first, last - t);
self.stooge_sort(&arr, first + t, last);
self.stooge_sort(&arr, first, last - t);
}
}
}
}
func main()
{
let obj: MySort = MySort();
//Define an sorted array of integers
var arr: [Int] = [11, 8, 3, 8, 12, -1, -3, 1, 4, 0, 5];
//Get the size of array
let size: Int = arr.count;
print("\n Before Sort :\n", terminator: "");
obj.display(arr, size);
//Sort element
obj.stooge_sort(&arr, 0, size - 1);
print("\n After Sort :\n", terminator: "");
obj.display(arr, size);
}
main();``````

#### Output

`````` Before Sort :
11   8   3   8   12   -1   -3   1   4   0   5

After Sort :
-3   -1   0   1   3   4   5   8   8   11   12``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post