Алгоритм сортировки методом вставки

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

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

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 элемен­тов, тогда как алгоритму двоичного поиска, в самом худшем случае, потребуется проверить только log₂n элементов (логарифм по­казывает, сколько раз число п можно разделить на два).

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

В наилучшем случае применение алгоритма сортировки мето­дом вставки к списку из п элементов потребует выполнения n-1 сравнений. (Второй элемент сравнивается с одним элементом (пер­вым), третий элемент — с одним элементом (вторым) и т. д.)

Наихудший сценарий имеет место в том случае, когда каждый опорный элемент потребуется сравнивать со всеми впереди стоя­щими элементами. Первый опорный элемент (второй элемент спи­ска) сравнивается с одним элементом, второй опорный элемент (третий элемент списка) - с двумя элементами и т. д. Следователь­но, общее количество сравнений при сортировке списка из п эле­ментов составит 1 + 2 + 3 +... + (n - 1), что эквивалентно п(п- 1)/2 или (1/2)(n² - п).

В среднем при сортировке методом вставки можно ожидать, что каждый опорный элемент потребуется сравнить с половиной предшествующих ему элементов. В этом случае общее количество выполненных сравнений будет вдвое меньше, т. е. (1/4)(n2 — п).

 

Количество сравнений, выполненных алгоритмом сортировки методом встав­ки, позволяет оценить вре­мя, которое потребуется для выполнения сортиров­ки. Эта оценка показана на графике (рис. 6), который построен по оценкам рабо­ты алгоритма в наихудшем случае, когда для списка длиной п требуется выпол­нить не менее (1/2)(n²-n) сравнений элементов. При увеличении длины списка на одно и то же количество элементов время, необ ХОДИМОЕ ДЛЯ СОрТИрОВКИ списка, все больше и больше возрастает. Та­ким образом, с увеличе­нием длины списка эф­фективность данного ал­горитма уменьшается.

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

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

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

Способ обозначения, используемый для определения этих классов, иногда называют тета-классами. Алгоритмы, графики которых имеют параболическую форму (например, сортировка методом вставки), относятся к классу Θ (n²), алгоритмы, графики которых имеют логарифмическую форму (например, двоичный поиск), - к классу Θ (lg п). Таким образом, любой алгоритм из тета-класса Θ (lg n) по самой свой сути всегда более эффективен, чем алгоритм из тета-класса Θ (п²).