Таблица 2.1 – Лучший и худший случаи для сортировок
100 |
Сортировка |
Быстрая сортировка |
Сортировка |
|||
элементов |
«расческой» |
|
|
«Шелла» |
||
|
|
|
|
|
|
|
|
Лучший |
Худший |
Лучший |
Худший |
Лучший |
Худший |
|
случай |
случай |
случай |
случай |
случай |
случай |
|
|
|
|
|
|
|
Число |
1233 |
1339 |
669 |
722 |
503 |
795 |
операций |
|
|
|
|
|
|
|
|
|
|
|
|
|
Время(мкс) |
12,8 |
18,7 |
7,8 |
8,2 |
5,4 |
12,4 |
|
|
|
|
|
|
|
Анализируя данную таблицу, можно сделать вывод, что в худшем случае быстрая сортировка показывает лучший результат, а в лучшем случае самый быстрый результат показывает сортировка «Шелла».
11
3 Заключение
Входе выполнения лабораторной работы были реализованы сортировки и проанализированы их алгоритмические сложности, так же найдены худшие и лучшие варианты для сортировок. Цели работы были достигнуты. Результаты по данным сортировкам совпали с теоретическими.
12
Приложение А
(обязательное)
Сортировка «расческой»
using System;
using System.Diagnostics; using System.Threading;
namespace StructureOfData21
{
class Program
{
static void Main(string[] args)
{
try
{
Console.Write("Введите количество чисел в массиве (Сортировка 'расческой'): ");
int n = int.Parse(Console.ReadLine()); Random rand = new Random();
Stopwatch stopWatch = new Stopwatch(); stopWatch.Start();
double[] arr = new double[n]; for (int i = 0; i <= n - 1; i++)
{
arr[i] = rand.NextDouble(); arr[i] *= 100;
while (arr[i] / 10 < 1)
{
arr[i] = rand.NextDouble(); arr[i] *= 100;
}
}
int step = arr.Length-1; int Sum = 0; while (step >= 1)
{
for (int i = 0; i + step < arr.Length; i++)
{
Sum++;
if (arr[i] > arr[i + step])
{
Sum++;
double temp = arr[i]; arr[i] = arr[i + step]; arr[i + step] = temp;
}
}
step = Convert.ToInt32(Math.Floor(step / 1.247));
}
stopWatch.Stop();
TimeSpan ts = stopWatch.Elapsed; Console.WriteLine(); Console.WriteLine("RunTime " + ts);
Console.WriteLine($"Количество операций = {Sum}"); //Console.ReadLine();
Main(args);
}
catch (Exception)
{
Console.WriteLine("Неверно введены данные!!!"); Main(args);
}
13
}
}
}
14
Приложение Б
(обязательное)
Быстрая сортировка
using System;
using System.Threading; using System.Diagnostics;
using System.Collections.Generic; using System.Runtime.ExceptionServices;
namespace quiq_sort2
{
class Program
{
static void sorting(double[] arr, int first, int last, ref int sum)
{
int count = 0;
double p = arr[(last - first) / 2 + first]; double temp;
int l = first, r = last; while (l <= r)
{
count++;
while (arr[l] < p && l <= last)
{
count++;
l++;
}
count++;
while (arr[r] > p && r >= first)
{
count++; r--;
}
if (l <= r)
{
count++;
temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; l++; r--;
}
}
sum += count; if (r > first)
{
sorting(arr, first, r, ref sum);
}
if (l < last)
{
sorting(arr, l, last, ref sum);
}
}
static void Main(string[] args)
{
Console.WriteLine("========================================"); Console.Write("Введите количество чисел в массиве (Быстрая сортировка):
");
int n = int.Parse(Console.ReadLine()); Random rand = new Random();
Stopwatch stopWatch = new Stopwatch(); double[] arr = new double[n];
15