Материал: Исследование методов сортировки выбором

Затем, в ходе выполнения программы производится проверка полноты и корректности введенных начальных данных. Если исходные данные не прошли проверку - выводится соответствующее уведомление.

После успешно пройденной проверки, программа начинает сортировать полученные данные. Программа считывает данные, заполненные в специальных полях и производит сортировку по установленным алгоритмам.

После этого результаты выводятся в специально отведенное поле, а выполнение программы прекращается.

2.2 Макет приложения

Макет приложения «Методы сортировок выбором»(Form1)

richTextBox1 - получает введенный пользователем массив, либо автоматически генерируемый с помощью кнопки «Сгенерировать»

button1 - принимает текстовое значение «Сгенерировать», а также генерирует в поле richTextBox1 рандомный массив от 0 до 100.

comboBox1 - содержит список, предоставляющий пользователю выбрать методы сортировки данных массива. Содержит текстовые значения: «Пирамидальная сортировка», «Плавная сортировка», «сортировка Выбором».

button2 - принимает текстовое значение «Сортировать», а также сортирует введенные или сгенерированные пользователем данные из richTextBox1.

richTextBox2 - служит для вывода результатов сортировки тем или иным выбранным методом.

2.3 Описание программы

Иерархия классов

using System;

using System.Collections.Generic;System.ComponentModel;System.Data;System.Drawing;System.Linq;System.Text;System.Threading.Tasks;System.Windows.Forms;

Используемые элементы

Обработчики событийvoid button1_Click(object sender, EventArgs e)void button2_Click(object sender, EventArgs e)

Функции

В данной курсовой используется 3 основных и 4 вспомогательных функции.

Функция Print отвечает за вывод результата, предварительно отсортированного выбранным методом и передает результат в поле вывода.

private void Print(int[] array) // результат

{.Clear(); // очищение поля(var x in array) // перебор в переменную х всех значений массива array, в который записывается результат сортировки выбранным методом.Text += x + “” // добавление этих значений

}

Рисунок.6 Результат работы функции Print.

Функция selectSort производит сортировку по алгоритму «Выборка» и передает отсортированный массив в функцию Printvoid selectSort(int[] array) // сортировка выборкой

{min; // объявляем min(int i = 0; i < array.Length; i++) // перебираем элементы

{= i; // присваиваем наименьший элемент i-ому

for (int j = i + 1; j < array.Length; j++)

if (array[j] < array[min]) // если элменент массива меньше минимального= j; // присваиваем новое минимальное значение элементу массиву

// swap-функция. Меняем местами значения

int temp = array[i]

array[i] = array[min];[min] = temp;

}

}

Рисунок.7 Результат работы функции selectSort

Функция heapSort производит сортировку по алгоритму «Пирамида» и передает отсортированный массива в функцию Printvoid heapSort(int[] array) // сортировка пирамидой

{i, temp; // объявляем переменные

for (i = array.Length / 2 - 1; i >= 0; i--) // элементы с номерами начиная с array.Length / 2 - 1 это листья, то тогда нужно переупорядочить поддеревья с корнями в индексах(array, i, array.Length - 1); // вызывается функция downHeap и ей передаются аргументы

for (i = array.Length - 1; i > 0; i--)

{= array[i];[i] = array[0];[0] = temp;(array, 0, i - 1); // в функцию передаются аргументы с шагом - 1

}

}

Рисунок.8 Результат работы функции heapSort

Функция smoothSort производит сортировку по алгоритму «Плавная» и передает отсортированный массив в функцию Print.void smoothSort(int[] mas) // функция плавная сортировки

{_heap_pool(mas); // вызов функции, создающей последовательность куч из произвольного массива

for (int i = mas.Length - 1; i >= 0; i--)

{nextPosHeapItemsAmount = 0;posMaxTopElem = findPosMaxElem(mas, curState, i, ref nextPosHeapItemsAmount); // максимальный верхний элемент кучи получает значение в виде результата функции findPosMaxElem(posMaxTopElem != i)

{(ref mas[i], ref mas[posMaxTopElem]); // вызываем функцию swap и передаем в нее значения mas[i] и mas[posMaxTopElem](mas, nextPosHeapItemsAmount, posMaxTopElem); // вызываем функцию

}(ref curState); // вызываем функцию PreveState и передаем значения, ссылаясь(ref) на значение переменной curState

}

}

программа сортировка пирамида выбор

Рисунок.9 Результат работы функции smoothSort

Функция downHeap является вспомогательной функцией для heapSort, обеспечивая нижнюю сортировку кучи массива

private void downHeap(int[] array, int k, int n) // функция нижней сортировки

{

// объявляем переменные

int new_elem;

int child;_elem = array[k]; (k <= n / 2) // пока у array[k] есть дети выполняем

{= 2 * k;

// выбираем большего сына(child < n && array[child] < array[child + 1])++;(new_elem >= array[child]) break;

// иначе[k] = array[child]; // переносим сына наверх= child;

}[k] = new_elem;

}

Функция NextState является вспомогательной функцией. Делает обратную операцию, но при этом она еще возвращает номер бита, соответствующий вершине последней кучи, если та состоит более чем из одного элемента. В противном случае функция возвращает -1.int NextState(ref int curState) // Функция NextState, делает обратную операцию, но при этом она еще возвращает номер бита, соответствующий вершине последней кучи, если та состоит более чем из одного элемента. В противном случае функция возвращает -1.

{posNewTop = -1; // позиция вершины объединенных куч.

// исключение((curState & 7) == 5)

{ // curState = 0101+= 3; // curState = 1000 = 3;

}

else // пытаемся найти два подряд единичных бита

{next = curState;pos = 0;(next != 0 && (next & 3) != 3)

{>>= 1;++

{+= 1 << pos; // curState = 10000= pos + 2;

}if ((curState & 1) != 0) // curState = x001|= 2; // curState = x011// curState = xx00|= 1; // curState = xx01

}posNewTop;

}

Функция PrevState является вспомогательной функцией. Она изменяет текущее состояние с учетом того, что вершина последней кучи исключена из рассмотрения.void PrevState(ref int curState) //Функция PrevState изменяет текущее состояние с учетом того, что вершина последней кучи исключена из рассмотрения.

{((curState & 15) == 8)

{ // curState = 1000-= 3; // curState = 010

}

еlse if ((curState & 1) != 0)

{((curState & 3) == 3) // curState = x011^= 2; // curState = x001// curState = xx01^= 1; // curState = xx00

}// ищим первый единичный бит

{prev = curState;pos = 0;(prev != 0 && !(Convert.ToBoolean(prev & 1)))

{>>= 1;++;

}(prev != 0) // curState = xx10000

{^= 1 << pos;|= 1 << (pos - 1);|= 1 << (pos - 2); // curState = xx01100

}

else

curState = 0;

}

}

Функция shiftDown является вспомогательной функцией. Она реализует просеивание данных массива «вниз»void shiftDown(int[] mas, int posHeapItemsAmount, int indexLastTop) // Реализация функции просейки вниз, в ней задается также mas[]

{posCurNode = indexLastTop; //indexLastTop - индекс крайней вершин(posHeapItemsAmount > 1) //nextPosHeapItemsAmount - количество элементво в кучи, вершина которой оказалось максимальной из всех вершин куч

{

// позиция правого сынаposR = posCurNode - 1;

// позиция левого сынаposL = posR - LeoNum[posHeapItemsAmount - 2]; // число элементов в текущей кучи

int posMaxChild = posL;posNextTop = posHeapItemsAmount - 1;

if (mas[posR] > mas[posL]) // если позиция правого сына больше левого

{= posR; // то "старший сын" правый

posNextTop = posHeapItemsAmount - 2;

}(mas[posCurNode] < mas[posMaxChild])

{(ref mas[posCurNode], ref mas[posMaxChild]);= posNextTop;= posMaxChild;

};

}

}

Функция make_heap_pool является вспомогательной функцией. Она создает последовательности куч из произвольного массива.void make_heap_pool(int[] mas) // Функция создания последовательности куч из произвольного массива.

{(int i = 0; i < mas.Length; i++)

{posHeapItemsAmount = NextState(ref curState);(posHeapItemsAmount != -1)(mas, posHeapItemsAmount, i);

}

}

Функция findPosMaxElem является вспомогательной функцией. Она ищет максимальный элемент среди вершин куч.int findPosMaxElem(int[] mas, int curState, int indexLastTop, ref int nextPosHeapItemsAmount) // Функция поиска максимального элемента среди вершин куч

{pos = 0;

// ищим позицию первого единичного бита

while (!Convert.ToBoolean(curState & 1))

{>>= 1;++;

}posMaxTopElem = indexLastTop;= pos;curTopElem = indexLastTop - LeoNum[pos];>>= 1;++;(curState != 0)

{((curState & 1) != 0)

{(mas[curTopElem] > mas[posMaxTopElem])

{= curTopElem;= pos;

}-= LeoNum[pos];

}>>= 1;++;

}posMaxTopElem;

}

Функция swap является вспомогательной функцией. Она выполняет переприсваивание значений.

private void swap(ref int a, ref int b) // функция переприсваивания (swap)

{temp = b;= a;

a = temp;

}

2.4 Руководство пользователя

. Для корректной работы программы необходимо заполнить вручную или сгенерировать с помощью кнопки массив данных.

. Чтобы автоматически заполнить массив данных нажмите кнопку «Сгенерировать»

. Необходимо в раскрывающемся списке выбрать подходящий вам метод сортировки.

. Для получения результата сортировки нажмите кнопку «Сортировать»

ЗАКЛЮЧЕНИЕ

Язык программирования C# на основе Visual Studio способен реализовать все необходимые средства для сортировки данных.

Во время выполнения поставленной задачи были улучшены навыки программирования, работы с методами сортировок. Разработанная программа наглядно демонстрирует реализацию 3 методов сортировки. Основное преимущество программы - выполнение сортировки динамически задаваемых данных.

Был проведен анализ предметной области, выявлены требования к разрабатываемой программе, было спроектировано и реализовано приложение, определена эффективность разработки.

Программа корректна.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Плавная сортировка // Информационный ресурс Википедиа [Электронный ресурс] Режим доступа: https://ru.wikipedia.org/wiki/Плавная_сортировка - Загл с экрана Яз. рус., англ.

. Пирамидальная сортировка // Информационный ресурс Википедиа [Электронный ресурс] Режим доступа: https://ru.wikipedia.org/wiki/Пирамидальная_сортировка - Загл с экрана Яз. рус., англ.

. Сортировка выбором // Информационный ресурс Википедиа [Электронный ресурс] Режим доступа: https://ru.wikipedia.org/wiki/Сортировка_выбором - Загл с экрана Яз. рус., англ.

. Герберт Шилдт, C# 4.0 Полное руководство, учебное пособие [Текст] // Герберт Шилдт. - Московский дом книги, 2008. - 340с.

ПРИЛОЖЕНИЕ-ЛИСТИНГ ПРОГРАММЫ

using System;

using System.Collections.Generic;System.ComponentModel;System.Data;System.Drawing;System.Linq;System.Text;System.Threading.Tasks;System.Windows.Forms;ApplicationSort

{partial class Form1 : Form

{Form1()

{();.DropDownStyle = ComboBoxStyle.DropDownList;.SelectedIndex = 0;

}void button1_Click(object sender, EventArgs e) // задать рандом

{rand = new Random();.Clear();(int i = 0; i < 100; i++).Text += rand.Next(0, 100) + “”;

}void button2_Click(object sender, EventArgs e)

{

{

// присваиваем int[]arr значения введенные или сгенерированные

int[] arr = richTextBox1.Text.(new char[] { ‘ ’ }, StringSplitOptions.RemoveEmptyEntries)

.Select(x => int.Parse(x))//используем LINQ, для удобства конвертации string -> int

.ToArray();

// значения индекса соответствует вызову определенного метода.

int k = comboBox1.SelectedIndex;(k == 0)

heapSort(arr); // выбираем метод сортировки пирамидойif (k == 1)(arr); // выбираем сортировку выборкой(arr); // выбираем плавную сортировку(arr); // вывод результата

// обработка исключений

}(ArgumentNullException ex) // если значения принимают недопустимый аргумент

{.Show(ex.Message);

}(FormatException)

{.Show(“Вводите только целые числа”);

}(Exception exp) // исключения, которые могут возникунть во время выполнения программы

{.Show(exp.Message);

}

}void Print(int[] array) // результат

{.Clear(); // очищение поля(var x in array) // перебор в переменную х всех значений массива array, в который записывается результат сортировки выбранным методом.Text += x + “ “; // добавление этих значений

}void selectSort(int[] array) // сортировка выборкой

{min; // объявляем min(int i = 0; i < array.Length; i++) // перебираем элементы

{= i; // присваиваем наименьший элемент i-ому

for (int j = i + 1; j < array.Length; j++)

if (array[j] < array[min]) // если элменент массива меньше минимального= j; // присваиваем новое минимальное значение элементу массиву

// swap-функция. Меняем местами значенияtemp = array[i];

array[i] = array[min];[min] = temp;

}

}void heapSort(int[] array) // сортировка пирамидой

{i, temp; // объявляем переменные(i = array.Length / 2 - 1; i >= 0; i--) // элементы с номерами начиная с array.Length / 2 - 1 это листья, то нужно переупорядочить поддеревья с корнями в индексах(array, i, array.Length - 1); // вызывается функция downHeap и ей передаются аргументы

for (i = array.Length - 1; i > 0; i--)

{= array[i];[i] = array[0];[0] = temp;(array, 0, i - 1); // в функцию передаются аргументы с шагом - 1

}

}void downHeap(int[] array, int k, int n) // функция нижней сортировки

{

// объявляем переменныеnew_elem;

int child;_elem = array[k];

while (k <= n / 2) // пока у array[k] есть дети выполняем

{= 2 * k;

// выбираем большего сына(child < n && array[child] < array[child + 1])++;(new_elem >= array[child]) break;

// иначе[k] = array[child]; // переносим сына наверх= child;

}[k] = new_elem;

}

// принцип формирования чисел Леонардо L(N) = L(N-1) + L(N-2) + 1[] LeoNum = { 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891, 35421, 57313, 92735, 150049, 242785, 392835, 635621, 1028457, 1664079, 2692537, 4356617, 7049155, 11405773, 18454929, 29860703, 48315633, 78176337, 126491971, 204668309, 331160281, 535828591, 866988873, 1402817465 }; // числа леонардоcurState; // Переменная curState - это текущее состояние последовательности куч, двоичное представление которой задает размерности этих куч.

// Двоичное представление числа curState является описанием

// текущего состояния массива куч.

// Двоичное представление: 10110

// Числа Леонардо 95311

// Т.е. первые 9 элементов - это первая кучу, вторые 3 - вторая куча,

// и последний - это третья куча

// После выполнение функции число curState будет описывать массив куч после добавления

// одного элемента в конец. Его двоичное представление будет 11000 = 24.

// Результат: Номер бита, соответствующий вершине последней кучи, если та состоит более,

// чем из одного элементаint NextState(ref int curState) // Функция NextState, делает обратную операцию, но при этом она еще возвращает номер бита, соответствующий вершине последней кучи, если та состоит более чем из одного элемента. В противном случае функция возвращает -1.

{posNewTop = -1; // позиция вершины объединенных куч.

// исключение((curState & 7) == 5)

{ // curState = 0101+= 3; // curState = 1000 = 3;

}// пытаемся найти два подряд единичных бита

{next = curState;pos = 0;(next != 0 && (next & 3) != 3)

{>>= 1;++;

}((next & 3) == 3) // curState = 01100

{+= 1 << pos; // curState = 10000= pos + 2;

}if ((curState & 1) != 0) // curState = x001|= 2; // curState = x011// curState = xx00|= 1; // curState = xx01

}void PrevState(ref int curState) //Функция PrevState изменяет текущее состояние с учетом того, что вершина последней кучи исключена из рассмотрения.

{((curState & 15) == 8)

{ // curState = 1000-= 3; // curState = 0101

}if ((curState & 1) != 0)

{((curState & 3) == 3) // curState = x011^= 2; // curState = x001// curState = xx01^= 1; // curState = xx00

}// ищим первый единичный бит

{prev = curState;pos = 0;(prev != 0 && !(Convert.ToBoolean(prev & 1)))

{>>= 1;++;

}(prev != 0) // curState = xx10000

{^= 1 << pos;|= 1 << (pos - 1);|= 1 << (pos - 2); // curState = xx01100

}= 0;

}

}void shiftDown(int[] mas, int posHeapItemsAmount, int indexLastTop) // Реализация функции просейки вниз, в ней задается также mas[]

{posCurNode = indexLastTop; //indexLastTop - индекс крайней вершины

while (posHeapItemsAmount > 1) //nextPosHeapItemsAmount - количество элементво в кучи, вершина которой оказалось максимальной из всех вершин куч

{

// позиция правого сынаposR = posCurNode - 1;

// позиция левого сынаposL = posR - LeoNum[posHeapItemsAmount - 2]; // число элементов в текущей кучи

int posMaxChild = posL;posNextTop = posHeapItemsAmount - 1;

if (mas[posR] > mas[posL]) // если позиция правого сына больше левого

{= posR; // то "старший сын" правый

posNextTop = posHeapItemsAmount - 2;

}(mas[posCurNode] < mas[posMaxChild])

{(ref mas[posCurNode], ref mas[posMaxChild]);= posNextTop;= posMaxChild;

};

}

}void make_heap_pool(int[] mas) // Функция создания последовательности куч из произвольного массива.

{(int i = 0; i < mas.Length; i++)

{posHeapItemsAmount = NextState(ref curState);(posHeapItemsAmount != -1)(mas, posHeapItemsAmount, i);

}

}

// Среди вершин куч находим максимальный элемент

// mas - массив

// curState - число, двоичное представление которого описывает текущий массив куч