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

Реферат

Программа для сортировки данных методами выбора.

Ключевые слова: СОРТИРОВКА, МЕТОДЫ СОРТИРОВКИ, ВЫБОРКА, ПИРАМИДАЛЬНЫЙ, ПЛАВНЫЙ, МАССИВЫ.

Цель работы: Проектирование и разработка программы для осуществления сортировки данных методами «Выбора» с использованием языка C# и Visual Studio 2012.

Объект исследования: Методы сортировки Выбором.

Предмет исследования: Программа на языке С#.

Содержание Содержание Введение

1. ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ

1.1 Сортировка выбором

1.2 Пирамидальная сортировка

1.3 Плавный метод сортировки

1.4 Постановка задачи

2. ТЕХНОЛОГИЯ РАЗРАБОТКИ ПРИЛОЖЕНИЯ

2.1 Алгоритм решения

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

2.3 Описание программы ЗАКЛЮЧЕНИЕ СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ ПРИЛОЖЕНИЕ-ЛИСТИНГ ПРОГРАММЫ

В современном мире мы часто сталкиваемся с большими объемами нужной нам информации. Ее так много, что можно запутаться, что же делать? Действительно, нередко среди огромного потока информации могут затеряться необходимые данные. Чтобы избежать этого, а также ускорить поиск нужной информации используют методы сортировок. Существует два вида сортировки данных: внешний и внутренний.

Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступ к любой ячейке. Этот вид сортировки характерен тем, что данные сортируются на том же месте, без дополнительных затрат.

В свою очередь методы внутренней сортировки делятся на прямые и улучшенные:

Прямые методы:

· Вставкой (включением)

· Выбором (выделением)

· Обменом («пузырьковая»)

Улучшенные методы:

· Быстрая

· Шелла Внешняя сортировка — сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память, то есть когда применить одну из внутренних сортировок невозможно.

Стоит отметить, что внутренняя сортировка значительно эффективней внешней, так как на обращение к оперативной памяти затрачивается намного меньше времени, чем к магнитным дискам, лентам и т. п.

Рассматриваемый в данной курсовой работе вид сортировки «Выбор» имеет три варианта реализации: простая выборка, пирамидальная, плавная.

В соответствии с поставленной целью были сформулированы следующие задачи:

· Провести предметный анализ в области

· Разработать необходимую программу

· Провести тестирование приложения

· Определить эффективность разработанной программы

1.ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ

1.1 Сортировка выбором

Сортировка выбором (от англ. Selection sort) — алгоритм сортировки. Может быть как устойчивый, так и неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае И (), предполагая, что сравнения делаются за постоянное время.

Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке. Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м. На i-м шаге выбираем наименьший из элементов a[i]…a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на рис.1

Рисунок1. Демонстрация последовательных шагов при n=5

Вне зависимости от номера текущего шага i, последовательность a[0]…a[i] является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.

Для нахождения наименьшего элемента из n+1 рассматриваемых алгоритм совершает n сравнений. С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций:

n+ (n-1)+(n-2)+(n-3)+…1=½*(+n) = Theta ().

Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки растет квадратично относительно количества элементов.

1.2 Пирамидальная сортировка

Пирамидальная сортировка является методом, быстродействие которого оценивается как О (n log n). В качестве некоторой прелюдии к основному методу, рассмотрим перевернутую сортировку выбором. Во время прохода, вместо вставки наименьшего элемента в левый конец массива, будем выбирать наибольший элемент, а готовую последовательность строить в правом конце.

44 55 12 42 94 18 06 67 исходный массив

44 55 12 42 67 18 06 |94 94 <-> 67

44 55 12 42 06 18 |67 94 67 <-> 06

44 18 12 42 06 |55 67 94 55 <-> 18

06 18 12 42 |44 55 67 94 44 <-> 06

06 18 12 |42 44 55 67 94 42 <-> 42

06 12 |18 42 44 55 67 94 18 <-> 12

06 |12 18 42 44 55 67 94 12 <-> 12

Рисунок 2. Пример действия массива а[0]…a[7]

Вертикальной чертой отмечена левая граница уже отсортированной (правой) части массива. Рассмотрим оценку количества операций подробнее. Всего выполняется n шагов, каждый из которых состоит в выборе наибольшего элемента из последовательности a[0]…a[i] и последующем обмене. Выбор происходит последовательным перебором элементов последовательности поэтому необходимое на него время: O (n). Итак, n шагов по О (n) каждый — это О).

Произведем усовершенствование: построим структуру данных, позволяющих выбирать максимальный элемент последовательности не за O (n), а за O (logn) времени. Тогда общее быстродействие сортировки будет n*O (logn) = O (n log n).

Эта структура также должна позволять быстро вставлять новые элементы (чтобы быстро ее построить из исходного массива) и удалять максимальный элемент (он будет помещаться в уже отсортированную часть массива — его правый конец).

Итак назовем пирамидой бинарное дерево высоты k, в котором:

· все узлы имеют глубину k или k-1 — дерево сбалансированное.

· при этом уровень полностью заполнен, а уровень k заполнен слева направо.

· выполняется свойство пирамиды: каждый элемент меньше, либо равен родителю.

Соответствие между геометрической структурой пирамиды как дерева и массивом устанавливается по следующей схеме на рисунке 3.

· в а[0] хранится корень дерева

· левый и правый сыновья элемента a[i] хранятся, соответственно, в a[2i+1 и a[2i+2]

Таким образом, для массива, хранящего в себе пирамиду, выполняется следующее характеристическое свойство: a[i]>=a[2i+1] и a[i]>=a[2i+2]

Плюсы такого хранения пирамиды очевидны:

· никаких дополнительных переменных, нужно лишь понимать схему

· узлы хранятся от вершины и далее вниз, уровень за уровнем.

· узлы одного уровня хранятся в массиве слева направо Запишем в виде массива пирамиду, изображенную выше. Слева-направо, сверху-вниз: 94 67 18 44 55 12 06 42. На рисунке 3 место элемента пирамиды в массиве обозначено цифрой справа-вверху от него.

Восстановить пирамиду из массива как геометрический объект легко — достаточно вспомнить схему хранения и нарисовать, начиная от корня.

Начать построение пирамиды можно с a[k]…a[n], k = [size/2]. Эта часть массива удовлетворяет свойству пирамиды, так как не существует индексов i, j: i=2i+1 (или j = 2i+2). Такие i, j находятся за границей массива.

Далее будем расширять часть массива, обладающую столь полезным свойством, добавляя по одному элементу за шаг. Следующий элемент на каждом шаге добавления — тот, который стоит перед уже готовой частью.

Чтобы при добавлении элемента сохранялась пирамидальность, будем использовать следующую процедуру расширения пирамиды a[i+1]. .a[n] на элемент a[i] влево.

Новый элемент будет просеиваться сквозь пирамиду.

Ниже дана иллюстрация процесса для пирамиды из 8-ми элементов:

44 55 12 42 // 94 18 06 67

44 55 12 // 67 94 18 06 42

44 55 // 18 67 94 12 06 42

44 // 94 18 67 55 12 06 42

// 94 67 18 44 55 12 06 42

Справа — часть массива, удовлетворяющая свойству пирамиды, остальные элементы добавляются один за другим, справа налево.

В геометрической интерпретации ключи из начального отрезка a[size/2]…a[n] являются листьями в бинарном дереве, как изображено ниже. Один за другим остальные элементы продвигаются на свои места, и так — пока не будет построена вся пирамида.

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

Рисунок 4. Процесс построения пирамиды Итак, задача построения пирамиды из массива успешно решена. Как видно из свойств пирамиды, в корне всегда находится максимальный элемент. Отсюда вытекает алгоритм фазы 2:

· Берем верхний элемент пирамиды a[0]…a[n] (первый в массиве) и меняем с последним местами. Теперь «забываем» об этом элементе и далее рассматриваем массив a[0]…a[n-1]. Для превращения его в пирамиду достаточно просеять лишь новый первый элемент.

· Повторяем шаг 1, пока обрабатываемая часть массива не уменьшится до одного элемента.

Рисунок 5. Просеивание элементов массива Очевидно, что в конец массива каждый раз попадает максимальный элемент из текущей пирамиды, поэтому в правой части постепенно возникает упорядоченная последовательность.

Рисунок 6. Иллюстрация 2-й фазы сортировки во внутреннем представлении пирамиды.

94 67 18 44 55 12 06 42 //

67 55 44 06 42 18 12 // 94

55 42 44 06 12 18 // 67 94

44 42 18 06 12 // 55 67 94

42 12 18 06 // 44 55 67 94

18 12 06 // 42 44 55 67 94

12 06 // 18 42 44 55 67 94

06 // 12 18 42 44 55 67 94

Построение пирамиды занимает О (n log n) операций, причем более точная оценка дает даже О (n) за счет того, что реальное время выполнения зависит от высоты уже созданной части пирамиды.

Вторая фаза занимает O (n log n) времени: O (n) раз берется максимум и происходит просеивание бывшего последнего элемента. Плюсом является стабильность метода: среднее число пересылок (n log n)/2, и отклонения от этого значения сравнительно малы.

Пирамидальная сортировка не использует дополнительной памяти. Метод не является устойчивым: по ходу работы массив так «перетряхивается», что исходный порядок элементов может измениться случайным образом, частичная упорядоченность массива никак не учитывается.

1.3 Плавный метод сортировки

Плавная сортировка — алгоритм сортировки выбором, разновидность пирамидальной сортировки, разработанная Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную O (n log n). Преимущество плавной сортировки в том, что её сложность приближается к O (n), если входные данные частично отсортированы, в то время как у пирамидальной сортировки сложность всегда одна, независимо от состояния входных данных.

Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи. В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо. Куча состоит из последовательности куч, размеры которых равны одному из чисел Леонардо, а корни хранятся в порядке возрастания. Преимущества таких специальных куч перед двоичными состоят в том, что если последовательность отсортирована, её создание и разрушение займёт O (n) времени, что будет быстрее. Разбить входные данные на кучи просто: крайние слева узлы массива составят самую большую кучу, а оставшиеся будут разделены подобным образом:

· Массив любой длины может быть также разбит на части размера L (x).

· Не должно быть двух куч одинакового размера, потому что в этом случае последовательность превратится в строго убывающую по размерам.

· Не должно быть двух куч, размеры которых равны двум последовательным числам Леонардо, за исключением массива длины 2.

Эти положения могут быть доказаны:

Каждая куча размера L (x) состоит, слева направо, из подкучи размера L (x? 1), подкучи размера L (x? 2) и корня, за исключением куч размера L (1) и L (0), которые состоят только из корня. Для каждой кучи выполняется следующее свойство: значение корня должно быть не меньше значений корней его куч-потомков (и, как следствие, не меньше значений всех узлов его куч-потомков). Для последовательности куч в свою очередь выполняется следующее свойство: значение корня каждой кучи должно быть не меньше значения корня кучи слева. Следствие этого — крайний правый узел в последовательности будет иметь наибольшее значение, и, что важно, частично отсортированный массив не будет нуждаться в перестановке элементов, для того чтобы стать правильной последовательностью куч. Это является источником приспособляемости алгоритма. Алгоритм прост. Сначала происходит разделение неотсортированного массива на кучу с одним элементом и неотсортированную часть. Куча с одним элементом, очевидно, представляет собой правильную последовательность куч. Последовательность начинает расти путём добавления по одному элементу справа за раз (если нужно, элементы меняются местами, чтобы выполнялось свойство кучи и свойство последовательности), пока не достигнет размера изначального массива. И с этого момента крайний правый элемент в последовательности куч будет самым большим для любой кучи, а, следовательно, будет находиться на верной, конечной позиции. Затем последовательность куч уменьшается до кучи с одним элементом при помощи удаления крайнего правого узла и изменения позиций элементов для восстановления состояния кучи. Как только останется куча с одним элементом, массив будет отсортирован.

Необходимы две операции: увеличение последовательности куч путём добавления элемента справа и уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности куч.

Увеличение последовательности куч путем добавления элемента справа достигается при следующих условиях:

· Если две последние кучи имеют размеры L (x + 1) и L (x) (двух последовательных чисел Леонардо), новый элемент становится корнем кучи большего размера, равного L (x+2). Для неё свойство кучи необязательно.

· Если размеры двух последних куч не равны двум последовательным числам Леонардо, новый элемент образует новую кучу размером 1. Этот размер полагается равным L (1), кроме случая, когда крайняя правая куча уже имеет размер L (1), тогда размер новой одноэлементной кучи полагают равным L (0).

После этого должно быть восстановлено выполнение свойств кучи и последовательности куч, что, как правило, достигается при помощи разновидности сортировки вставками:

· Крайняя правая куча (сформированная последней) считается «текущей» кучей.

· Пока слева от неё есть куча и значение её корня больше значения текущего корня и обоих корней куч-потомков:

· Выполняется «просеивание», чтобы выполнялось свойство кучи:

Операция просеивания значительно упрощена благодаря использованию чисел Леонардо, так как каждая куча либо будет одноэлементной, либо будет иметь двух потомков. Нет нужды беспокоиться об отсутствии одной из куч-потомков.

Уменьшение последовательности куч путем удаления элемента справа достигается при следующих условиях:

Если размер крайней правой кучи равен 1 (то есть L (1) или L (0)), эта куча просто удаляется. В противном случае корень этой кучи удаляется, кучи-потомки считаются элементами последовательности куч, после чего проверяется выполнение свойства кучи, сначала для левой кучи, затем — для правой.

1.4 Постановка задачи

Название приложения: Программа сортировки методами выбора Назначение разработки: Исходя из введенных пользователем данных отсортировать тремя методами сортировки: выборкой, пирамидально, плавной.

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

Для корректной работы программы требуется заполнить все необходимые поля. Для реализации данной программы мы используем язык программирования C#, на платформе Visual Studio.

Системные требования к ПК:

1) Операционная система Windows 7 или выше.

2) Свободное место на жестко диске: 10Мб и более.

3) Наличие Net. Framework 4.0 или выше.

4) Оперативная память 512Мб и выше.

5) Клавиатура и мышь.

2. ТЕХНОЛОГИЯ РАЗРАБОТКИ ПРИЛОЖЕНИЯ

2.1 Алгоритм решения

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

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

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

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

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

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

Рисунок 7. Макет приложения.

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

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

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

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

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

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

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

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;

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

button

richTextBox

comboBox

label

Обработчики событий

private void button1_Click (object sender, EventArgs e)

private void button2_Click (object sender, EventArgs e)

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

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

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

{

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

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

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

}

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

Функция selectSort производит сортировку по алгоритму «Выборка» и передает отсортированный массив в функцию Print

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;

}

}

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

Функция heapSort производит сортировку по алгоритму «Пирамида» и передает отсортированный массива в функцию Print

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

}

}

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

Функция smoothSort производит сортировку по алгоритму «Плавная» и передает отсортированный массив в функцию Print.

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); // вызываем функцию

}

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

}

}

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

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

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;

}

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

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;

}

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

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

{

if ((curState & 15) == 8)

{ // curState = 1000

curState -= 3; // curState = 010

}

еlse 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

else

curState = 0;

}

}

Функция shiftDown является вспомогательной функцией. Она реализует просеивание данных массива «вниз»

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;

}

}

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

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);

}

}

Функция findPosMaxElem является вспомогательной функцией. Она ищет максимальный элемент среди вершин куч.

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;

}

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

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

{

int temp = b;

b = a;

a = temp;

}

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

Язык программирования 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

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;

}

}

}