Sorting by Reversals in C#
I am getting a masters and I was studying this and wanted to implement it to understand it fully. Efficiency could be improved for sure but the goal of this is not efficiency, just to implement the algorithm so when I question comes up on the final, I can answer it.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Reversals
{
class Program
{
static void Main(string[] args)
{
// SolveByReversals1
int[] array1 = new int[] { 0, 1, 2, 3, 7, 6, 5, 4, 9, 8, 10 };
Console.WriteLine("Before: " + string.Join(", ", array1));
SolveByReversals1(array1);
Console.WriteLine(" After: " + string.Join(", ", array1));
Console.WriteLine();
// SolveByReversals2
int[] array2 = new int[] { 0, 1, 2, 3, 7, 6, 5, 4, 9, 8, 10 };
Console.WriteLine("Before: " + string.Join(", ", array2));
SolveByReversals1(array2);
Console.WriteLine(" After: " + string.Join(", ", array2));
int[] array3 = new int[] { 0, 10, 20, 30, 70, 60, 50, 40, 90, 80, 100 };
Console.WriteLine("Before: " + string.Join(", ", array3));
SolveByReversals2(array3);
Console.WriteLine(" After: " + string.Join(", ", array3));
Console.WriteLine();
// SolveByReversals3
int[] array4 = new int[] { 0, 1, 2, 3, 7, 6, 5, 4, 9, 8, 10 };
Console.WriteLine("Before: " + string.Join(", ", array4));
SolveByReversals3(array4);
Console.WriteLine(" After: " + string.Join(", ", array4));
int[] array5 = new int[] { 0, 10, 20, 30, 70, 60, 50, 40, 90, 80, 100 };
Console.WriteLine("Before: " + string.Join(", ", array5));
SolveByReversals3(array5);
Console.WriteLine(" After: " + string.Join(", ", array5));
int[] array6 = new int[] { 0, 0, 1, 4, 3, 3, 1, 2, 2, 4 };
Console.WriteLine("Before: " + string.Join(", ", array6));
SolveByReversals3(array6);
Console.WriteLine(" After: " + string.Join(", ", array6));
}
/// <summary>
/// Works only for perfect sequences starting at zero
/// and incrementing by one {0,1,2,3,...,10,...}
/// </summary>
/// <param name="array"></param>
/// <returns></returns>
public static int[] SolveByReversals1(int[] array)
{
for (int i = 0; i < array.Length; i++)
{
int j = Array.IndexOf<int>(array, i);
Array.Reverse(array, i, j - i + 1);
}
return null;
}
/// <summary>
/// Works with sequences of unique integers.
/// </summary>
/// <param name="array"></param>
/// <returns></returns>
public static int[] SolveByReversals2(int[] array)
{
int pos = 0;
for (int i = 0; i < array.Max() - 1; i++)
{
int j = Array.IndexOf<int>(array, i, pos);
if (j == -1)
continue;
Array.Reverse(array, pos, j - pos + 1);
pos++;
}
return null;
}
/// <summary>
/// Works for numbers of any sequence.
/// </summary>
/// <param name="array"></param>
/// <returns></returns>
public static int[] SolveByReversals3(int[] array)
{
int pos = 0;
int highLoop = array.Max();
if (array.Length > highLoop)
highLoop = array.Length;
for (int i = 0; i < array.Max() - 1; i++)
{
int j = 0;
while ((j = Array.IndexOf<int>(array, i, pos)) != -1)
{
Array.Reverse(array, pos, j - pos + 1);
pos++;
}
}
return null;
}
}
}
So it was nice to implement this to understand some of the difficulties and solve this issue. I may never have arrived at the third method just from class discussion.
