Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Харьков 2014

1. Задание:

1. Разработать проект для исследования алгоритмов сортировки в соответствии с вариантом (сортировка простыми включениями (простой вставкой),шейкер-сортировка). Интервал: [0,200].

2. Разработать интерфейс проекта, позволяющий:

- задавать размерность и качество массива;

- осуществлять выбор алгоритма сортировки для исследования;

- осуществлять вывод информации о результатах исследования алгоритма сортировки (исходный и отсортированный массив, пошаговую работу алгоритма сортировки (при небольшой размерности массива), показатели качества работы алгоритма сортировки).

3. Создать подпрограмму для генерации целочисленного массива различного качества. В подпрограмме предусмотреть:

- задание размерности массива;

- задание диапазона чисел массива;

- создание массива с равномерно распределенными случайными числами;

- создание упорядоченного по возрастанию массива;

- создание упорядоченного по убыванию массива.

4. Создать подпрограмму, реализующую алгоритм сортировки в соответствии с вариантом. В подпрограмме предусмотреть:

- определение числа сравнений;

- определение числа обменов;

- определение суммы обменов и сравнений;

- сортировку массива по возрастанию.

2.Математическая постановка задачи:

Задача сортировки состоит в следующем: пусть дана последовательность из n элементов принадлежащих некоторому множеству а, на котором задано отношение всеобщего порядка “<=”. Найти перестановку этих элементов в таком порядке ak1,…akn, при котором будет справедливо отношение ak1<=ak2<=…akn.

3.Текст программы:

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

namespace Lab1_MSD

{

public partial class Form1: Form

{

List<int> array = new List<int>();

public Form1()

{

InitializeComponent();

cmbGenerate.SelectedIndex = 0;

cmbType.SelectedIndex = 0;

}

private void button1_Click(object sender, EventArgs e)

{

Random rnd = new Random();

int count = (int)numCount.Value;

array = new List<int>();

for (int i = 0; i < count; i++)

{

array.Add(rnd.Next((int)numMin.Value, (int)numMax.Value));

}

if (cmbGenerate.SelectedIndex == 1)

{

array.Sort();

}

else if (cmbGenerate.SelectedIndex == 2)

{

array.Sort();

array.Reverse();

}

ShowArray(txtGenerate);

btnSort.Enabled = true;

txtView.Text = "";

}

void ShowArray(TextBox textbox)

{

textbox.Text = "";

foreach (int item in array)

{

textbox.Text += item + " ";

}

}

private void button1_Click_1(object sender, EventArgs e)

{

txtSteps.Text = "";

if (cmbType.SelectedIndex == 0) //выбрана сортировка простыми включениями

{

int tmp; //temp variable

int comparisons = 0; // количество сравнений

int exchanges = 0; // количество обменов

for (int i = 1; i < (int)numCount.Value; ++i)

{

tmp = array[i];

for (int j = i - 1; (j >= 0); --j)

{

comparisons++;

if (array[j] > tmp)// сравнение

{

exchanges++; // обмен

array[j + 1] = array[j];

array[j] = tmp;

}

else

break;

foreach (int item in array)

{

txtView.Text += item + " ";

}

txtView.Text += "\n";

}

}

ShowArray(txtSort);

txtSteps.Text += "Сравнений: " + comparisons.ToString() + Environment.NewLine;

txtSteps.Text += "Обменов: " + exchanges.ToString() + Environment.NewLine;

txtSteps.Text += "Операций: " + (comparisons + exchanges).ToString();

}

else if (cmbType.SelectedIndex == 1) //выбрана шейкер-сортировка

{

int i, left, right, a, tmp, comparisons = 0, exchanges = 0;

for (right = (int)numCount.Value - 1, left = 0, a = -1; a!= 0;)//определяем правую и левую границу

{

a = 0;

for (i = left; i < right; i++)//слева направо

{

comparisons++;

if (array[i] > array[i + 1]) //сравнения

{

exchanges++; //обмен

tmp = array[i];

array[i] = array[i + 1];

array[i + 1] = tmp;

a = i;

}

}

right = a;

for (i = right; i > left; i--)//справа налево

{

comparisons++;

if (array[i - 1] > array[i]) //сравнения

{

exchanges++; //обмен

tmp = array[i];

array[i] = array[i - 1];

array[i - 1] = tmp;

a = i;

}

}

left = a;

foreach (int item in array)

{

txtView.Text += item + " ";

}

txtView.Text += "\n";

}

ShowArray(txtSort);

txtSteps.Text += "Сравнений: " + comparisons.ToString() + Environment.NewLine;

txtSteps.Text += "Обменов: " + exchanges.ToString() + Environment.NewLine;

txtSteps.Text += "Операций: " + (comparisons + exchanges).ToString();

}

}

}

}

4.Исследование программной реализации простых алгоритмов сортировки:

4.1. Примеры пошаговой работы:

4.2. Зависимость количества сравнений, обменов и их суммы исследуемых алгоритмов сортировки от размерности задачи n для прямого, обратного, случайного и равного расположения элементов в массиве:

Таблица 1 Сортировка простыми включениями, массив упорядочен случайно

Таблица 2 Сортировка простыми включениями, массив упорядочен по возрастанию

Таблица 3 Сортировка простыми включениями, массив упорядочен по убыванию

Таблица 4 Шейкер-сортировка, массив упорядочен случайно

Таблица 5 Шейкер-сортировка, массив упорядочен по возрастанию

Таблица 6 Шейкер-сортировка, массив упорядочен по убыванию

4.3. Графики зависимости показателя качества исследуемых алгоритмов сортировки:

Рисунок 1 – График,при котором исходный массив распределен хаотически

Рисунок 2 – График, при котором исходный массив распределен по возрастанию

Рисунок 3 – График, при котором исходный массив распределен по убыванию

5.Выводы:

Выполнив лабораторную работу и проанализировав полученные данные, можно судить о том, какой алгоритм и при каком распредлении массива чисел эффективнее.Выяснилось, что для массива со случайным распределением чисел и для массива,уорядоченного по убыванию,сортировка простыми включениями является лучше в виду того,что требуется меньшее количество операций. Для массива, упорядоченного по возрастанию, сортировка простыми включениями и сортировка-шейкером привела к одинаковому количеству операций.Для алгоритма сортировки простыми вставками характерным является зависимость числа операций от качества массива,как и для шейкер-сортировки,но при сравнении двух алгоритмов, для сортировки простыми включениями необходимо меньшее количество операций. Не смотря на то,что сложность алгоритма O(n²), алгоритм описывает устойчивую сортировку, так как оставляет неизменным порядок элементов с одинаковыми значениями,что является определенным достоинством этого алгоритма.Что касается шейкер-сортировки,то он проигрывает в эффективности в виду того,что на каждом элементарном шаге сортировки элементы перемещаются только на одну позицию, что в общем случае приводит к большому количеству присваиваний.