Как вычислить количество сравнений и перестановок? - 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++;
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

11   голосов , оценка 3.909 из 5
Похожие ответы