- •Предназначено студентам очной формы обучения.
- •Введение
- •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. Сортировка и слияние
При работе со списками очень часто возникает необходимость перестановки элементов списка в определенном порядке. Такая задача называется сортировкой списка. Сортировку следует понимать именно как процесс перегруппировки однотипных элементов структуры данных в некотором определенном порядке. Цель сортировки – облегчить последующие поиск, обновление, исключение, включение элементов в структуру данных. На отсортированных данных легче определить, имеются ли пропущенные элементы, все ли элементы проверены, легче найти общие элементы двух однотипных структур, слить их воедино. Сортировка является важным средством для ускорения работы практически любого алгоритма, в котором требуется частое обращение к определенным элементам структуры данных.
Разработано множество алгоритмов сортировки, однако нет алгоритма, который был бы наилучшим в любом случае. Эффективность алгоритма сортировки может зависеть от ряда факторов, таких, как: число сортируемых элементов; степень отсортированности элементов; характеристики алгоритма (сложность, требования к памяти и т.п.); место размещения элементов (в оперативной памяти или на ВЗУ).
Метод сортировки называется устойчивым, если в процессе сортировки относительное расположение элементов с одинаковыми ключами не изменяется. Устойчивость сортировки желательна, если речь идет об элементах, уже отсортированных по некоторым другим ключам (свойствам), не влияющим на ключ, по которому сейчас осуществляется сортировка.
3.1. Пузырьковая сортировка
Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=< K1, K2,..., Kn>. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B'=< K1', K2',..., Kn' >, в котором для любого 1 i n элемент K'i K'i+1.
При обменной сортировке упорядоченный список В' получается из В систематическим обменом пары рядом стоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют.
Наиболее простой метод систематического обмена соседних элементов с неправильным порядком при просмотре всего списка слева на право определяет пузырьковую сортировку: максимальные элементы как бы всплывают в конце списка. При этом учитывается, что если при просмотре встретилась перестановка, то битовой переменной IS присваивается значение ’1’ B, иначе IS присваивается значение ’0’ B.
Пример:
B=<20, -5, 10, 8, 7>, исходный список;
B1=<-5, 10, 8, 7, 20>, IS=’1’ B;
B2=<-5, 8, 7, 10, 20>, IS=’1’ B
B2=<-5, 7, 8, 10, 20>, IS=’1’ B;
B3=<-5, 7, 8, 10, 20>, IS=’0’ B.
В последующих примерах будем считать, что сортируется одномерный массив (либо его часть от индекса n до индекса m) в порядке возрастания элементов.
Нижеприведенная функция bubble сортирует входной массив методом пузырьковой сортировки.
/* сортировка пузырьковым методом */
float *bubble(float *a, intm, intn)
{
char is=1;
int i;
float c;
while(is)
{
is=0;
for (i=m+1; i<=n; i++)
if (a[i] < a[i-1])
{
c=a[i];
a[i]=a[i-1];
a[i-1]=c;
is=1;
}
}
return(a);
}
Пузырьковая сортировка выполняется при количестве действий O((n-m)*(n-m)) и не требует дополнительной памяти.