«Сравнение и анализ алгоритмов сортировки двусвязного списка методом прямого включения»

dat", FileMode::Create);
if (f1->Length > 0) {
int N = f1->Length;
array^ buf = gcnew array(1000);

int L = 1; // Длина отсортированной части
while (L < N) { // Пока не отсортировано все
f2->Seek(0, SeekOrigin::Begin);
f1->Seek(L, SeekOrigin::Begin);
unsigned char V = f1->ReadByte();
// Ищем место вставки и сразу формируем файл с результатом вставки
int pos = 0;
f1->Seek(pos, SeekOrigin::Begin);
while (pos < L) {
unsigned char V1 = f1->ReadByte();
if (V < V1)
break;
f2->WriteByte(V1);
pos++;
}
f2->WriteByte(V);
f1->Seek(pos, SeekOrigin::Begin);
while (pos < L) {
int read = f1->Read(buf, 0, Math::Min(L - pos, buf->Length));
f2->Write(buf, 0, read);
pos += read;
}
pos++;
f1->Seek(pos, SeekOrigin::Begin);
// Дописываем в промежуточный файл неотсортированный остаток
while (pos < N) {
int read = f1->Read(buf, 0, Math::Min(N - pos, buf->Length));
f2->Write(buf, 0, read);
pos += read;
}
L++;
FileStream^ f = f1;
f1 = f2;
f2 = f;
}
if (Path::GetFileName(f1->Name)->Equals("temp.dat")) {
f1->Seek(0, SeekOrigin::Begin);
array^ data = gcnew array(f1->Length);
f1->Read(data, 0, data->Length);
f2->Seek(0, SeekOrigin::Begin);
f2->Write(data, 0, data->Length);
}
}
f2->Close();
f1->Close();
}

}

Файл MyForm.h
#pragma once

#include "sorts.h"

namespace sortings {

using namespace System;
using namespace System::ComponentModel;
using namespace System::Collections;
using namespace System::Windows::Forms;
using namespace System::Data;
using namespace System::Drawing;

///

/// Сводка для MyForm
///

public ref class MyForm : public System::Windows::Forms::Form
{
public:
MyForm(void)
{
InitializeComponent();
//
//TODO: добавьте код конструктора
//
}

protected:
///

/// Освободить все используемые ресурсы.
///

~MyForm()
{
if (components)
{
delete components;
}
}
private: System::Windows::Forms::Button^ btStart;
private: System::Windows::Forms::GroupBox^ groupBox1;



private: System::Windows::Forms::GroupBox^ groupBox2;
private: System::Windows::Forms::RadioButton^ rbPartialSorted;


private: System::Windows::Forms::RadioButton^ rbRevSorted;
private: System::Windows::Forms::RadioButton^ rbSorted;
private: System::Windows::Forms::RadioButton^ rbRandom;
private: System::Windows::Forms::DataVisualization::Charting::Chart^ Chart;



private: System::Windows::Forms::GroupBox^ groupBox3;
private: System::Windows::Forms::CheckedListBox^ cbNums;


private: System::Windows::Forms::DataGridView^ Grid;
private: System::Windows::Forms::CheckedListBox^ cbMethods;
private: System::Windows::Forms::Label^ label2;
private: System::Windows::Forms::NumericUpDown^ nmPercent;

private: System::Windows::Forms::Label^ label1;

protected:

private:
///

/// Обязательная переменная конструктора.
///

System::ComponentModel::Container ^components;

#pragma region Windows Form Designer generated code
///

/// Требуемый метод для поддержки конструктора — не изменяйте
/// содержимое этого метода с помощью редактора кода.
///

void InitializeComponent(void)
{
this->btStart = (gcnew System::Windows::Forms::Button());
this->groupBox1 = (gcnew System::Windows::Forms::GroupBox());
this->cbMethods = (gcnew System::Windows::Forms::CheckedListBox());
this->groupBox2 = (gcnew System::Windows::Forms::GroupBox());
this->label2 = (gcnew System::Windows::Forms::Label());
this->nmPercent = (gcnew System::Windows::Forms::NumericUpDown());
this->label1 = (gcnew System::Windows::Forms::Label());
this->rbPartialSorted = (gcnew System::Windows::Forms::RadioButton());
this->rbRevSorted = (gcnew System::Windows::Forms::RadioButton());
this->rbSorted = (gcnew System::Windows::Forms::RadioButton());
this->rbRandom = (gcnew System::Windows::Forms::RadioButton());
this->Chart = (gcnew System::Windows::Forms::DataVisualization::Charting::Chart());
this->groupBox3 = (gcnew System::Windows::Forms::GroupBox());
this->cbNums = (gcnew System::Windows::Forms::CheckedListBox());
this->Grid = (gcnew System::Windows::Forms::DataGridView());
this->groupBox1->SuspendLayout();
this->groupBox2->SuspendLayout();
(cli::safe_cast(this->nmPercent))->BeginInit();
(cli::safe_cast(this->Chart))->BeginInit();
this->groupBox3->SuspendLayout();
(cli::safe_cast(this->Grid))->BeginInit();
this->SuspendLayout();
//
// btStart
//
this->btStart->Location = System::Drawing::Point(12, 471);
this->btStart->Name = L"btStart";
this->btStart->Size = System::Drawing::Size(223, 28);
this->btStart->TabIndex = 0;
this->btStart->Text = L"Запуск сортировок";
this->btStart->UseVisualStyleBackColor = true;
this->btStart->Click += gcnew System::EventHandler(this, &MyForm::btStart_Click);
//
// groupBox1
//
this->groupBox1->Controls->Add(this->cbMethods);
this->groupBox1->Location = System::Drawing::Point(12, 12);
this->groupBox1->Name = L"groupBox1";
this->groupBox1->Size = System::Drawing::Size(223, 132);
this->groupBox1->TabIndex = 1;
this->groupBox1->TabStop = false;
this->groupBox1->Text = L" Методы сортировки ";
//
// cbMethods
//
this->cbMethods->FormattingEnabled = true;
this->cbMethods->Items->AddRange(gcnew cli::array< System::Object^ >(3) { L"Простым слянием", L"Естественным слиянием", L"Поглощением" });
this->cbMethods->Location = System::Drawing::Point(6, 19);
this->cbMethods->Name = L"cbMethods";
this->cbMethods->Size = System::Drawing::Size(210, 106);
this->cbMethods->TabIndex = 0;
//
// groupBox2
//
this->groupBox2->Controls->Add(this->label2);
this->groupBox2->Controls->Add(this->nmPercent);
this->groupBox2->Controls->Add(this->label1);
this->groupBox2->Controls->Add(this->rbPartialSorted);
this->groupBox2->Controls->Add(this->rbRevSorted);
this->groupBox2->Controls->Add(this->rbSorted);
this->groupBox2->Controls->Add(this->rbRandom);
this->groupBox2->Location = System::Drawing::Point(11, 150);
this->groupBox2->Name = L"groupBox2";
this->groupBox2->Size = System::Drawing::Size(224, 132);
this->groupBox2->TabIndex = 2;
this->groupBox2->TabStop = false;
this->groupBox2->Text = L" Данные ";
//
// label2
//
this->label2->AutoSize = true;
this->label2->Location = System::Drawing::Point(200, 108);
this->label2->Name = L"label2";
this->label2->Size = System::Drawing::Size(19, 16);
this->label2->TabIndex = 8;
this->label2->Text = L"%";
//
// nmPercent
//
this->nmPercent->Location = System::Drawing::Point(142, 105);
this->nmPercent->Minimum = System::Decimal(gcnew cli::array< System::Int32 >(4) { 1, 0, 0, 0 });
this->nmPercent->Name = L"nmPercent";
this->nmPercent->Size = System::Drawing::Size(58, 22);
this->nmPercent->TabIndex = 7;
this->nmPercent->Value = System::Decimal(gcnew cli::array< System::Int32 >(4) { 50, 0, 0, 0 });
//
// label1
//
this->label1->AutoSize = true;
this->label1->Location = System::Drawing::Point(8, 107);
this->label1->Name = L"label1";
this->label1->Size = System::Drawing::Size(127, 16);
this->label1->TabIndex = 6;
this->label1->Text = L"Упорядоченность:";
//
// rbPartialSorted
//
this->rbPartialSorted->AutoSize = true;
this->rbPartialSorted->Location = System::Drawing::Point(8, 80);
this->rbPartialSorted->Name = L"rbPartialSorted";
this->rbPartialSorted->Size = System::Drawing::Size(198, 20);
this->rbPartialSorted->TabIndex = 5;
this->rbPartialSorted->Text = L"Частично упорядоченные";
this->rbPartialSorted->UseVisualStyleBackColor = true;
//
// rbRevSorted
//
this->rbRevSorted->AutoSize = true;
this->rbRevSorted->Location = System::Drawing::Point(8, 60);
this->rbRevSorted->Name = L"rbRevSorted";
this->rbRevSorted->Size = System::Drawing::Size(192, 20);
this->rbRevSorted->TabIndex = 2;
this->rbRevSorted->Text = L"Обратно упорядоченные";
this->rbRevSorted->UseVisualStyleBackColor = true;
//
// rbSorted
//
this->rbSorted->AutoSize = true;
this->rbSorted->Location = System::Drawing::Point(8, 41);
this->rbSorted->Name = L"rbSorted";
this->rbSorted->Size = System::Drawing::Size(133, 20);
this->rbSorted->TabIndex = 1;
this->rbSorted->Text = L"Упорядоченные";
this->rbSorted->UseVisualStyleBackColor = true;
//
// rbRandom
//
this->rbRandom->AutoSize = true;
this->rbRandom->Checked = true;
this->rbRandom->Location = System::Drawing::Point(8, 21);
this->rbRandom->Name = L"rbRandom";
this->rbRandom->Size = System::Drawing::Size(102, 20);
this->rbRandom->TabIndex = 0;
this->rbRandom->TabStop = true;
this->rbRandom->Text = L"Случайные";
this->rbRandom->UseVisualStyleBackColor = true;
//
// Chart
//
this->Chart->Location = System::Drawing::Point(242, 24);
this->Chart->Name = L"Chart";
this->Chart->Size = System::Drawing::Size(804, 313);
this->Chart->TabIndex = 3;
this->Chart->Text = L"Графики времени";
//
// groupBox3
//
this->groupBox3->Controls->Add(this->cbNums);
this->groupBox3->Location = System::Drawing::Point(11, 288);
this->groupBox3->Name = L"groupBox3";
this->groupBox3->Size = System::Drawing::Size(224, 177);
this->groupBox3->TabIndex = 4;
this->groupBox3->TabStop = false;
this->groupBox3->Text = L" Число элементов ";
//
// cbNums
//
this->cbNums->FormattingEnabled = true;
this->cbNums->Items->AddRange(gcnew cli::array< System::Object^ >(7) {
L"500", L"1000", L"5000", L"10000", L"30000", L"40000",
L"50000"
});
this->cbNums->Location = System::Drawing::Point(8, 22);
this->cbNums->Name = L"cbNums";
this->cbNums->Size = System::Drawing::Size(210, 140);
this->cbNums->TabIndex = 0;
//
// Grid
//
this->Grid->ColumnHeadersHeightSizeMode = System::Windows::Forms::DataGridViewColumnHeadersHeightSizeMode::AutoSize;
this->Grid->Location = System::Drawing::Point(242, 344);
this->Grid->Name = L"Grid";
this->Grid->RowHeadersWidth = 51;
this->Grid->RowTemplate->Height = 24;
this->Grid->Size = System::Drawing::Size(804, 150);
this->Grid->TabIndex = 5;
//
// MyForm
//
this->AutoScaleDimensions = System::Drawing::SizeF(8, 16);
this->AutoScaleMode = System::Windows::Forms::AutoScaleMode::Font;
this->ClientSize = System::Drawing::Size(1058, 507);
this->Controls->Add(this->Grid);
this->Controls->Add(this->groupBox3);
this->Controls->Add(this->Chart);
this->Controls->Add(this->groupBox2);
this->Controls->Add(this->groupBox1);
this->Controls->Add(this->btStart);
this->FormBorderStyle = System::Windows::Forms::FormBorderStyle::FixedSingle;
this->MaximizeBox = false;
this->Name = L"MyForm";
this->StartPosition = System::Windows::Forms::FormStartPosition::CenterScreen;
this->Text = L"Внешние сортировки";
this->groupBox1->ResumeLayout(false);
this->groupBox2->ResumeLayout(false);
this->groupBox2->PerformLayout();
(cli::safe_cast(this->nmPercent))->EndInit();
(cli::safe_cast(this->Chart))->EndInit();
this->groupBox3->ResumeLayout(false);
(cli::safe_cast(this->Grid))->EndInit();
this->ResumeLayout(false);

}
#pragma endregion
// Вызывается при нажатии кнопки запуска
private: System::Void btStart_Click(System::Object^ sender, System::EventArgs^ e) {
// Считаем количество методов
int nMethods = 0;
for (int i = 0; i < cbMethods->Items->Count; i++) {
if (cbMethods->GetItemChecked(i))
nMethods++;
}
// Считаем количество градаций размера
int nNums = 0;
for (int i = 0; i < cbNums->Items->Count; i++) {
if (cbNums->GetItemChecked(i))
nNums++;
}
// Настраиваем таблицу с результатами
if (nMethods == 0) { // Если не заданы методы
MessageBox::Show("Не выбрано ни одного метода");
return; // то выходим
}
if (nNums == 0) { // Если не заданы количества
MessageBox::Show("Не выбрано ни одного количества элементов данных");
return; // то выходим
}
Grid->Rows->Clear();
if (nMethods == 0)
nMethods = 1;
if (nNums == 0)
nNums = 1;
// Настраиваем график
Grid->RowCount = nMethods;
Grid->ColumnCount = nNums;
Chart->Series->Clear();
Chart->ChartAreas->Clear();
Chart->ChartAreas->Add("Main");
Chart->Legends->Clear();
Chart->Legends->Add("MainLegend");
for (int i = 0; i < cbMethods->Items->Count; i++) {
if (cbMethods->GetItemChecked(i)) {
Chart->Series->Add(cbMethods->Items[i]->ToString());
Chart->Series[Chart->Series->Count - 1]->ChartType = System::Windows::Forms::DataVisualization::Charting::SeriesChartType::Line;
}
}
// Цикл по количествам элементов
int column = 0;
for (int i = 0; i < cbNums->Items->Count; i++)
if (cbNums->GetItemChecked(i)) {
int N = Convert::ToInt32(cbNums->Items[i]); // Число элементов
FileStream^ SRC = gcnew FileStream("src.dat", FileMode::Create); // Исходная последовательность
Random^ rnd = gcnew Random();
if (rbPartialSorted->Checked) { // Частичная упорядоченность
// Длина каждого упорядоченного участка
int part_length = 1 + (N - 1) * Convert::ToInt32(nmPercent->Value) / 100;
int count = 0;
while (count < N) {
unsigned char val = 0;
SRC->WriteByte(val);
count++;
int rest = part_length - 1;
// Создаем прочие элементы упорядоченного участка
while (rest > 0 && count < N) {
val = (part_length - rest) * 255 / part_length;
SRC->WriteByte(val);
rest--;
count++;
}
}
}
else { // Прочие виды набора данных
for (int i = 0; i < N; i++) {
unsigned char val =
rbSorted->Checked ? i*255/N :
(rbRevSorted->Checked ? (N - i)*255/N :
rnd->Next(256));
SRC->WriteByte(val);
}
}
SRC->Close();
Grid->Columns[column]->HeaderText = cbNums->Items[i]->ToString();
int row = 0;
// Цикл по методам
for (int j = 0; j < cbMethods->Items->Count; j++) {
if (cbMethods->GetItemChecked(j)) {
File::Copy("src.dat", "processing.dat", true);
DateTime^ dt = DateTime::Now; // ЗАсечка времени
// Сортировка j-м методом
switch (j) {
case 0:
simple_merge_sort("processing.dat");
break;
case 1:
nature_merge_sort("processing.dat");
break;
case 2:
eating_sort("processing.dat");
break;
}
// Считаем затраченное время
DateTime^ dt2 = DateTime::Now; // ЗАсечка времени
int time = Convert::ToInt32((dt2->Subtract(*dt)).Milliseconds);
// Заносим время в таблицу
Grid->Rows[row]->Cells[column]->Value = time;
Grid->Rows[row]->HeaderCell->Value = cbMethods->Items[j]->ToString();
// Отмечаем время на графике
Chart->Series[row]->Points->AddXY(N, time);
row++;
}
}
column++;
}
Grid->RowHeadersWidth = Grid->Width / 3;
}
};
}








5

Показать больше