инфороматика Алгоритмы сортировки одномерных массивов Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы. Практически каждый алгоритм сортировки можно разбить на три части: - сравнение, определяющее упорядоченность пары элементов; - перестановку, меняющую местами пару элементов; - собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, сока все элементы множества не будут упорядочены. Подобными свойствами обладают и те алгоритмы сортировки, которые рассмотрены ниже. Они отобраны из множества алгоритмов, потому что, во-первых, наиболее часто используются, а во-вторых, потому что большинство остальных алгоритмов является различными модификациями описанных здесь. Алгоритмы разделяются на две группы: 3 прямых (Метод Пузырька, Метод прямого выбора, Метод прямого включения) и 3 улучшенных (Метод Хора, Метод Шела, Пирамидальная сортировка) Метод пузырька. ( метод назван также обменной сортировкой с выбором) . Идея этого метода отражена в его названии. Самые легкие элементы массива "всплывают" наверх, самые "тяжелые" - тонут. Алгоритмически это можно реализовать следующим образом. Мы будем просматривать весь массив "снизу вверх" и менять стоящие рядом элементы в том случае, если "нижний" элемент меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий” элемент всего массива. Теперь повторим всю операцию для оставшихся неотсортироваными N-1 элементов (т.е. для тех, которые лежат "ниже" первого. Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности. Немного более эффективным, но таким наглядным является второй метод. Метод прямого выбораСогласно этому методу,начиная с первой записи таблицы, осуществляется поиск элемента,имеющего наименьшее значение ключа. После того, как этот элемент найден, он меняется местами с первой записью в таблице. В результате такой перестановки запись с наименьшим значением ключа помещается в первую позицию в таблице. Затем, начиная со второго элемента таблицы, осуществляется поиск второго наименьшего ключа. Найденный элемент меняется местами со вторым элементом таблицы. Этот процесс продолжается до тех пор, пока все записи не будут расположены в порядке возрастания кодов ключа. Число сравнений в данном методе равно n(n-1)/2 (в среднем порядка n**2),где n - количество записей в таблице. Максимальное количество перестановок при такой сортировке равно (n-1). Метод прямого включения Сортировка вставками, так же как и сортировка методов простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов. Сортировка методом прямого включения, как и все описанные выше, производится по шагам. На k-м шаге считается, что часть массива, содержащая первые k-1 элементов, уже упорядочена, то есть a[1] Метод Хoopа Этот метод, называемый также быстрой сортировкой. Суть метода заключается в том, чтобы найти такой элемент множества, подлежащего сортировке, который разобьет его на два подмножества: те элементы, что меньше делящего элемента, и те, что не меньше его. Эту идею можно реализовать многими способами. Метод Шелла Основная идея этого алгоритма заключается в том, чтобы в начале ycтpанить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как видно, интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми). Сортировка выбором На этот раз при просмотре мaccива мы будем искать наименьший элемент, Сравнивая его с первым. Если такой элемент найден, поменяем его местами с первым. Затем повторим эту операцию, но начнем не с первого элемента, а со второго. И будем продолжать подобным образом, пока не рассортируем весь массив. ^ Алгоритмы поиска в упорядоченных таблицах Одним из эффективных методов поиска в больших отсортированных массивах является бинарный поиск, или поиск методом деления пополам. В основе этого метода лежит идея целенаправленных последовательных догадок о предполагаемом местоположении искомого элемента. Алгоритм выполнения бинарного поиска в упорядоченном массиве: Вместо просмотра подряд всех элементов массива делим его пополам. Так как массив отсортирован, то сравнивая искомый элемент со значением среднего элемента массива, мы в можем сделать вывод, может ли быть элемент с таким значением в массиве и в каокй половине он находится, т.е. определить область дальнейшего поиска. Затем делится пополам та часть массива, в которой находится элемент, и так до тех пор, пока рассматриваемая часть массива получится состоящей из одного элемента. ^ Бинарное дерево поиска Двоичное дерево - это дерево, у которого каждый узел имеет не более двух наследников. Пример бинарного дерева приведен на рис. 2. Предполагая, что k содержит значение, хранимое в данном узле, мы можем сказать, что бинарное дерево обладает следующим свойством: у всех узлов, расположенных слева от данного узла, значение соответствующего поля меньше, чем k, у всех узлов, расположенных справа от него, - больше. Вершину дерева называют его корнем, узлы, у которых отсутствуют оба наследника, называются листьями. Корень дерева на рис. 2 содержит 20, а листья - 4, 16, 37 и 43. Высота дерева - это длина наидлиннейшего из путей от корня к листьям. В нашем примере высота дерева равна 2. ^ Рис. 2: Двоичное дерево Чтобы найти в дереве какое-то значение, мы стартуем из корня и движемся вниз. Например, для поиска числа 16, мы замечаем, что 16 7, и потому мы движемся вправо. Третья попытка успешна - мы находим элемент с ключом, равным 16. Каждое сравнение вдвое уменьшает количество оставшихся элементов. В этом отношении алгоритм похож на двоичный поиск в массиве. Однако, все это верно только в случаях, когда наше дерево сбалансировано. На рис. 3 показано другое дерево, содержащее те же элементы. Несмотря на то, что это дерево тоже бинарное, поиск в нем похож, скорее, на поиск в односвязном списке, время поиска увеличивается пропорционально числу запоминаемых элементов. ^ Рис. 3: Несбалансированное бинарное дерево Вставка и удаление Чтобы лучше понять, как дерево становится несбалансированным, посмотрим на процесс вставки пристальнее. Чтобы вставить 18 в дерево на рис. 2 мы сначала должны найти это число. Поиск приводит нас в узел 16, где благополучно завершается. Поскольку 18 > 16, мы попросту добавляет узел 18 в качестве правого потомка узла 16 (рис. 4). На этом примере хорошо видно, как возникает несбалансированность дерева. Если данные поступают в возрастающем порядке, каждый новый узел добавляется справа от последнего вставленного. Это приводит к одному длинному списку. Обратите внимание: чем более "случайны" поступающие данные, тем более сбалансированным получается дерево. Удаления производятся примерно так же - необходимо только позаботиться о сохранении структуры дерева. Например, если из дерева на рис. 4 удаляется узел 20, его сначала нужно заменить на узел 37. Это даст дерево, изображенное на рис. 5. Рассуждения здесь примерно следующие. Нам нужно найти потомка узла 20, справа от которого расположены узлы с большими значениями. Таким образом, нам нужно выбрать узел с наименьшим значением, расположенный справа от узла 20. Чтобы найти его, нам и нужно сначала спуститься на шаг вправо (попадаем в узел 38), а затем на шаг влево (узел 37); эти двухшаговые спуски продолжаются, пока мы не придем в концевой узел, лист дерева. Рис. 4: Бинарное дерево после добавления узла 18 Рис. 5: Бинарное дерево после удаления узла 20