Write a program to demonstrate stooge sort algorithm.
Solution:
using System;
namespace StoogeSort
{
class Program
{
static void Main()
{
int[] arr = { 89, 2, 12, 44, 90, 88, 46 };
var n = arr.Length;
Console.WriteLine("Array before sorting");
for (var i = 0; i < n; i++)
Console.WriteLine(arr[i]);
Sort(arr, 0, n - 1);
Console.WriteLine("Array after sorting");
for (var i = 0; i < n; i++)
Console.WriteLine(arr[i]);
Console.ReadLine();
}
static void Sort(int[] arr, int startPos, int length)
{
if (startPos >= length)
return;
if (arr[startPos] > arr[length])
{
var temp = arr[startPos];
arr[startPos] = arr[length];
arr[length] = temp;
}
if (length - startPos + 1 <= 2) return;
var pos = (length - startPos + 1) / 3;
Sort(arr, startPos, length - pos);
Sort(arr, startPos + pos, length);
Sort(arr, startPos, length - pos);
}
}
}