sd_2
.pdf11
Приложение A (обязательное)
Листинг программы
using System;
using System.Diagnostics;
namespace sd2_shella
{
class Program
{
static void Main(string[] args)
{
var t = new Stopwatch(); int S = 0;
Console.WriteLine("Введите размер массива N"); int N = int.Parse(Console.ReadLine());
var rand = new Random(); int[] massiv = new int[N];
for (int i = 0; i < massiv.Length; i++)
{
massiv[i] = rand.Next(0, 1000000); Console.WriteLine(massiv[i]);
}
Console.WriteLine("\n");
t.Start();
Console.WriteLine(string.Join(", ", sort(massiv,ref S))); t.Stop();
Console.ReadLine();
Console.WriteLine(($"Время сортировки: {t.Elapsed}")); Console.WriteLine(($"Действий:", S));
}
static void mon(ref int c, ref int g, ref int S)
{
var a = c; c = g;
g = a; S++;
}
static int[] sort(int[] massiv,ref int S)
{
var d = massiv.Length / 2; while (d >= 1)
{
for (var i = d; i < massiv.Length; i++)
{
var j = i;
while ((j >= d) && (massiv[j - d] > massiv[j]))
{
mon(ref massiv[j], ref massiv[j - d], ref S);
12
j = j - d; S++;
}
S++;
}
d = d / 2;
}
return massiv;
}
}
}
13
Приложение B (обязательное)
Листинг программы
using System;
using System.Diagnostics;
namespace sd2_rasc
{
class Program
{
static void Main(string[] args)
{
int s = 0;
var t = new Stopwatch(); int[][] a = new int[23][]; Random r = new Random(); a[0] = new int[1];
a[1] = new int[2]; a[2] = new int[3]; a[3] = new int[4]; a[4] = new int[5]; a[5] = new int[10]; a[6] = new int[15]; a[7] = new int[20]; a[8] = new int[25]; a[9] = new int[30]; a[10] = new int[40]; a[11] = new int[50]; a[12] = new int[75]; a[13] = new int[100]; a[14] = new int[150]; a[15] = new int[200]; a[16] = new int[250]; a[17] = new int[300]; a[18] = new int[400]; a[19] = new int[500]; a[20] = new int[600]; a[21] = new int[800]; a[22] = new int[1000]; t.Start();
for (int j = 0; j < a.Length; j++)
{
for (int i = 0; i < a[j].Length; i++)
{
a[j][i] = r.Next(0, 1000000);
}
}
14
for (int i = 0; i < 23; i++)
{
Console.WriteLine(string.Join("; ", RSort(a[i], ref s))); Console.WriteLine($"\nВремя сортировки: { t.ElapsedMilliseconds}"); Console.WriteLine("Количествово действий: {0}", s);
}
t.Stop();
}
public static int[] RSort(int[] a, ref int s)
{
double shag = a.Length; bool f = true;
int shag1, b; int i = 0;
while (shag > 1 || f)
{
shag /= 1.247; if (shag < 1)
{
shag = 1;
}
f = false;
int k = Convert.ToInt32(shag); while (i + k < a.Length)
{
shag1 = i + k;
if (a[i] > a[shag1])
{
b = a[i];
a[i] = a[shag1]; a[shag1] = b;
f = true; s++;
}
s++;
i++;
}
}
return a;
}
}
}
15
Приложение C (обязательное)
Листинг программы
using System;
using System.Diagnostics;
namespace sd2_bistr
{
class Program
{
static void Main(string[] args)
{
var t = new Stopwatch(); V:
int k = 0;
Console.Write("Введите длину массива "); int N = Convert.ToInt32(Console.ReadLine()); double[] massiv = new double[N];
Random random = new Random(); t.Restart();
for (int i = 0; i < N; ++i)
{
massiv[i] = random.NextDouble();
}
t.Start();
QuickSorting.sorting(massiv, 0, massiv.Length - 1, ref k); t.Stop();
Console.WriteLine($"Время сортировки: { t.Elapsed}"); Console.WriteLine($"Действий: {k}\n");
goto V;
}
}
class QuickSorting
{
public static void sorting(double[] massiv, long first, long last, ref int k)
{
double b;
double c = massiv[(last - first) / 2 + first]; long i = first, j = last;
while (i <= j)
{
while (massiv[i] < c && i <= last)
{
k++;
++i;
}
while (massiv[j] > c && j >= first)
16
{
k++; --j;
}
if (i <= j)
{
b = massiv[i]; massiv[i] = massiv[j]; massiv[j] = b;
k++;
++i; --j;
}
}
if (j > first)
{
sorting(massiv, first, j, ref k);
}
if (i < last)
{
sorting(massiv, i, last, ref k);
}
}
}
}