Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования (ИСТОРИЯ И ХАРАКТЕРИСТИКА СОРТИРОВКИ ДАННЫХ)

Содержание:

ВВЕДЕНИЕ

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

К концу XX века человечество осуществило переход к новому типу построения общества – общество стало информационным, основой его стала информация. В связи с растущими объемами и потоками информации потребовались новые технологии хранения, обработки и передачи информации. Базы данных совместили в себе функции хранения и обработки. Объемы хранимой информации бывают таковы, что в некоторых случаях база данных превышает несколько терабайт. Одним из ключевых элементов обработки информации является поиск необходимой ее части в общем объеме, а в больших базах данных этот вопрос является особенно актуальным и требует быстрых методов поиска.

Существует много методов поиска, каждый из которых показывает лучшие результаты по сравнению с другими в определенных условиях. Каждый из них рассматривать в данной работе не целесообразно, поэтому остановимся на 2-х основных: линейный (последовательный) поиск и бинарный поиск.

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

Пожалуй, никакая другая проблема не породила такого количества разнообразнейших решений, как задача сортировки. Существует ли некий «универсальный», наилучший алгоритм? Вообще говоря, нет. Однако, имея приблизительные характеристики входных данных, можно подобрать метод, работающий оптимальным образом. Вышесказанное определяет актуальность темы работы.

Целью курсовой работы является изучение методов сортировки данных и ее эволюции.

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

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

Задачи работы:

Рассмотрет эволюцию сортировки данных;

Изучить методы сортировки данных;

Провести сравнение алгоритмов сортировки.

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

ГЛАВА 1. ИСТОРИЯ И ХАРАКТЕРИСТИКА СОРТИРОВКИ ДАННЫХ

1.1.Эволюция сортировки данных

Важное практическое значение проблема сортировки данных в больших массивах впервые приобрела в США в середине XIX века. В 1840 году там был создан центральный офис переписи населения, куда стекались первичные данные из всех штатов. В ходе переписи было опрошено 17 069 453 человек, каждая анкета состояла из 13 вопросов. Объем полученных данных был столь велик, что их обработка традиционным ручным способом потребовала непомерных затрат труда и времени. Ситуация усугублялось необходимостью проведения постоянных сверок и пересчетов из-за допускаемых при ручной сортировке данных ошибок. С каждой новой переписью, которая проводилась раз в десять лет, объем обрабатываемой информации, а вместе с ним стоимость и длительность обработки данных возрастали. Так, ручная обработка данных переписи населения 1880 года (50 189 209 человек) потребовала привлечения сотен служащих и длилась семь с половиной лет [1].

Перед переписью 1890 года для решения проблемы сортировки данных в очень больших массивах информации по инициативе бюро переписи был проведен конкурс на лучшее электромеханическое сортировочное оборудование, которое сделало бы сортировку данных более эффективной — более быстрой, точной и дешевой. Конкурс выиграл американский инженер и изобретатель немецкого происхождения Герман Холлерит (Herman Hollerith), разработавший оборудование для работы с перфокартами — электрическую табулирующую систему, ставшую известной как Hollerith Electric Tabulating System. Использование этого оборудования при переписях населения США в 1890 и 1900 годах было признано очень успешным. Вот как были описаны преимущества машины Холлерита в русском журнале «Вестник Опытной Физики и Элементарной Математики» в 1895 году: «Преимущества машины Голлерита заключаются: а) в значительном ускорении и удешевлении работы. При ручном способе можно разложить и подсчитать за час не более 400 карточек. [4]

Таким образом, обработка данных с помощью машины Холлерита потребовала в три раза меньше времени, чем вручную, причем точность сводных таблиц значительно возросла. Таким образом, в конце XIX века на смену ручной сортировке данных в массивах пришла сортировка с помощью статистических табуляторов. При этом использовался алгоритм поразрядной сортировки. Следующий этап развития способов и алгоритмов сортировки начался в начале 1940-х годов с появлением первых электронных вычислительных машин. Фантастическое по тем временам быстродействие ЭВМ вызвало рост интереса к новым, приспособленным для машинной обработки алгоритмам сортировки.

В 1946 году вышла первая статья об алгоритмах сортировки данных, автором которой был Джон Уильям Мочли (John William Mauchly) — американский физик и инженер, один из создателей первого в мире электронного цифрового компьютера общего назначения ENIAC. В статье рассматривался целый ряд новых алгоритмов сортировки, в том числе метод бинарных вставок. До середины 1950-х годов наиболее распространенными были модификации сортировки слиянием и вставками сложности O (n log n) для п элементов. Еще одним следствием перехода к сортировке данных с помощью ЭВМ стало разделение сортировки на два типа — внешнюю и внутреннюю, то есть на использующую и не использующую данные, расположенные на периферийных устройствах. В середине 1950-х годов с разработкой ЭВМ второго поколения началось активное развитие алгоритмов сортировки [3].

Итоги этого этапа активного развития алгоритмов сортировки подвел в 1973 году Дональд Эрвин Кнут (Donald Ervin Knuth) в третьем томе своей фундаментальной монографии «Искусство программирования» («The Art of Computer Programming»). К началу 1970-х годов использовались следующие виды алгоритмов внутренней сортировки: сортировка посредством подсчета; сортировка путем вставок; обменная сортировка; сортировка посредством выбора; сортировка методом слияния; сортировка методом распределения. Наибольшее количество разработанных к тому времени методов относилось к сортировке путем вставок (метод простых вставок, бинарные и двухпутевые вставки, метод Шелла, вставка в список, сортировка с вычислением адреса и др.), обменной сортировке (метод пузырька и его модификации, параллельная сортировка Бэтчера, быстрая сортировка, обменная поразрядная сортировка, асимптотические методы) и сортировке посредством выбора (выбор из дерева, пирамидальная сортировка, метод исключения наибольшего из включенных, метод связанного представления приоритетных очередей). [11]

Не менее активно разрабатывались и методы внешней сортировки, в том числе методы многопутевого слияния и выбора с замещением, многофазного слияния, каскадного слияния, осциллирующей сортировки, внешней поразрядной сортировки и т. д. [4]. Очередной всплеск интереса к алгоритмам сортировки произошел в середине 1970-х годов, когда элементной базой компьютеров стали большие интегральные схемы и появилась возможность объединения мощности вычислительных машин путем создания единых вычислительных центров, позволяющих работать с разделением времени. В период с середины 1970-х до 1990-х годов были достигнуты значительные успехи в увеличении скорости сортировки за счет повышения эффективности уже известных к тому времени алгоритмов путем их доработки или комбинирования. К примеру, нидерландский учёный Эдсгер Вибе Дейкстра (Edsger Wybe Dijkstra) в 1981 году предложил алгоритм плавной сортировки (Smoothsort), который является развитием пирамидальной сортировки (Heapsort). Вторым направлением совершенствования алгоритмов сортировки стал поиск оптимальных входных последовательностей для разных методов сортировки, что позволяло значительно сократить ее время. Третьим направлением, наиболее интенсивно развивающимся, было решение задачи сортировки в классе параллельных алгоритмов, для чего не только обобщались ранее известные парадигмы, но и разрабатывались принципиально новые алгоритмы. Развитие данного направления стимулировалось и все более широким использованием сортирующих сетей, а также многомерных вычислительных решеток.

Таким образом, исследовав эволюцию способов и алгоритмов машинной сортировки данных в массивах, можно выделить следующие пять этапов. Первый этап начался в 1870 году и длился до начала 1940-х годов. Его ознаменовал переход от ручной сортировки к сортировке с помощью статистических табуляторов. При этом использовался алгоритм поразрядной сортировки. Второй этап — с начала 1940-х годов до середины 1950-х. На смену счетно-перфорационным машинам пришли ЭВМ первого поколения, для которых был разработан ряд новых алгоритмов сортировки. [15]

Наибольшее количество разработанных к тому времени методов относилось к сортировке путем вставок, обменной сортировке и сортировке посредством выбора. Четвертый этап продолжался с середины 1970-х до середины 1990-х годов. Появление вычислительных центров, объединяющих мощности отдельных вычислительных машин и позволяющих работать с разделением времени потребовало разработки новых алгоритмов сортировки и модификации существующих.

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

1.2 Методы сортировки данных

В программировании довольно часто перед тем как начать работу с данными их необходимо предварительно отсортировать. От выбранного способа сортировки зависит эффективность всей работы, поэтому алгоритм должен быть самый эффективный и удачно реализованный, иначе попытка оптимизации может привести к заметному понижению эффективности всей программы в целом. Поэтому перед началом работы у программиста возникает вопрос: каким способом лучше отсортировать данные?

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

Однако на практике часто приходится иметь дело с неупорядоченными данными находящимися на внешних носителях с последовательным доступом. Но эти файлы имеют большой объем, поэтому нельзя переместить их полностью в оперативную память, произвести сортировку и вернуть обратно, поэтому чтение и запись в файл происходит по частям с использованием различных алгоритмов внешней сортировки [1].

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

Скорость выполнения внешних сортировок зависит от размера буфера основной памяти, который может быть использован. Наиболее часто внешняя сортировка используется в СУБД при выполнении запросов, и ее производительность зависит от эффективности применяемых методов [4].

Основное понятие, которое используется в алгоритмах внешней сортировки - серия. Она представляет собой последовательность упорядоченных элементов. Длина серии варьируется от N (нет упорядоченным элементов) до 1 (все элементы упорядочены).

Методы внешней сортировки состоят из многократно повторяющихся фаз слияния и распределения. Фаза слияния - это процесс объединения двух и более упорядоченных серий в одну. Фаза распределение - процесс разделения упорядоченных серий по вспомогательным файлам [2].

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

Каждая сортировка имеет свои ключевые особенности из которых складываются достоинства и недостатки данного алгоритма. Рассмотрим некоторые алгоритмы внешней сортировки:

1. Алгоритм однофазной сортировки простым слиянием является простейшим. Он основан на процедуре слияния серией. Их длина фиксируется на каждом шаге. Сначала в файле все серии имеют длину 1, затем после каждого шага она увеличивается в 2 раза. Сортировка заканчивается, когда p > n, где p - длина серии, n - количество элементов в файле [1].
2. Алгоритм однофазного естественного слияния в отличие от предыдущего учитывает частично упорядоченные последовательности. То есть длина серии не ограничивается и зависит от уже упорядоченных элементов при каждом проходе [1,3].
3. Сортировка методом поглощения начинает считывать серии с конца файла в оперативную память, упорядочивает их алгоритмами внутренней сортировки и поглощает полученной серией элементы в исходном файле, при этом происходит слияние с упорядоченной последовательностью, которая была получена на предыдущем шаге [1].
4. Многофазная сортировка появилась из сбалансированного многофазного слияния [5]. В этом алгоритме примерно половина вспомогательных файлов используется для разделения и столько же для их слияния. Поэтому появилась идея многофазной сортировки. Она состоит в том, что из m файлов для распределения серий используется m-1, а оставшийся для слияния. Как только один из вводных файлов становится пустым его начинают использовать для слияния. Этот процесс происходит до тех пор, пока в одном из файлов не останется одна серия.

Наиболее популярной является сортировка простым слиянием. В ней число сравнений и перестановок оценивается как O(nlog(n)). Однако в ней не учитывается тот факт, что последовательность может быть уж частично упорядочена. Этот недостаток учитывает следующая сортировка [1].

Метод естественного слияния основывается на распределении исходного файла на вспомогательные с учетом частично упорядоченных серий. Количество чтений и записей при использовании этого алгоритма будет не хуже, чем в предыдущей сортировке, однако количество сравнений будет больше, так как требуются дополнительные сравнения для распознавания конца серий. Также к недостатку можно отнести то, что длина вспомогательных файлов может быть близка к размеру исходного [3].

Многофазное слияние даёт ожидаемый результат и на каждом этапе сливает максимальное количество серий если начальное распределение серий по вспомогательным файлам описывается соседними числами Фибоначчи. В общем виде для успешной работы алгоритма с использованием m вспомогательных файлов начальное распределение серий между (m-1) файлами должно описываться суммами соседних чисел Фибоначчи порядка (m­2) [1]. Не всегда распределение удовлетворяет данному условию, тогда между файлами равномерно распределяют пустые серии, которые потом при слиянии распознаются. Следовательно, чем ближе количество серий к числу Фибоначчи, тем эффективнее алгоритм.

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

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

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

Для эксперимента была выбрана среда разработки Delphi7. Delphi — объектно-ориентированный язык программирования со строгой статической типизацией переменных. Основная область использования — написание прикладного программного обеспечения. Первоначально носил название Object Pascal и был разработан в фирме Apple в 1986 году группой Ларри Теслера. Однако в настоящее время термин Object Pascal чаще всего употребляется в значении языка среды программирования Delphi. Начиная с Delphi 7, в официальных документах Borland стало использоваться название Delphi для обозначения языка Object Pascal [1].

Гипотеза - Любой метод сортировки должен отличаться в количестве итераций - действий, ходов совершенными объектом, для сортировки данных.

Выходными данными в эксперименте является количество итераций.

Для исследования воспользуемся методами сортировок выбора, обмена (или многим известным, как метод «Пузырька») и подсчетов данных.

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

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

Сортировка обмена.

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

Сортировка подсчетом.

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

Огромное количество данных в наше время поступает на сортировку. Выбор наилучшего метода сортировки данных очень значимая проблема современной жизни. Различные методы обуславливаются различными условиями их применения. Поиск универсального метода сортировки данных важна, ведь именно она, сэкономит время сортировки данных при любом количестве входных данных, относительно других методов, а также упросит и уменьшит код программ для сортировки данных, позволив использовать лишь один метод, а не несколько. Программа произведет значимое влияние на обучение студентов и упростит преподавателям обучение, путем визуального представления работы каждого метода сортировки и сравнения их при различных условиях [2], [4].

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

В таблице 1, получена в ходе исследований, куда записывались данные из ранее приведенных сортировок в программе, такие как: сортировка, время, количество итераций и количество элементов.

Рисунок 1 - Сравнение методов сортировок

В данной таблице можно наглядно убедиться в различной скорости сортировки данных разными методами при разном количестве входных значений. К примеру: сортировка подсчетом отсортировала два числа за одну итерацию, как и сортировка обмена, когда сортировка выбора - за три итерации. Но при этом, сортировка выбора отсортировала пять чисел за двенадцать итераций, когда сортировка обмена и подсчетом - за шестнадцать. Данный эксперимент был важен тем, что наглядно показывает различность между методами сортировок данных [5].

ГЛАВА 2. СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ СОРТИРОВКИ

2.1 Практика сортировки данных в Excel

Сортировка в Excel — это встроенная функция анализа данных. С помощью нее можно выставить фамилии в алфавитном порядке, отсортировать средний балл абитуриентов по возрастанию или убыванию, задать порядок строк в зависимости от цвета или значка и т.д. Также с помощью этой функции можно быстро придать таблице удобный вид, что позволит пользователю быстрее находить необходимую информацию, анализировать ее и принимать решения. [5]

Существует два способа открыть меню сортировки:

Щелкнуть правой кнопкой мыши по таблице. Выбрать «Сортировку» и способ.

Открыть вкладку «Данные» - диалоговое окно «Сортировка».

Часто используемые методы сортировки представлены одной кнопкой на панели задач:

Сортировка таблицы по отдельному столбцу:

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

Далее действуем в зависимости от поставленной задачи. Если нужно выполнить простую сортировку по возрастанию/убыванию (алфавиту или обратно), то достаточно нажать соответствующую кнопку на панели задач. Когда диапазон содержит более одного столбца, то Excel открывает диалоговое окно вида:Чтобы сохранилось соответствие значений в строках, выбираем действие «автоматически расширить выделенный диапазон». В противном случае отсортируется только выделенный столбец – структура таблицы нарушится.

Если выделить всю таблицу и выполнить сортировку, то отсортируется первый столбец. Данные в строках станут в соответствии с положением значений в первом столбце. [11]

СОРТИРОВКА ПО ЦВЕТУ ЯЧЕЙКИ И ПО ШРИФТУ

Программа Excel предоставляет пользователю богатые возможности форматирования. Следовательно, можно оперировать разными форматами.

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

Выделяем столбец – правая кнопка мыши – «Сортировка».

Из предложенного списка выбираем «Сначала ячейки с выделенным цветом».

Соглашаемся «автоматически расширить диапазон».

Программа отсортировала ячейки по акцентам. Пользователь может самостоятельно выбрать порядок сортировки цвета. Для этого в списке возможностей инструмента выбираем «Настраиваемую сортировку».

В открывшемся окне вводим необходимые параметры:

Здесь можно выбрать порядок представления разных по цвету ячеек.

По такому же принципу сортируются данные по шрифту.

СОРТИРОВКА В EXCEL ПО НЕСКОЛЬКИМ СТОЛБЦАМ

Как задать порядок вторичной сортировки в Excel? Для решения этой задачи нужно задать несколько условий сортировки.

Открываем меню «Настраиваемая сортировка». Назначаем первый критерий.

Нажимаем кнопку «Добавить уровень».

Появляются окошки для введения данных следующего условия сортировки. Заполняем их.

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

СОРТИРОВКА СТРОК В EXCEL

По умолчанию сортируются данные по столбцам. Как осуществить сортировку по строкам в Excel:

В диалоговом окне «Настраиваемой сортировки» нажать кнопку «Параметры».

В открывшемся меню выбрать «Столбцы диапазона».

Нажать ОК. В окне «Сортировки» появятся поля для заполнения условий по строкам.

Таким образом выполняется сортировка таблицы в Excel по нескольким параметрам. [6]

СЛУЧАЙНАЯ СОРТИРОВКА В EXCEL

Встроенные параметры сортировки не позволяют расположить данные в столбце случайным образом. С этой задачей справится функция СЛЧИС.

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

Ставим курсор в соседнюю ячейку (слева-справа, не важно). В строку формул вводим СЛЧИС(). Жмем Enter. Копируем формулу на весь столбец – получаем набор случайных чисел.

Теперь отсортируем полученный столбец по возрастанию /убыванию – значения в исходном диапазоне автоматически расположатся в случайном порядке.

ДИНАМИЧЕСКАЯ СОРТИРОВКА ТАБЛИЦЫ В MS EXCEL

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

Есть набор простых чисел, которые нужно отсортировать по возрастанию.

Ставим курсор в соседнюю ячейку и вводим формулу: =НАИМЕНЬШИЙ(A:A;СТРОКА(A1)). Именно так. В качестве диапазона указываем весь столбец. А в качестве коэффициента – функцию СТРОКА со ссылкой на первую ячейку.

Изменим в исходном диапазоне цифру 7 на 25 – «сортировка» по возрастанию тоже изменится.

Если необходимо сделать динамическую сортировку по убыванию, используем функцию НАИБОЛЬШИЙ.

Для динамической сортировки текстовых значений понадобятся формулы массива.

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

Выделяем столбец и даем ему имя «Фрукты». Для этого в поле имен, что находится возле строки формул вводим нужное нам имя для присвоения его к выделенному диапазону ячеек. [10]

В соседней ячейке (в примере – в В5) пишем формулу:  Так как перед нами формула массива, нажимаем сочетание Ctrl + Shift + Enter. Размножаем формулу на весь столбец.

Если в исходный столбец будут добавляться строки, то вводим чуть модифицированную формулу:  Добавим в диапазон "фрукты" еще одно значение "помело" и проверим:

Впоследствии при добавлении данных в таблицу процесс сортирования будет выполняться автоматически.

2.2 Сравнение алгоритмов сортировки

Алгоритмы сортировок очень широко применяются в программировании, но иногда программисты даже не задумываются какой алгоритм работает лучше всех (под понятием «лучше всех» имеется ввиду сочетание быстродействия и сложности как написания, так и выполнения).
Для обеспечения наилучших результатов все представленные алгоритмы будут сортировать целочисленный массив из 200 элементов. Компьютер, на котором будет проводится тестирование имеет следующие характеристики: процессор AMD A6-3400M 4x1.4 GHz, оперативная память 8 GB, операционная система Windows 10 x64 build 10586.36. [9]

Для проведения исследования были выбраны следующие алгоритмы сортировки:

Selection sort (сортировка выбором) – суть алгоритма заключается в проходе по массиву от начала до конца в поиске минимального элемента массива и перемещении его в начало. Сложность такого алгоритма O(n2).

Bubble sort (сортировка пузырьком) – данный алгоритм меняет местами два соседних элемента, если первый элемент массива больше второго. Так происходит до тех пор, пока алгоритм не обменяет местами все неотсортированные элементы. Сложность данного алгоритма сортировки равна O(n^2).

Insertion sort (сортировка вставками) – алгоритм сортирует массив по мере прохождения по его элементам. На каждой итерации берется элемент и сравнивается с каждым элементом в уже отсортированной части массива, таким образом находя «свое место», после чего элемент вставляется на свою позицию. Так происходит до тех пор, пока алгоритм не пройдет по всему массиву. На выходе получим отсортированный массив. Сложность данного алгоритма равна O(n^2).

Quick sort (быстрая сортировка) – суть алгоритма заключается в разделении массива на два под-массива, средней линией считается элемент, который находится в самом центре массива. В ходе работы алгоритма элементы, меньшие чем средний будут перемещены в лево, а большие в право. Такое же действие будет происходить рекурсивно и с под-массива, они будут разделяться на еще два под-массива до тех пор, пока не будет чего разделать (останется один элемент). На выходе получим отсортированный массив. Сложность алгоритма зависит от входных данных и в лучшем случае будет равняться O(n×2log2n). В худшем случае O(n^2). Существует также среднее значение, это O(n×log2n). [7]

Comb sort (сортировка расческой) – идея работы алгоритма крайне похожа на сортировку обменом, но главным отличием является то, что сравниваются не два соседних элемента, а элементы на промежутке, к примеру, в пять элементов. Это обеспечивает от избавления мелких значений в конце, что способствует ускорению сортировки в крупных массивах. Первая итерация совершается с шагом, рассчитанным по формуле (размер массива)/(фактор уменьшения), где фактор уменьшения равен приблизительно 1,247330950103979, или округлено до 1,3. Вторая и последующие итерации будут проходить с шагом (текущий шаг)/(фактор уменьшения) и будут происходить до тех пор, пока шаг не будет равен единице. Практически в любом случае сложность алгоритма равняется O(n×log2n).

Для проведения тестирования будет произведено по 5 запусков каждого алгоритма и выбрано наилучшее время. Наилучшее время и используемая при этом память будут занесены в таблицу. Также будет проведено тестирование скорости сортировки массива размером в 10, 50, 200 и 1000 элементов чтобы определить для каких задач предназначен конкретный алгоритм.

Полностью неотсортированный массив:

Частично отсортированный массив (половина элементов упорядочена):



Результаты, предоставленные в графиках:

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

ЗАКЛЮЧЕНИЕ

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

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

С целью улучшения временных характеристик сортировки данных методом вычисления адреса (хеширования) вместо линейных односвязных списков предлагается использовать двусвязные линейные списки, дополнительно создать массив указателей на последние элементы линейных двусвязных списков и применить интерполяционный поиск для поиска места вставки элемента в данный список. Наиболее эффективными методами сортировок массивов данных являются сортировки, использующие методы вставок : простая сортировка вставками, сортировка двоичными вставками, сортировка Шелла, сортировка с вычислением адреса (хеширования). Одна их самых быстрых сортировок этой группы – метод хеширования. Известный способ реализации этой сортировки – использование одномерного массива указателей на линейные односвязные списки. К каждому ключу применяется некоторая функция f (функция, сохраняющая порядок) для вычисления индекса в одномерном массиве указателей. Затем элемент включается в соответствующий линейный односвязный упорядоченный список Одним из основных недостатков данного алгоритма сортировки является проход наибольшего элемента по всему линейному списку, что делает данный алгоритм медленным для случая сортировки по возрастанию значений элементов.

Таким образом, худшим случаем для данной реализации сортировки с вычислением адреса являетсясортировка упорядоченной по возрастанию последовательности, а лучшим случаем – сортировка упорядоченной по убыванию последовательности, так как элементы вставляются в начало линейного односвязного списка. Для решения данной проблемы были разработаны следующие пути улучшения алгоритма сортировки с вычислением адреса: – использование линейных двусвязных списков вместо линейных односвязных списков; – создание одномерного массива указателей на последние элементы линейных двусвязных списков; – применение интерполяционного поиска, позволяющего предсказать положение включаемого элемента в список, и тем самым найти короткий путь прохождения его через данный список (от начала или от конца). Линейные двусвязные списки в данном улучшении позволяют добавлять сразу не только наименьший элемент в начало, но и наибольший элемент в конец списка. Помимо этого, можно проходить по списку не только в направлении от начала к концу, но и от конца к началу для быстрого нахождения места включаемого элемента

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. А.В. Левитин. Глава 4. Метод декомпозиции: Быстрая сортировка // Алгоритмы: введение в разработку и анализ. - М.: «Вильямс», 2006. - С. 174-179. 
2. Вирт Н. Алгоритмы и структуры данных. — М.: ДМК Пресс, 2012. — 272 с.
3. Горбунова О.В., Иванова О.А. // Алгоритм работы учителя // Школьные технологии. 2015. № 3. С. 124-142
4. Г. В. Электрическая машина Голлерита для подсчета статистических данных//В. О. Ф.Э.М. -1895. -№ 225. -С. 193-201.
5. Дупленко А. Г. Сравнительный анализ алгоритмов сортировки данных в массивах//Молодой ученый. -2013. -№ 8. -С. 50-53.
6. Кнут Д. Э. Искусство программирования, т.3. Сортировка и поиск. -М.: Издательский дом «Вильямс», 2010.
7. Никитин Ю. Б. Сложность алгоритмов сортировки на частично упорядочен-ных множествах: автореферат дис. … канд. физ.-мат. наук: 01.01.09/Никитин Юрий Бо-рисович. -Москва, 2001. -80 с.
8. Кнут Дональд. Искусство программирования, том 3. Сортировка и поиск. 2-ое изд.-М.: Вильямс, 2007. -824 с.
9. Кормен Томас, Лейзерсон Чарльз, Ривест Рональд, Штайн Клиффорд. Алгоритмы: построение и анализ. 2-ое изд.-М.: Вильямс, 2006. 1296 с.
10. Седжвик Роберт. Фундаментальные алгоритмы на C.-С-Пб.: ДиаСофтЮП, 2003. -672 с.
11. Музычкин П.А., Романова Ю.Д. // Информационная система // Плехановский научный бюллетень. 2015. № 1 (7). С. 135-178.
12. Стивенс Р. Delphi. Готовые алгоритмы. — СПб.: Питер, 2010. — 384 с.
13. Чередник А.В. // основы концепции создания учебных электронных изданий // Вестник МГУП имени Ивана Федорова. 2013. № 5. С. 101-108
14. Сортировка массива. http://edunow.su/site/content/algorithms/sortirovka_massiva (доступ 29.10.2019). \
15. Кузнецов С.Д. Методы сортировки и поиска. http://citforum.ru/programming/theory/sorting/sorting1.shtml (доступ 29.10.2019).