Заключение.
Исследование методов сортировки выбором

РефератПомощь в написанииУзнать стоимостьмоей работы

Пирамидальная сортировка // Информационный ресурс Википедиа Режим доступа: https://ru.wikipedia.org/wiki/Пирамидальная_сортировка — Загл с экрана Яз. рус., англ. For (i = array. Length / 2 — 1; i ≥ 0; i—) // элементы с номерами начиная с array. Length / 2 — 1 это листья, то нужно переупорядочить поддеревья с корнями в индексах. Int curState; // Переменная curState — это текущее состояние… Читать ещё >

Заключение. Исследование методов сортировки выбором (реферат, курсовая, диплом, контрольная)

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

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

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

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

Список использованных источников

1. Плавная сортировка // Информационный ресурс Википедиа [Электронный ресурс] Режим доступа: https://ru.wikipedia.org/wiki/Плавная_сортировка — Загл с экрана Яз. рус., англ.
2. Пирамидальная сортировка // Информационный ресурс Википедиа [Электронный ресурс] Режим доступа: https://ru.wikipedia.org/wiki/Пирамидальная_сортировка — Загл с экрана Яз. рус., англ.
3. Сортировка выбором // Информационный ресурс Википедиа [Электронный ресурс] Режим доступа: https://ru.wikipedia.org/wiki/Сортировка_выбором — Загл с экрана Яз. рус., англ.
4. Герберт Шилдт, C# 4.0 Полное руководство, учебное пособие [Текст] // Герберт Шилдт. — Московский дом книги, 2008. — 340с.
5. Дональд Кнут, Искусство программирования, том 3. Сортировка и поиск [Текст] // Дональд Кнут. — Вильямс, 2007. — 457с.

Приложение

Листинг программы

using System;

using System.Collections.Generic;

using System. ComponentModel;

using System. Data;

using System. Drawing;

using System. Linq;

using System. Text;

using System.Threading.Tasks;

using System.Windows.Forms;

namespace ApplicationSort.

public partial class Form1: Form.

public Form1().

InitializeComponent ();

comboBox1.DropDownStyle = ComboBoxStyle. DropDownList;

comboBox1.SelectedIndex = 0;

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

Random rand = new Random ();

richTextBox1.Clear ();

for (int i = 0; i < 100; i++).

richTextBox1.Text += rand. Next (0, 100) + ««;

private void button2_Click (object sender, EventArgs e).

try.

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

int[] arr = richTextBox1.Text.

Split (new char[] { ` ' }, StringSplitOptions. RemoveEmptyEntries).

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

.ToArray ();

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

int k = comboBox1. SelectedIndex;

if (k == 0).

heapSort (arr); // выбираем метод сортировки пирамидой.

else if (k == 1).

selectSort (arr); // выбираем сортировку выборкой.

else.

smoothSort (arr); // выбираем плавную сортировку.

Print (arr); // вывод результата.

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

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

MessageBox.Show (ex.Message);

catch (FormatException).

MessageBox.Show («Вводите только целые числа»);

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

MessageBox.Show (exp.Message);

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

richTextBox2.Clear (); // очищение поля.

foreach (var x in array) // перебор в переменную х всех значений массива array, в который записывается результат сортировки выбранным методом.

richTextBox2.Text += x + ««; // добавление этих значений.

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

int min; // объявляем min.

for (int i = 0; i < array. Length; i++) // перебираем элементы.

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

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

if (array[j] < array[min]) // если элменент массива меньше минимального.

min = j; // присваиваем новое минимальное значение элементу массиву.

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

int temp = array[i];

array[i] = array[min];

array[min] = temp;

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

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

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

downHeap (array, i, array. Length — 1); // вызывается функция downHeap и ей передаются аргументы.

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

temp = array[i];

array[i] = array[0];

array[0] = temp;

downHeap (array, 0, i — 1); // в функцию передаются аргументы с шагом — 1.

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

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

int new_elem;

int child;

new_elem = array[k];

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

child = 2 * k;

// выбираем большего сына.

if (child < n && array[child] < array[child + 1]).

child++;

if (new_elem >= array[child]) break;

// иначе.

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

k = child;

array[k] = new_elem;

// принцип формирования чисел Леонардо L (N) = L (N-1) + L (N-2) + 1.

int[] LeoNum = { 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13 529, 21 891, 35 421, 57 313, 92 735, 150 049, 242 785, 392 835, 635 621, 1 028 457, 1 664 079, 2 692 537, 4 356 617, 7 049 155, 11 405 773, 18 454 929, 29 860 703, 48 315 633, 78 176 337, 126 491 971, 204 668 309, 331 160 281, 535 828 591, 866 988 873, 1 402 817 465 }; // числа леонардо.

int curState; // Переменная curState — это текущее состояние последовательности куч, двоичное представление которой задает размерности этих куч.

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

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

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

// Числа Леонардо 95 311.

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

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

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

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

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

// чем из одного элемента.

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

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

// исключение.

if ((curState & 7) == 5).

{ // curState = 0101.

curState += 3; // curState = 1000.

posNewTop = 3;

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

int next = curState;

int pos = 0;

while (next ≠ 0 && (next & 3) ≠ 3).

next >>= 1;

pos++;

if ((next & 3) == 3) // curState = 1 100.

curState += 1 << pos; // curState = 10 000.

posNewTop = pos + 2;

else if ((curState & 1) ≠ 0) // curState = x001.

curState |= 2; // curState = x011.

else // curState = xx00.

curState |= 1; // curState = xx01.

return posNewTop;

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

if ((curState & 15) == 8).

{ // curState = 1000.

curState -= 3; // curState = 0101.

else if ((curState & 1) ≠ 0).

if ((curState & 3) == 3) // curState = x011.

curState ^= 2; // curState = x001.

else // curState = xx01.

curState ^= 1; // curState = xx00.

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

int prev = curState;

int pos = 0;

while (prev ≠ 0 && !(Convert.ToBoolean (prev & 1))).

prev >>= 1;

pos++;

if (prev ≠ 0) // curState = xx10000.

curState ^= 1 << pos;

curState |= 1 << (pos — 1);

curState |= 1 << (pos — 2); // curState = xx01100.

else.

curState = 0;

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

int posCurNode = indexLastTop; //indexLastTop — индекс крайней вершины.

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

// позиция правого сына.

int posR = posCurNode — 1;

// позиция левого сына.

int posL = posR — LeoNum[posHeapItemsAmount — 2]; // число элементов в текущей кучи.

int posMaxChild = posL;

int posNextTop = posHeapItemsAmount — 1;

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

posMaxChild = posR; // то «старший сын» правый.

posNextTop = posHeapItemsAmount — 2;

if (mas[posCurNode] < mas[posMaxChild]).

swap (ref mas[posCurNode], ref mas[posMaxChild]);

posHeapItemsAmount = posNextTop;

posCurNode = posMaxChild;

else.

break;

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

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

int posHeapItemsAmount = NextState (ref curState);

if (posHeapItemsAmount ≠ -1).

shiftDown (mas, posHeapItemsAmount, i);

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

// mas — массив.

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

// indexLastTop — индекс крайней вершины.

// nextPosHeapItemsAmount — количество элементво в кучи, вершина которой оказалось максимальной из всех вершин куч.

// Возврат: индекс элемента (одной из вершин кучи), который больше чем остальные вершины куч.

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

int pos = 0;

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

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

curState >>= 1;

pos++;

int posMaxTopElem = indexLastTop;

nextPosHeapItemsAmount = pos;

int curTopElem = indexLastTop — LeoNum[pos];

curState >>= 1;

pos++;

while (curState ≠ 0).

if ((curState & 1) ≠ 0).

if (mas[curTopElem] > mas[posMaxTopElem]).

posMaxTopElem = curTopElem;

nextPosHeapItemsAmount = pos;

curTopElem -= LeoNum[pos];

curState >>= 1;

pos++;

return posMaxTopElem;

private void smoothSort (int[] mas) // функция плавная сортировки.

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

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

int nextPosHeapItemsAmount = 0;

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

if (posMaxTopElem ≠ i).

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

shiftDown (mas, nextPosHeapItemsAmount, posMaxTopElem); // вызываем функцию shiftDown.

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

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

int temp = b;

b = a;

a = temp;

Показать весь текст

Заполнить форму текущей работой