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

В современном мире мы часто сталкиваемся с большими объемами нужной нам информации. Чтобы избежать этого, а также ускорить поиск нужной информации используют методы сортировок. Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступ к любой ячейке. В свою очередь методы внутренней сортировки делятся на прямые и улучшенные: Прямые методы: · Вставкой (включением) Внешняя сортировка - сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память, то есть когда применить одну из внутренних сортировок невозможно.На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае ?( ), предполагая, что сравнения делаются за постоянное время. Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке. Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м. На i-м шаге выбираем наименьший из элементов a[i]…a[n] и меняем его местами с a[i].Итак назовем пирамидой бинарное дерево высоты k, в котором: · все узлы имеют глубину k или k-1 - дерево сбалансированное. Таким образом, для массива, хранящего в себе пирамиду, выполняется следующее характеристическое свойство: a[i]>=a[2i 1] и a[i]>=a[2i 2] На рисунке 3 место элемента пирамиды в массиве обозначено цифрой справа-вверху от него. Восстановить пирамиду из массива как геометрический объект легко - достаточно вспомнить схему хранения и нарисовать, начиная от корня. Чтобы при добавлении элемента сохранялась пирамидальность, будем использовать следующую процедуру расширения пирамиды a[i 1]..a[n] на элемент a[i] влево.Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путем непрерывного удаления максимума из кучи. Куча состоит из последовательности куч, размеры которых равны одному из чисел Леонардо, а корни хранятся в порядке возрастания. Разбить входные данные на кучи просто: крайние слева узлы массива составят самую большую кучу, а оставшиеся будут разделены подобным образом: · Массив любой длины может быть также разбит на части размера L(x). Для каждой кучи выполняется следующее свойство: значение корня должно быть не меньше значений корней его куч-потомков (и, как следствие, не меньше значений всех узлов его куч-потомков). Для последовательности куч в свою очередь выполняется следующее свойство: значение корня каждой кучи должно быть не меньше значения корня кучи слева.Назначение разработки: Исходя из введенных пользователем данных отсортировать тремя методами сортировки: выборкой, пирамидально, плавной. После обработки и выполнения сортировки программа выводит результат в соответствующее поле вывода. Для реализации данной программы мы используем язык программирования C#, на платформе Visual Studio.В самом начале выполнения программы появляется форма, где пользователю предлагается заполнить соответствующие поля необходимыми для расчета данными. Затем, в ходе выполнения программы производится проверка полноты и корректности введенных начальных данных.RICHTEXTBOX1 - получает введенный пользователем массив, либо автоматически генерируемый с помощью кнопки «Сгенерировать» button1 - принимает текстовое значение «Сгенерировать», а также генерирует в поле RICHTEXTBOX1 рандомный массив от 0 до 100. Содержит текстовые значения: «Пирамидальная сортировка», «Плавная сортировка», «сортировка Выбором». button2 - принимает текстовое значение «Сортировать», а также сортирует введенные или сгенерированные пользователем данные из RICHTEXTBOX1.Функция SELECTSORT производит сортировку по алгоритму «Выборка» и передает отсортированный массив в функцию Print private void SELECTSORT(int[] array) // сортировка выборкой {min = i; // присваиваем наименьший элемент i-ому for (int j = i 1; j <array.Length; j ) if (array[j] <array[min]) // если элменент массива меньше минимального min = j; // присваиваем новое минимальное значение элементу массиву Меняем местами значения int temp = array[i] array[i] = array[min]; Функция 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-)Для корректной работы программы необходимо заполнить вручную или сгенерировать с помощью кнопки массив данных.Язык программирования C# на основе Visual Studio способен реализовать все необходимые средства для сортировки данных. Во время выполнения поставленной задачи были улучшены навыки программирования, работы с м

Содержание

Реферат

Введение

1. Описание предметной области

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

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

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

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

2. Технология разработки приложения

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

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

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

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

Заключение

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

Приложение

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

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

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

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

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

Улучшенные методы: · Быстрая

· Шелла

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

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

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

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

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

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

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