ГБПОУ Белебеевский гуманитарно-технический колледж

 

 

 

 

 

 

Исследовательская работа

Экспериментальный анализ различных алгоритмов сортировки массивов

 

 

 

 

 

 

 

 

Выполнила: студентка группы 24ис

Шафикова Алина

Руководитель: Иванов Федор Иванович

 

 

 

 

 

 

2023

Содержание

Введение. 3

1       Назначение разработки. 4

2       Используемые Методы сортировки. 5

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

2.2        Сортировка простой вставкой. 5

2.3        Сортировка бинарными включениями. 5

2.4        Сортировка прямого обмена (пузырька) 6

2.5        Сортировка Шелла. 6

2.6        Сортировка перемешиванием.. 6

3       Описание задачи. 7

3.1        Описание данных. 7

3.2        Главная форма приложения. 7

3.3        Подробная сортировка. 7

3.4        Графики и диаграммы.. 7

3.5        Отчет. 7

3.6        Сообщение программы.. 7

3.7        Справка программы.. 7

Заключение. 8

Список литературы.. 9

 

 

Введение

Практически во всех задачах присутствуют элементы сортировки. Отсортированные элементы содержатся в телефонных справочниках, в оглавлениях, в библиотеках, в словарях.

Зачастую выбор алгоритма решения задачи зависит от структуры сортируемых данных. В случае сортировки эта зависимость имеет большое значение, и методы сортировки обычно разделяют на две категории:

-          сортировка массивов (внутренняя сортировка):

-          сортировка последовательных файлов (внешняя сортировка).

Критериями оценки методов сортировки являются:

-          количество операций сравнения пар ключей;

-          число перестановок элементов;

-          экономное использование памяти;

Стабильность - также важная свойство методов сортировки. Метод сортировки является стабильным в случае, когда он сохраняет относительный порядок расположения записей с одинаковыми ключами.

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

 

1          Назначение разработки

Разрабатываемое приложение, предназначено для исследовательской работы в области изучения методов сортировки массивов.

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

Программа решает следующие задачи:

1)        Выполняет сортировку массива одним из представленных методов на выбор пользователя:

-    метод прямого обмена (пузырька);

-    сортировка перемешиванием (Шейкер);

-    сортировка Шелла;

-    метод сортировки выборкой;

-    метод сортировки простыми вставками;

-    метод сортировки бинарными включениями.

2)                 По выполнению сортировки программа представляет отсортированный массив и график.

 

2          Используемые Методы сортировки

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

Пусть имеется массив A размером N, тогда сортировка выбором сводится к следующему:

-          берем первый элемент последовательности A[i],

-          находим минимальный элемент последовательности и запоминаем его номер в переменную key;

-          если номер первого элемента и номер найденного элемента не совпадают, т. е. если key≠1, тогда два этих элемента обмениваются значениями, иначе никаких манипуляций не происходит;

-          увеличиваем i на 1 и продолжаем сортировку оставшейся части массива.

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

Вывод: метод оказывается эффективным только на маленьких массивах (не более 10 элементов), на массивах больших размеров, в силу асимптотической сложности n^2, алгоритм оказывается крайне неэффективным.

2.2   Сортировка простой вставкой

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

Вывод: сортировка вставками наиболее эффективна, когда массив уже частично отсортирован и когда элементов массива не много. Если же элементов меньше 10, то данный алгоритм является лучшим.

 

2.3   Сортировка бинарными включениями

Алгоритм метода бинарной вставки представляет из себя оптимизированную версию простых вставок, отличие заключается в том, что при поиске место, на которое надо вставить элемент a[i] в уже упорядоченную совокупность a[0] , ..., a[i-1] , определяется алгоритмом деления пополам. Метод бинарной вставки обеспечивает более высокую скорость сортировки по сравнению с методом простой вставки.

2.4   Сортировка прямого обмена (пузырька)

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива.

Вывод: метод пузырька оказывается крайне неэффективным на любом входном наборе данных. Единственный плюс алгоритма - простота его исполнения.

2.5   Сортировка Шелла

При данном методе сортировки сначала сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии. После этого процедура повторяется для некоторых меньших значений, а завершается сортировка Шелла упорядочиванием элементов (то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места.

Вывод: Каждый проход сортировки распространяется на относительно небольшое количество элементов либо на элементы, расположенные уже в относительном порядке. Поэтому сортировка Шелла эффективна, а каждый проход повышает упорядоченность

2.6   Сортировка перемешиванием

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

Вывод: алгоритм шейкер-сортировки удобно применять тогда, когда ясно, что элементы уже, в основном, упорядочены.

 

3          Описание задачи

3.1   Описание данных

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

-          количество элементов массива ;

-          исходный массив.

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

-          отсортированный массив;

-          количество обменов;

-          количество сравнений;

-          затраченное время;

-          графики.

3.2   Главная форма приложения

Главная форма состоит из 4 частей:

-          исходный массив –заполняются все вводимые пользователем данные;

-          результат – выводится массив в отсортированном виде;

-          параметры массива;

-          анализ – в данную таблицу выносятся используемые параметры.

3.3   Подробная сортировка

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

3.4   Графики и диаграммы

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

3.5   Отчет

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

3.6   Сообщение программы

Далее будут приведены несколько сообщений, которые могут появиться при работе с приложением.

3.7   Справка программы

Справку о программе можно получить выбрав пункт меню «Справка» - «О программе».

Заключение

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

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

В качестве недостатка программы можно отнести:

-    некорректное удаление массива из таблиц «Результат» и «Анализ»;

-    при изменении количества элементов в массиве в меньшую сторону – ячейки в таблице «Результат» скрываются;

-    реализовать наиболее точный способ замера времени.

Дальнейшая доработка:

-    добавить подробную сортировка по методам: прямого обмена, сортировки Шелла и сортировки перемешиванием;

-    программа может быть преобразована для использования в целях сортировки массивов, вводимых пользователем.

В целом, задачи, поставленные в рамках дипломного проекта, реализованы. Проведено исследование различных методов сортировки массива.

 

Список литературы

1.         Бахтизин В.В., Глухова Л.А.Технология разработки программного обеспечения: учеб. пособие /. – Минск : БГУИР, 2010.

2.         Гагарина Л.Г., Виснадул Б.Д., Игошин А.В. Основы технологии разработки программных продуктов: Учебное пособие. – М.: ФОРУМ: ИНФРА-М, 2006. – (Профессиональное образование).

3.         Иванова Г.С., Ничушкина Т.Н., Пугачёв Е.К. - Объектно-ориентированное программирование. МГТУ им. Н.Э. Баумана, 2001.

4.         Культин Н. Самоучитель.Основы программирования в Delphi 7. БХВ-Петербург. 2007.

5.         Мозговой М.В. - Занимательное программирование. Питер, 2005.

6.         Пономарев В.А. COM и ActiveX в Delphi. – СПб.:БХВ – Петербург, 2001.

7.         Рудаков А.В. Технология разработки программных продуктов: Учеб. пособие для студ. сред. проф. образования. – М.: Издательский центр «Академия», 2010.

8.         Флёнов М.Е. - Библия Delphi (3-е издание), БХВ-ПЕТЕРБУРГ, 2011.

 

Скачано с www.znanio.ru