Как вычислить количество сравнений и перестановок? - C#
Формулировка задачи:
Здравствуйте. У меня есть 2 сортировки "Вставкой" и Шейкером, как мне посчитать кол-во сравнений и перестановок в каждом из них.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApp2
{
class Program
{
public int[] a = new int[50];
static void PoVozrostaniy(ref int[] a, int count)
{
{
int i, j, t;
Random rand = new Random();
for (i = 0; i < 50; i++)
a[i] = rand.Next(0, 400);
for (i = 1; i < 50; i++)
{
t = a[i];
for (j = i; j > 0 && a[j - 1] > t; j--)
{
a[j] = a[j - 1];
}
a[j] = t;
}
Console.WriteLine();
Console.WriteLine("Сгенерированный массив по возрастанию:");
for (j = 0; j < 50; j++)
{
Console.Write(a[j] + " ");
}
}
}
static void PoUbivaniyu(ref int[] a, int count)
{ int i, j,t;
Random rand = new Random();
for (i=0;i<50;i++)
a[i] = rand.Next(0, 400);
for(i=1;i<50;i++)
{
t=a[i];
for(j=i;j>0 && a[j-1]<t;j--)
{
a[j]=a[j-1];
}
a[j]=t;
}
Console.WriteLine();
Console.WriteLine("Сгенерированный массив по спадонию:");
for (j=0;j<50;j++)
{
Console.Write(a[j] + " ");
}
}
static void CreateMass(ref int[] a, int count)
{
Console.WriteLine("Сформированный массив:");
Random rand = new Random();
for (int i = 0; i < 50; i++)
{
a[i] = rand.Next(0, 400);
Console.Write(a[i]+" ");
}
;
}
static void SortInsertMethod(ref int[] a, int count)
{
int x, i, j;
Console.WriteLine();
Console.WriteLine("Отсортированный массив методом вставки:");
for (i = 0; i < 50; i++)
{
x = a[i];
for (j = i - 1; j >= 0 && a[j] > x; j--)
{
a[j + 1] = a[j];
}
a[j + 1] = x;
}
for (i = 0; i < 50; i++)
{ Console.Write(a[i] + " "); }
Console.WriteLine();
}
static void ShakeSort(ref int[] a, int count)
{
int b = 0;
int left = 0;//Левая граница
int right = 50 - 1;//Правая граница
Console.WriteLine("Отсортированный массив методом Шейкера:");
while (left < right)
{
for (int i = left; i < right; i++)//Слева направо...
{
if (a[i] > a[i + 1])
{
b = a[i];
a[i] = a[i + 1];
a[i + 1] = b;
b = i;
}
}
right = b;//Сохраним последнюю перестановку как границу
if (left >= right) break;//Если границы сошлись выходим
for (int i = right; i > left; i--)//Справа налево...
{
if (a[i - 1] > a[i])
{
b = a[i];
a[i] = a[i - 1];
a[i - 1] = b;
b = i;
}
}
left = b;//Сохраним последнюю перестановку как границу
}
for (int i = 0; i < 50; i++)
{ Console.Write(a[i] + " "); }
Console.WriteLine();
}
static void Main(string[] args)
{
int k ;
k = int.Parse( Console.ReadLine());
int[] a = new int[50];
//Program prog = new Program();
if (k == 1)
{
Program.CreateMass(ref a, 50);
Console.ReadLine();
}
else if (k == 2)
{
Program.PoUbivaniyu(ref a, 50);
Console.ReadLine();
}
if (k == 3)
{
Program.PoVozrostaniy(ref a, 50);
Console.ReadLine();
}
Program.SortInsertMethod(ref a, 50);
Program.ShakeSort(ref a, 50);
Console.ReadLine();
}
}
}Решение задачи: «Как вычислить количество сравнений и перестановок?»
textual
Листинг программы
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void Main()
{
var a = Enumerable.Range(1, 100).Reverse().ToArray();
var comparer = new TrackingComparer<int>();
var swapper = new TrackingSwapper<int>();
// Пузырик
for (int i = 0; i < a.Length; i++)
{
for (int j = i + 1; j < a.Length; j++)
{
if (comparer.Compare(a[i], a[j]) > 0)
swapper.Swap(ref a[i], ref a[j]);
}
}
Console.WriteLine(string.Join(" ", a));
Console.WriteLine($"Comparisons: {comparer.ComparisonCount}");
Console.WriteLine($"Swaps: {swapper.SwapCount}");
}
}
sealed class TrackingComparer<T> : IComparer<T>
{
private readonly Func<T, T, int> _comparison;
public TrackingComparer(Func<T, T, int> comparison)
{
_comparison = comparison ?? throw new ArgumentNullException(nameof(comparison));
}
public TrackingComparer(IComparer<T> comparer)
{
if (comparer == null)
throw new ArgumentNullException(nameof(comparer));
_comparison = comparer.Compare;
}
public TrackingComparer() : this(Comparer<T>.Default)
{
}
public int ComparisonCount { get; private set; }
public int Compare(T x, T y)
{
var result = _comparison(x, y);
ComparisonCount++;
return result;
}
}
sealed class TrackingSwapper<T>
{
public int SwapCount { get; private set; }
public void Swap(ref T a, ref T b)
{
T c = a;
a = b;
b = c;
SwapCount++;
}
}