Алгоритм сортировки методом вставки
В этом алгоритме решается задача сортировки списка имен в алфавитном порядке. При этом необходимо отсортировать список путем перестановки его элементов, не перемещая весь список в другое место. Подобное ограничение типично для компьютерных приложений, где стремятся наиболее эффективно использовать весь доступный объем памяти.
Для их сортировки должны повторяться следующие действия. Поднять карточку с именем, первую в неотсортированной части списка, сдвинуть вниз карточки с именами, которые находятся ниже по алфавиту, чем имя на взятой карточке, а затем поместить эту карточку на освободившееся место в списке. Текст программы сортировки на языке псевдокода выглядит так:
procedure Сортировка (<список>) assign N the value 2;
while (значение N не превышает <длина списка>)
do (Выбрать N-й элемент списка в качестве опорного; Переместить этот элемент во временное хранилище, оставив в списке пустое место;
while (над пустым местом есть имя, которое по алфавиту размещается ниже, чем опорный элемент)
do (переместить имя, находящееся над пустым местом вниз, оставив в прежней позиции пустое место); Поместить опорный элемент на пустое место в списке assign N the value N+1
здесь N - счетчик, параметр <длина списка> - количество элементов в списке.
Программа сортирует список, многократно повторяя следующие действия: «Элемент извлекается из списка, а затем вставляется на надлежащее ему место».
Каждое выполнение тела внешнего цикла приводит к тому, что внутренний цикл инициализируется и выполняется до тех пор, пока не будет выполнено условие его окончания. Условие окончания внешнего цикла выполняется, когда значение счетчика N превысит длину сортируемого списка.
Управление внутренним циклом инициализируется, когда опорный элемент извлекается из списка и в нем образуется пустое место. Операция модификации включает перемещение расположенных выше элементов на пустое место вниз, в результате чего свободное место перемещается вверх по списку. Условие окончания выполняется, когда пустое место или находится непосредственно под именем, которое по алфавиту размещается выше опорного значения или же достигает верхней позиции списка.
ЭФФЕКТИВНОСТЬ АЛГОРИТМОВ
Современные вычислительные машины способны выполнять миллионы операций в секунду, однако эффективность по-прежнему остается важнейшим аспектом разработки алгоритмов. Часто выбор между эффективным и неэффективным решением задачи может на самом деле означать выбор между реализуемым и нереализуемым способом ее решения.
Рассмотрим задачу, с которой сталкивается секретарь университета при поиске личных дел студентов и их заполнении. В университете на протяжении любого семестра числится около 30 тысяч студентов. Чтобы найти личное дело некоторого студента, секретарь должен выполнить поиск по его идентификационному номеру в общем списке. Почувствует ли секретарь разницу при поиске между алгоритмом последовательного и двоичного поиска?
Алгоритм последовательного поиска начинает работу с начала списка и последовательно сравнивает каждый выбираемый элемент с искомым числом. Средняя глубина поиска будет равна половине длины списка из 15-ти тысяч элементов. Если выборка каждого дела из памяти выполняется за 10 мс, то среднее время поиска будет составлять 150 секунд. Этот вариант совершенно неприемлем.
Алгоритм двоичного поиска сравнивает искомое значение со средним элементом списка. Если это не искомый элемент, то область поиска сразу же сужается до половины исходного списка. После второго этапа область поиска в большинстве случаев сократится до 7 500 дел и т. д. Искомое значение будет найдено при выборе, максимум 15 элементов списка. Процесс поиска нужного личного дела потребует не более 0,15 секунды, то есть мгновенно.
В общем случае такой анализ осуществляется в более широком контексте. Хотя выше рассматривался список определенной длины, эти рассуждения можно обобщить на случай списка произвольной длины. При применении к списку из п элементов алгоритма последовательного поиска в среднем потребуется проверить п/2 элементов, тогда как алгоритму двоичного поиска, в самом худшем случае, потребуется проверить только log2n элементов (логарифм показывает, сколько раз число п можно разделить на два).
Аналогичным образом можно проанализировать алгоритм сортировки методом вставки. Поскольку основным действием в реализации этого алгоритма является сравнение двух имен, то необходимо подсчитать количества таких сравнений, которые потребуется выполнить при сортировке списка длиной п элементов.
В наилучшем случае применение алгоритма сортировки методом вставки к списку из п элементов потребует выполнения n-1 сравнений. (Второй элемент сравнивается с одним элементом (первым), третий элемент — с одним элементом (вторым) и т. д.)
Наихудший сценарий имеет место в том случае, когда каждый опорный элемент потребуется сравнивать со всеми впереди стоящими элементами. Первый опорный элемент (второй элемент списка) сравнивается с одним элементом, второй опорный элемент (третий элемент списка) - с двумя элементами и т. д. Следовательно, общее количество сравнений при сортировке списка из п элементов составит 1 + 2 + 3 + ... + (n - 1), что эквивалентно п(п-1)/2 или (1/2)(n2 - п).
В среднем при сортировке методом вставки можно ожидать, что каждый опорный элемент потребуется сравнить с половиной предшествующих ему элементов. В этом случае общее количество выполненных сравнений будет вдвое меньше, т. е. (1/4)(n2 — п).
Количество сравнений, выполненных алгоритмом сортировки методом вставки, позволяет оценить время, которое потребуется для выполнения сортировки. Эта оценка показана на графике (рис. 6), который построен по оценкам работы алгоритма в наихудшем случае, когда для списка длиной п требуется выполнить не менее (1/2)(n2-n) сравнений элементов. При увеличении длины списка на одно и то же количество элементов время, необХОДИМОЕ ДЛЯ СОрТИрОВКИсписка, все больше и больше возрастает. Таким образом, с увеличением длины списка эффективность данного алгоритма уменьшается.
При использовании алгоритма двоичного поиска в наихудшем случае для поиска в списке из п элементов потребуется проанализировать не более log2 n элементов. На рис. 7 представлен график, построенный по результатам анализа времени, необходимого для выполнения алгоритма при различной длине сортируемого списка. Темпы роста времени выполнения алгоритма снижаются по мере увеличения длины списка, т. е. эффективность алгоритма двоичного поиска возрастает с увеличением длины списка.
Основным отличием между этими графиками является их общая форма, которая определяется типом отображаемого выражения. Все линейные выражения изображаются прямой линией, все квадратичные выражения - параболической кривой, а все логарифмические выражения порождают логарифмическую кривую.
Форма графика, представляющего зависимость времени выполнения алгоритма от объема входных данных, отражает общие характеристики эффективности алгоритма. Поэтому алгоритмы принято классифицировать согласно форме их графиков, построенных для самого неблагоприятного случая.
Способ обозначения, используемый для определения этих классов, иногда называют тета-классами. Алгоритмы, графики которых имеют параболическую форму (например, сортировка методом вставки), относятся к классу Θ (n2), алгоритмы, графики которых имеют логарифмическую форму (например, двоичный поиск), - к классу Θ (lg п). Таким образом, любой алгоритм из тета-класса Θ (lg n) по самой свой сути всегда более эффективен, чем алгоритм из тета-класса Θ (п2).