Алгоритмы обработки данных

Министерство образования и науки Российской Федерации 

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ 

 
 
 
 
 
 
В.В. ЛАНДОВСКИЙ 
 
 
 
 
 
 
АЛГОРИТМЫ ОБРАБОТКИ  
ДАННЫХ 
 
Утверждено Редакционно-издательским советом университета  
в качестве учебного пособия 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
НОВОСИБИРСК 
2018 

 

УДК 004.424.5.021 
         Л 222 
 

Рецензенты: 

канд. техн. наук, доцент В.А. Астапчук, 
старший преподаватель С.А. Менжулин 
 
 
 
Работа подготовлена на кафедре автоматизированных систем 
управления для студентов III курса АВТФ направления 09.03.01 – 
«Информатика и вычислительная техника» 
 
 
 
Ландовский В.В. 
Л 222   
Алгоритмы обработки данных: учебное пособие / В.В. Ландовский. – Новосибирск: Изд-во НГТУ, 2018. – 67 с. 

ISBN 978-5-7782-3645-5 

В настоящем пособии рассмотрены две группы алгоритмов: алгоритмы сортировки и алгоритмы на строках. Среди алгоритмов сортировки выделены простые обменные методы, имеющие полиномиальную временную сложность, методы с линейно-логарифмической и 
линейной оценками времени. Представлено описание классических 
алгоритмов быстрого поиска образца в тексте с использованием 
вспомогательных структур, приведены алгоритмы их построения. 
Рассмотрены алгоритмы вычисления редакционного расстояния между строками. 
 
 
 
УДК 004.424.5.021 
 
 
ISBN 978-5-7782-3645-5  
 
 
 
 
 
 
© Ландовский В.В., 2018 
© Новосибирский государственный 
    технический университет, 2018 

 

ВМЕСТО ПРЕДИСЛОВИЯ 

В настоящее время незнание фундаментальных алгоритмов становится нормой среди разработчиков программ. Это неудивительно, так 
как пробелы в базовом образовании компенсируются, с одной стороны, обилием легкодоступных учебных материалов, а с другой – возможностями применения готовых библиотечных рецептов. Нет ничего 
дурного в том, что специалист (в особенности начинающий) заглядывает в поисках информации в первый попавшийся интернет-источник. 
Использование макросредств без их глубокого изучения тоже может 
быть оправданно, если единственными критериями являются скорость 
написания и корректность работы программы. Но если потребуется 
обеспечить достаточную скорость обработки данных, то возможны 
проблемы. В зависимости от таланта и временны´ х рамок один с нуля 
изобретет велосипед, другой наконец-то изучит то, что пропустил в 
школе. И только тот, кто заранее уделил достаточно времени изучению 
основополагающих концепций и приобрел достаточную широту знаний, способен сразу выбрать правильный путь решения задачи. 
Темпы развития компьютерной техники и программного обеспечения в последнее время требуют от специалистов постоянной, почти 
непрерывной актуализации своих знаний. Может показаться, что обучение, не связанное с решением реальных задач, – непозволительная 
роскошь. Однако среди многообразия современных материалов, посвященных отдельным языкам, средствам разработки и конкретным 
прикладным решениям, теряются общие, нестареющие подходы к решению большого класса задач. Меняется главным образом форма: всё 
более дружественные интерфейсы, всё более высокоуровневые средства, высокие скорости обработки и наглядные способы отображения 
информации. Содержание же остается прежним; идеи, которые вот-вот 
отпразднуют вековой юбилей, не теряют своей актуальности. Это позволяет сделать вывод, что незнание фундамента лишает человека возможности занимать твердую позицию и делает его заложником чужих 

коммерческих интересов, связанных с развитием тех или иных программных средств. И, напротив, наличие базовых знаний позволяет 
уверенно адаптироваться к изменениям, быстро осваивать новые технологии. 
В дополнение к сказанному уместно будет процитировать фрагмент из книги одного из ведущих исследователей и преподавателей в 
области информатики Н. Вирта: «Программирование – это искусство 
конструирования. Как можно научить конструкторской, изобретательской деятельности? Есть такой метод: выделить простейшие строительные блоки из многих уже существующих программ и дать их систематическое описание. Но программирование представляет собой 
обширную и разнообразную деятельность, часто требующую сложной 
умственной работы. Ошибочно считать, что ее можно свести к использованию готовых рецептов. В качестве метода обучения нам остается 
тщательный выбор и рассмотрение характерных примеров. Конечно, 
не следует считать, что изучение примеров всем одинаково полезно. 
При этом подходе многое зависит от сообразительности и интуиции 
обучающегося» [1]. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

1. АЛГОРИТМЫ СОРТИРОВКИ 

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

1.1. ПРОСТЫЕ МЕТОДЫ 

В этом разделе рассмотрены простые алгоритмы, в которых процесс сортировки представляет собой последовательность обменов. 
К числу преимуществ этих методов следует отнести минимальный 
объем дополнительной памяти, небольшие константы в оценках времени и, разумеется, простоту реализации. Основной недостаток – 
асимптотика времени выполнения O(n2), где n – количество сортируемых элементов. 

1.1.1. СОРТИРОВКА ПУЗЫРЬКОМ 

Для понимания этого алгоритма полезно изобразить последовательность сортируемых элементов сверху вниз. Разделим последовательность на две части: упорядоченную и неупорядоченную, первая 
располагается сверху, и до начала работы алгоритма она отсутствует.  

i 
0 
1 
2 
3 
4 
– 

4 
4 
1 
1 
1 
1 
1 

6 
6 
4 
2 
2 
2 
2 

3 
3 
6 
4 
3 
3 
3 

1 
1 
3 
6 
4 
4 
4 

5 
5 
2 
3 
6 
5 
5 

2 
2 
5 
5 
5 
6 
6 

2 

1 

1 

1 

2 

2 

2 

3 

3 

5 

 
Рис. 1.1. Пример сортировки пузырьком 

Начало 

i = 0, n – 2 

A[j].key < 
A[j – 1]. key 

tmp = A[j] 
A[j] = A[j – 1] 
A[j – 1] = tmp 

Конец 

A[i], i = 0,…, n – 1 – исходное 
неупорядоченное множество 

j = n – 1, i + 1 

Да 

Нет 

 
Рис. 1.2. Алгоритм сортировки пузырьком 

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

1.1.2. СОРТИРОВКА ВСТАВКАМИ 

Отличие этого метода от предыдущего заключается в том, что элементы перемещаются в упорядоченной части. На каждой итерации 
очередной элемент, находящийся на верхней границе неупорядоченной части, помещается на нужную позицию в отсортированной части 
(вставляется). Очевидно, что уже на первой итерации необходимо 
наличие неупорядоченной части, для этого первым добавляют фиктивный элемент c минимально возможным значением ключа. Пример сортировки вставками показан на рис. 1.3, на рис. 1.4 изображена блоксхема алгоритма. 
Внешний цикл сортировки вставками обязан дойти до конца, а 
внутренний может заканчиваться в произвольный момент. 

1.1.3. СОРТИРОВКА ВЫБОРОМ 

Два предыдущих метода меняли местами только соседние элементы. Эта особенность обеспечивает одинаковую асимптотику как для 
структур данных с последовательным доступом (списков), так и для