Исследование методов сортировки выбором
Реферат
Программа для сортировки данных методами выбора.
Ключевые слова: СОРТИРОВКА, МЕТОДЫ СОРТИРОВКИ, ВЫБОРКА, ПИРАМИДАЛЬНЫЙ,
ПЛАВНЫЙ, МАССИВЫ.
Цель работы: Проектирование и разработка программы для осуществления
сортировки данных методами «Выбора» с использованием языка C# и Visual Studio 2012.
Объект исследования: Методы сортировки Выбором.
Предмет исследования: Программа на языке С#.
Содержание
Содержание
Введение
. ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ
.1 Сортировка выбором
.2 Пирамидальная сортировка
.3 Плавный метод сортировки
.4 Постановка задачи
. ТЕХНОЛОГИЯ РАЗРАБОТКИ ПРИЛОЖЕНИЯ
.1 Алгоритм решения
.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=1/2*(+n) = Theta().
Таким образом, так как число обменов всегда будет меньше числа сравнений,
время сортировки растет квадратично относительно количества элементов.
1.2 Пирамидальная сортировка
Пирамидальная сортировка является методом, быстродействие которого
оценивается как О(n log n). В качестве некоторой прелюдии к основному методу,
рассмотрим перевернутую сортировку выбором. Во время прохода, вместо вставки
наименьшего элемента в левый конец массива, будем выбирать наибольший элемент,
а готовую последовательность строить в правом конце.
55 12 42 94 18 06 67 исходный массив
55 12 42 67 18 06 |94 94 <-> 67
55 12 42 06 18 |67 94 67 <-> 06
18 12 42 06 |55 67 94 55 <-> 18
18 12 42 |44 55 67 94 44 <-> 06
18 12 |42 44 55 67 94 42 <-> 42
12 |18 42 44 55 67 94 18 <-> 12
|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-ми элементов:
55 12 42 // 94 18 06 67
55 12 // 67 94 18 06 42
55 // 18 67 94 12 06 42
// 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-й фазы сортировки во внутреннем представлении
пирамиды.
67 18 44 55 12 06 42 //
55 44 06 42 18 12 // 94
42 44 06 12 18 // 67 94
42 18 06 12 // 55 67 94
12 18 06 // 44 55 67 94
12 06 // 42 44 55 67 94
06 // 18 42 44 55 67 94
// 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.
Системные требования к ПК:
) Операционная система Windows 7 или выше.
) Свободное место на жестко диске: 10Мб и более.
) Наличие Net.Framework 4.0 или выше.
) Оперативная память 512Мб и выше.
) Клавиатура и мышь.
2. ТЕХНОЛОГИЯ
РАЗРАБОТКИ ПРИЛОЖЕНИЯ
2.1 Алгоритм решения
В самом начале выполнения программы появляется форма,
где пользователю предлагается заполнить соответствующие поля необходимыми для
расчета данными.
Затем, в ходе выполнения программы производится
проверка полноты и корректности введенных начальных данных. Если исходные
данные не прошли проверку - выводится соответствующее уведомление.
После успешно пройденной проверки, программа начинает
сортировать полученные данные. Программа считывает данные, заполненные в
специальных полях и производит сортировку по установленным алгоритмам.
После этого результаты выводятся в специально
отведенное поле, а выполнение программы прекращается.
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 - число, двоичное представление которого описывает текущий
массив куч
// indexLastTop - индекс крайней вершины
// nextPosHeapItemsAmount - количество элементво в кучи, вершина которой
оказалось максимальной из всех вершин куч
// Возврат: индекс элемента(одной из вершин кучи), который больше чем
остальные вершины куч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;
}
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); // вызываем функцию shiftDown
}(ref curState); // вызываем функцию PreveState и передаем значения, ссылаясь(ref) на значение переменной curState
}
}void swap(ref int a, ref int b) // функция перестановки(swap)
{temp = b;= a;= temp;
}
}
}