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

Реферат

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

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

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

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

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

Содержание

Содержание

Введение

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

.1 Сортировка выбором

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

Введение

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

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

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

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

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

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

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

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

∙        Быстрая

∙        Шелла

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

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

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

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

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

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

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

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

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

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

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

Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке. Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из 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 сравнений. С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций: