Файл: Алгоритмы сортировки данных (Алгоритмы устойчивой сортировки).pdf

Наиболее часто внешняя сортировка используется в СУБД. Основным понятием при использовании внешней сортировки является понятие отрезка. Например, в некотором файле А есть одномерный массив:

12 35 65 0 24 36 3 5 84 90 6 2 30

Поделим массив на отрезки:

12 35 65 | 0 24 36 | 3 5 84 90 | 6 | 2 30

Можно сказать, что массив в файле А состоит из 5 отрезков.

Например, в некотором файле B есть одномерный массив:

1 2 3 4 5 6 7 8 9 10

Поделим массив на отрезки:

| 1 2 3 4 5 6 7 8 9 10 |

Можно сказать, что массив в файле B состоит из 1 отрезка.

Например, в некотором файле А есть одномерный массив:

20 17 16 14 13 10 9 8 6 4 3 2 0

Поделим массив на отрезки:

| 20 | 17 | 16 | 14 | 13 | 10 | 9 | 8 | 6 | 4 | 3 | 2 | 0 |

Можно сказать, что массив в файле А состоит из 13 отрезков.

Идея большинства методов заключается в расчленении данных на ряд последовательностей помещающихся в оперативную память. Далее применяется один из методов внутренней сортировки, после чего последовательности сливаются. Чем больше объём оперативной памяти, тем длиннее будут последовательности и, следовательно, тем меньшим окажется их количество, что увеличит скорость сортировки.

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

Основные методы сортировок:

Естественная сортировка (метод естественного слияния)

Сортировка методом двухпутевого сбалансированного слияния

Сортировка методом n-путевого слияния.

Многофазная сортировка (Фибоначчиевая)

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

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

К наиболее известным алгоритмам внешних сортировок относятся:

сортировки слиянием (простое слияние и естественное слияние);

улучшенные сортировки (многофазная сортировка и каскадная сортировка).

Из представленных внешних сортировок наиболее важным является метод сортировки с помощью слияния. Прежде чем описывать алгоритм сортировки слиянием введем несколько определений.

Основным понятием при использовании внешней сортировки является понятие серии. Серия (упорядоченный отрезок) – это последовательность элементов, которая упорядочена по ключу.

Количество элементов в серии называется длиной серии. Серия, состоящая из одного элемента, упорядочена всегда. Последняя серия может иметь длину меньшую, чем остальные серии файлов. Максимальное количество серий в файле N (все элементы не упорядочены). Минимальное количество серий одна (все элементы упорядочены).

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

Распределение – это процесс разделения упорядоченных серий на два и несколько вспомогательных файла.

Фаза – это действия по однократной обработке всей последовательности элементов. Двухфазная сортировка – это сортировка, в которой отдельно реализуется две фазы: распределение и слияние. Однофазная сортировка – это сортировка, в которой объединены фазы распределения и слияния в одну.

Двухпутевым слиянием называется сортировка, в которой данные распределяются на два вспомогательных файла. Многопутевым слиянием называется сортировка, в которой данные распределяются на N (N > 2) вспомогательных файлов.

Общий алгоритм сортировки слиянием

Сначала серии распределяются на два или более вспомогательных файлов. Данное распределение идет поочередно: первая серия записывается в первый вспомогательный файл, вторая – во второй и так далее до последнего вспомогательного файла. Затем опять запись серии начинается в первый вспомогательный файл. После распределения всех серий, они объединяются в более длинные упорядоченные отрезки, то есть из каждого вспомогательного файла берется по одной серии, которые сливаются. Если в каком-то файле серия заканчивается, то переход к следующей серии не осуществляется. В зависимости от вида сортировки сформированная более длинная упорядоченная серия записывается либо в исходный файл, либо в один из вспомогательных файлов. После того как все серии из всех вспомогательных файлов объединены в новые серии, потом опять начинается их распределение. И так до тех пор, пока все данные не будут отсортированы.

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

количество фаз в реализации сортировки;

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

3.3. Блинная сортировка

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

По поводу этой задачи хочется отметить два интересных факта. Во-первых, способ нахождения достаточно эффективного (хотя и неоптимального) решения был в свое время предложен небезызвестным Биллом Гейтсом, пока тот был еще студентом. Этот алгоритм, предложенный в 1979 году, оставался наиболее эффективным вплоть до 2008, когда результат был превзойден. Во-вторых, как было доказано впоследствии, задача нахождения оптимального решения относится к классу NP-полных. Также Гейтсом и его руководителем Христосом Пападимитриу был предложен усложненный вариант задачи, известный как задача о подгоревших блинах.

Задача о подгоревших блинах

В этой форме задачи каждый элемент, помимо размера, имеет еще и бинарный атрибут «направление», то есть у каждого «блина» одна сторона подгоревшая, а другая румяная; результатом решения задачи является стопка, упорядоченная по размеру, но, помимо этого, все «блины» лежат подгоревшей стороной вниз. Не вдаваясь в подробности, скажем, что и эта задача NP-полна, и что в общем случае известны ее достаточно эффективные, но неоптимальные решения. Тем не менее, существуют ограничения на данные, при выполнении которых задача становится полиномиальной. Для рассматриваемой задачи такими данными являются простые перестановки. Чтобы понять, что это такое, рассмотрим перестановку чисел от 1 до 7: 2647513. Заметим, что выделенная жирным шрифтом последовательность сама является перестановкой чисел от 4 до 7 (называется блоком). Простые перестановки — это те, где нет нетривиальных блоков (блоков длины 1 и n).

За образной постановкой задачи, когда элементы представлены подгоревшими блинами, сложно разглядеть тот факт, что она имеет биологическое значение. Тем не менее, распространенной мутацией является переворот в молекуле ДНК, и если посчитать минимальное количество переворотов, необходимое для преобразования одной молекулы в другую (без рассмотрения более мелких точечных мутаций), то можно примерно оценить родство организмов. Например, геном человека и мыши разделен всего лишь порядка 120 глобальными мутациями; признаюсь, я раньше полагал, что между этими видами разницы гораздо больше…

Генетический алгоритм решения задачи о подгоревших блинах

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

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

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

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

Достаточно ли одного переворота блина для решения задачи? Мы легко это можем проверить, поместив часть колонии в опасную для нее среду. Помещенные в антибиотик бактерии не выжили, и мы продолжаем наблюдать за оставшимися. Пройдет еще два-три периода, и, наконец, в группе бактерий, помещенных в антибиотик, останутся живые. «Коллективный разум» справился с задачей!

Итоги

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

Заключение

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

Практически каждый алгоритм сортировки можно разбить на три части:

- сравнение, определяющее упорядоченность пары элементов;

- перестановку, меняющую местами пару элементов;

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

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

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

Термин «алгоритм» применяют весьма широко. Алгоритм – это организованная последовательность действий, допустимых в определенных случаях. Умение разбить задачу на подзадачи, распределение решений этих задач, определение выходных параметров способствуют легкому восприятию любой ситуации.