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

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

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

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

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

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

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

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

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

Многофазное слияние даёт ожидаемый результат и на каждом этапе сливает максимальное количество серий если начальное распределение серий по вспомогательным файлам описывается соседними числами Фибоначчи. В общем виде для успешной работы алгоритма с использованием m вспомогательных файлов начальное распределение серий между (m-1) файлами должно описываться суммами соседних чисел Фибоначчи порядка (m2) [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 ПО НЕСКОЛЬКИМ СТОЛБЦАМ