- •Предназначено студентам очной формы обучения.
- •Введение
- •1. Оценки сложности алгоритмов
- •1.1. Определение понятия алгоритм
- •1.2. Оценка сложности алгоритмов
- •2. Линейные структуры данных
- •2.1. Методы организации и хранения линейных списков
- •2.2. Операции со списками при последовательном хранении
- •2.3. Операции со списками при связном хранении
- •2.4. Организация двусвязных списков
- •Задания для самоконтроля
- •2.5. Стеки и очереди
- •2.6. Сжатое и индексное хранение линейных списков
- •3. Сортировка и слияние
- •3.1. Пузырьковая сортировка
- •3.2. Сортировка вставкой
- •3.3. Сортировка посредством выбора
- •3.4. Сортировка квадратичной выборкой
- •3.5. Слияние списков
- •3.6. Сортировка списков путем слияния
- •3.7. Быстрая и распределяющая сортировки
- •4. Поиск
- •4.1. Последовательный поиск
- •4.2. Бинарный поиск
- •4.4. Методы вычисления адреса
- •4.5. Выбор в линейных списках
- •5. Рекурсия
- •6. Алгоритмы на графах и сетях
- •6.1. Исходные понятия
- •6.2. Матричные представления графов
- •6.3. Другие представления графов
- •6.4. Поиск в глубину как система исследования графа
- •6.5. Перебор цепей поиском в глубину
- •6.6. Взвешенные графы. Ориентированные графы
- •6.7. Нахождение фундаментального множества циклов
- •6.8. Выявление мостов и точек сочленений
- •6.9. Поиск в ширину как система исследования графа
- •6.10. Кратчайшие пути, ведущие от заданного узла X ко всем прочим
- •6.11. Алгоритм Дейкстры нахождения кратчайших путей во взвешенном графе
- •6.12. Улучшения алгоритма Дейкстры
- •6.13. Построение кратчайшего каркаса
- •6.14. Нахождение всевозможных кратчайших путей в графе
- •6.15. Потоковые задачи
- •6.16. Пример практической задачи на графах
- •7. Генераторы случайных и псевдослучайных последовательностей
- •7.1. Общая постановка задачи
- •7.3. Генератор случайных чисел, поставляемый с системой
- •7.4. Генератор с малым кодом
- •7.5. Генератор Парка-Миллера
- •7.6. Улучшенная версия генератора Парка-Миллера
- •7.7. Быстрый генератор для 32-битового представления целых и действительных чисел
- •7.8. Алгоритм л'Экюера, комбинирующий две последовательности
- •Оглавление
- •7. Генераторы случайных и псевдослучайных последовательностей 144
- •394026 Воронеж, Московский просп., 14
3.6. Сортировка списков путем слияния
Для получения упорядоченного списка B' последовательность значений В=<K1, K2, …, KN> разделяют на N списков B1=<K1>, B2=<K2>, ..., Bn=<KN>, длина каждого из которых 1. Затем осуществляется функция прохода, при которой М 2 упорядоченных списков B1, B2 ,..., BM заменяется на М/2 (или (М+1)/2) упорядоченных списков, B(2i-1) и B(2i) ( 2i M ) и добавлением BMпри нечетном М. Проход повторяется до тех пор пока не получится одна последовательность длины N.
Приведем пример сортировки списка путем использования слияния, отделяя последовательности косой чертой, а элементы запятой.
Пример:
9 / 7 / 18 / 3 / 52 / 4 / 6 / 8 / 5 / 13 / 42 / 30 / 35 / 26;
7, 9 / 3, 18 / 4 / 52 / 6 / 8 / 54 / 13 / 30 / 42 / 26 / 35;
3, 7, 9, 18 / 4, 6, 8, 52 / 5, 13, 30, 42 / 26, 35;
3, 4, 6, 7, 8, 9, 18, 52 / 5, 13, 26, 30, 35, 42;
3, 4, 5, 6, 7, 8, 9, 13, 18, 26, 30, 35, 42, 52.
Количество действий, требуемое для сортировки слиянием, равно O(N*log2(N)), так как за один проход выполняется N сравнений, а всего необходимо осуществить log2(N) проходов. Сортировка слиянием является очень эффективной и часто применяется для больших N, даже при использовании внешней памяти.
Функция smerge упорядочивает массив s сортировкой слиянием, используя описанную ранее функцию merge.
/* сортировкаслиянием */
double *smerge (double *s, int m, int n)
{
int l,low,up;
double *merge (double *, int, int, int);
l=1;
while(l<=(n-m))
{
low=m;
up=m-1;
while (l+up<n)
{
up=(low+2*l-1 < n) ? (low+2*l-1) : n ;
merge (s,low,up,l);
low=up-1;
}
l*=2;
}
return(s);}
Для сортировки массива путем слияния удобно использовать рекурсию. Составим рекурсивную функцию srecmg для сортировки массива либо его части. При каждом вызове сортируемый массив делится на две равных части, каждая из которых сортируется отдельно, а затем происходит их слияние, как это показано на рис.18.
Рис. 18. Схема сортировки слиянием
/* рекурсивная сортировка слиянием 1/2 */
double *srecmg (double *a, int m, int n)
{
double * merge (double *, int, int, int);
double * smerge (double *, int, int);
int i;
if (n>m)
{
i=(n+m)/2;
srecmg(a,m,i);
srecmg(a,i+1,n);
merge(a,m,n,(n-m)/2+1);
}
return (a);
}
Задания для самоконтроля
1. Написать функцию, которая вставляет в упорядоченный линейный список новый элемент. Линейный список хранится связанно.
2. Написать функцию сортировки N целых чисел методом квадратичной выборки.
3. Пусть заданны на входе неупорядоченные списки студентов четырёх клубов С1, С2, С3, С4. Никакой клуб не имеет более 250 членов. Написать программу для определения всех студентов являющихся членами по крайней мере трех клубов. (Для упрощения предположить, что члены клубов перечисляются не по фамилиям, а целыми положительными числами по номерам их студенческих билетов.)
4. Пусть на входе заданно число N, за которым следует N целых чисел G1, G2, …, GN. Написать программу для сортировки последовательности G1, G2, …, GN слияния и печати результирующей последовательности. (Числа для сортировки хранятся с использованием связанного хранения; слияние делается не реальным перемещением, а изменением связей.)