Как вычислить количество сравнений и перестановок? - 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++; } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д