Введение

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

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

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

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

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

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

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

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

• Быстрая

• Шелла

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

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

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

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

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

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

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

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

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().

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