Додайте клас Form1 і клас SortingArrs, в яких вже є код швидкого сортування.
namespace Sorting
{
public partial class Form1 : Form
{
SortingArrs A;
public int m, n = 1;
public Form1()
{ InitializeComponent(); }
private void AddColumns(int n, DataGridView dgw)
{
DataGridViewColumn column;
for (int i = 0; i < n; i++)
{ column = new DataGridViewColumn();
column.HeaderText = "Column" + i.ToString();
column.Name = "Column" + i.ToString();
dgw.Columns.Add(column.Name, column.HeaderText);
}
}
private void AddRows(int m, DataGridView dgw)
{
for (int i = 0; i <m; i++)
{
dgw.Rows.Add(); dgw.Rows[i].HeaderCell.Value = i.ToString();
}
}
private void размерМассиваToolStripMenuItem_Click(object sender, EventArgs e)
{
this.textBoxArraySize.Enabled = true;
if (string.IsNullOrWhiteSpace(textBoxArraySize.Text))
{
MessageBox.Show("Поле не должно быть пустым!");
return;
}
m = int.Parse(this.textBoxArraySize.Text);
}
private void создатьМассивToolStripMenuItem_Click(object sender, EventArgs e)
{
m = int.Parse(this.textBoxArraySize.Text);
A = new SortingArrs(m);//Создание массива
A.FillRndNumbers();
int k; k = this.dataGridView1.ColumnCount; //Чистка таблицы
if (k != 0)
for (int i = 0; i < k; i++)
this.dataGridView1.Columns.RemoveAt(0);
n = 1;
AddColumns(n, this.dataGridView1);
AddRows(m, this.dataGridView1);
}
Додайте в меню пункти заповнення масиву і обробник події Click нього.
private void заполнитьМассивToolStripMenuItem_Click(object sender, EventArgs e)
{
this.A.FillRndNumbers();
for (int i = 0; i < m; i++)
{ dataGridView1.Rows[i].Cells[0].Value = this.A.arr[i].ToString(); }
}
private void перезагрузитьИсходныToolStripMenuItem_Click(object sender, EventArgs e)
{
label3.Text = "Время в миллисекундах ";
for (int i = 0; i < m; i++)
{
dataGridView1.Rows[i].Cells[0].Value = this.A.copyarr[i].ToString();
A.arr[i] = A.copyarr[i];
}
}Додайте в меню пункти вибора алгоритмів сортування і обробники подій Click них.
private void быстраяСортировкаToolStripMenuItem_Click(object sender, EventArgs e)
{
A.QuickSort(); this.label3.Text += "QuickSort";
textBox1.Text = A.AnalyseTimeQuickSort().Time.ToString();
this.textBoxSwapCount.Text=A.AnalyseTimeQuickSort().CountSwap.ToString();
for (int i = 0; i < m; i++)
{
dataGridView1.Rows[i].Cells[0].Value = this.A.arr[i].ToString();
}
}
private void сортировкаСлияниемToolStripMenuItem_Click(object sender, EventArgs e)
{
A.SortMerge(); this.label3.Text += "MergeSort";
textBox1.Text = A.AnalyseTimeMergeSort().Time.ToString();
this.textBoxSwapCount.Text = A.AnalyseTimeMergeSort().CountSwap.ToString();
for (int i = 0; i < m; i++)
{
dataGridView1.Rows[i].Cells[0].Value = this.A.arr[i].ToString();
}
}
private void пирамидальнаяСортировкаToolStripMenuItem_Click(object sender, EventArgs e)
{
A.PyramidSort(); this.label3.Text += "PyramidSort";
textBox1.Text = A.AnalyseTimeHeapSort().Time.ToString();
this.textBoxSwapCount.Text = A.AnalyseTimeHeapSort().CountSwap.ToString();
for (int i = 0; i < m; i++)
{
dataGridView1.Rows[i].Cells[0].Value = this.A.arr[i].ToString();
}
}
private void выходToolStripMenuItem_Click(object sender, EventArgs e)
{
Application.Exit();
}
private void textBoxArraySize_KeyPress(object sender, KeyPressEventArgs e)
{
// Разрешить клавиши управления: Backspace, Delete, стрелки
if (char.IsControl(e.KeyChar))
return;
// Разрешить только цифры
if (!char.IsDigit(e.KeyChar))
e.Handled = true;
}
}
}
Клас SortingArrs, в якому вже є код швидкого сортування, долайте інші.
namespace Sorting
{
public struct Analyse
{
public long Time { get; set; }
public long CountSwap { get; set; }
public Analyse(long time, long countSwap)
{
Time = time;
CountSwap = countSwap;
}
}
internal class SortingArrs
{
//delegate
public delegate void SortMethod();
int n; //размер массива
int Heap_Size; //размер пирамиды, построенной на массиве
public int[] arr; //сортируемый массив
public int[] copyarr;
Random rnd;
private long swapCount; // счетчик перестановок
//конструктор класса
public SortingArrs(int n)
{
this.n = n;
this.arr = new int[n]; this.copyarr = new int[n];
Heap_Size = n;
rnd = new Random();
swapCount = 0;
}
public int this[int n]
{
get
{
return arr[n];
}
}
public void FillRndNumbers()
{
for (int i = 0; i < n; i++)
{
arr[i] = rnd.Next(-1000, 1000);
copyarr[i] = arr[i];
}
}
// Вспомогательный метод для обмена элементов с подсчетом
private void Swap(ref int a, ref int b)
{
int temp = a;
a = b;
b = temp;
swapCount++;
}
// Вызывает рекурсивную процедуру QSort,
// передавая ей границы сортируемого массива.
// Сортируемый массив arr задается
// соответствующим полем класса.
public void QuickSort()
{
swapCount = 0; // сброс счетчика перед сортировкой
QSort(0, n - 1);
}
void QSort(int start, int finish)
{
if (start != finish)
{
int ind = rnd.Next(start, finish);
int item = arr[ind];
int ind1 = start, ind2 = finish;
/********
Введем три непересекающихся множества:
S1: {arr(i), start <= i =< ind1-1}
S2: {arr(i), ind1 <= i =< ind2}
S1: {arr(i), ind2+1 <= i =< finish}
Введем следующие логические условия,
играющие роль инвариантов циклов нашей программы:
P1: объединение S1, S2, S3 = arr
P2: (S1(i) < item) Для всех элементов S1
P3: (S3(i) >= item) Для всех элементов S3
P4: item - случайно выбранный элемент arr
Нетрудно видеть, что все условия становятся
истинными после завершения инициализатора цикла.
Для пустых множеств S1 и S3 условия P2 и P3
считаются истинными по определению.
Inv = P1 & P2 & P3 & P4
********/
while (ind1 <= ind2)
{
while ((ind1 <= ind2) && (arr[ind1] < item)) ind1++;
//(Inv == true) & ~B1 (B1 - условие цикла while)
while ((ind1 <= ind2) && (arr[ind2] >= item)) ind2--;
//(Inv == true) & ~B2 (B2 - условие цикла while)
if (ind1 < ind2)
{
Swap(ref arr[ind1], ref arr[ind2]);
ind1++; ind2--;
}
//(Inv ==true)
}
if (ind1 == start)
{
Swap(ref arr[start], ref arr[ind]);
QSort(start + 1, finish);
}
else
{
QSort(start, ind1 - 1);
QSort(ind2 + 1, finish);
}
}
}
//HeapSort - SortTree - PyramidSort
// Рекурсивная поцедура просеивания элемента по древу (пирамиде)
// Основная компонента построения пирамиды для массива
// и построения отсортированного массива по пирамиде
private void Seed(int i)
{
//просеивание элемента с индексом i,
//нарушающего свойство пирамидальности массива
int l = 2 * i + 1, r = l + 1; //индексы левого и правого потомка
if (l > Heap_Size - 1) return; //это лист пирамиды
int cand = i;
if (arr[i] < arr[l]) cand = l;
if ((r <Heap_Size) && (arr[cand] < arr[r])) cand = r;
if (cand != i) //обмен
{
Swap(ref arr[i], ref arr[cand]);
Seed(cand); //Просеивание вниз
}
}
// Преобразует массив arr в пирамиду
// Массив является пирамидой, если для каждого элемента массива,
// не являющегося листом пирамиды, его значение меньше или равно
// значения двух его потомков
private void MakePyramid()
{
int m = (n - 2) / 2;
//m- индекс последнего элемента, имеющего потомков
//элементы с индексами, большими m, являются листьями пирамиды
for (int k = m; k >= 0; k--)
Seed(k);
}
// Пирамидальная сортировка
// Вначале по массиву строится пирамида
// затем по пирамиде строится отсортированный массив
public void PyramidSort()
{
swapCount = 0; // сброс счетчика перед сортировкой
Heap_Size = arr.Length;
MakePyramid();
for (int i = 0; i < n - 1; i++)
{
Swap(ref arr[0], ref arr[Heap_Size - 1]);
Heap_Size--;
Seed(0);
}
}
// Сортировка слиянием
public void SortMerge()
{
swapCount = 0; // сброс счетчика перед сортировкой
int[] temp = new int[arr.Length];
SortM(0, n - 1, temp);
}
// Рекурсивная процедура сортировки слиянием
void SortM(int start, int finish, int[] temp)
{
if (start < finish)
{
int mid = (start + finish) / 2;
SortM(start, mid, temp);
SortM(mid + 1, finish, temp);
Merge(start, mid, finish, temp);
}
}
// Слияние отсортированных частей масссива в массив temp
// После слияния массив переписывается в исходный массив
void Merge(int start, int mid, int finish, int[] temp)
{
int topl = start, topr = mid + 1, topt = start;
//Слияние, пока не завершится одна из частей массива
while ((topl <= mid) && (topr <= finish))
{
if (arr[topl] <= arr[topr])
temp[topt++] = arr[topl++];
else
temp[topt++] = arr[topr++];
}
//дописывание остатка незавершенной части массива
while (topl <= mid)
temp[topt++] = arr[topl++];
while (topr <= finish)
temp[topt++] = arr[topr++];
//переливаем элементы в исходный массив
for (int i = start; i <= finish; i++)
{
if (arr[i] != temp[i]) // считаем только реальные перестановки
{
arr[i] = temp[i];
swapCount++;
}
}
}
// Поиск за линейное время(в среднем) квантили
// массива порядка k.
//При k = n/2 квантиль задает медиану массива.
//порядок квантили returns квантиль порядка k
public int Find(int k)
{
swapCount = 0; // сброс счетчика перед поиском
int l = 0, r = n - 1;
int x = 0;
while (l < r)
{
x = arr[k]; //барьер
//Разбиение на два подмножества
int i = l, j = r;
do
{
while (arr[i] < x) i++;
while (x < arr[j]) j--;
if (i <= j)
{
if (arr[i] != arr[j])
{//обмен
Swap(ref arr[i], ref arr[j]);
}
i++; j--;
}
}
while (i <= j);
//Изменение границ интервала поиска
if (j < k) l = i;
if (k < i) r = j;
}
return (arr[k]);
}
// Подсчет времени сортировки
// Сортируется один и тот же массив 10000 раз
// Метод сортировки передается как параметр
//>Метод сортировки returns время сортировки
private long HowLong(SortMethod sort)
{
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
sort();
stopwatch.Stop();
return stopwatch.ElapsedMilliseconds;
}
//Подсчет количества перестановок сортировки
// Метод сортировки передается как параметр
// Метод сортировки returns количество операций перестановок
private long HowCountSwap(SortMethod sort)
{
// Восстанавливаем исходный массив перед каждой сортировкой
Array.Copy(copyarr, arr, n);
swapCount = 0;
sort();
return swapCount;
}
public Analyse AnalyseSort(SortMethod method)
{
// Восстанавливаем исходный массив перед анализом
Array.Copy(copyarr, arr, n);
long time = HowLong(method);
// Восстанавливаем исходный массив перед подсчетом перестановок
Array.Copy(copyarr, arr, n);
long countSwap = HowCountSwap(method);
return new Analyse(time, countSwap);
}
public Analyse AnalyseTimeQuickSort()
{
Analyse a = AnalyseSort(QuickSort);
return a;
}
public Analyse AnalyseTimeHeapSort()
{
Analyse a = AnalyseSort(PyramidSort);
return a;
}
public Analyse AnalyseTimeMergeSort()
{
Analyse a = AnalyseSort(SortMerge);
return a;
}
}
}
