3.3 Сортировка
Слияние означает объединение двух или более упорядоченных массивов в один упорядоченный массив. Можно, например, слить подмассивы 503 703 765 и 087 512 677 и получить 087 503 512 677 703 765. Простой способ сделать это - сравнить два наименьших элемента, вывести наименьший из них и повторить эту процедуру. Начав с
и т. д. Необходимо решить, что делать в случае, когда исчерпается один из массивов. Весь процесс подробно описан в следующем алгоритме.
Алгоритм М (Двухпутевое слияние). Этот алгоритм осуществляет слияние упорядоченных массивов x1 х2 … хm и y1 у2 … уn в массив z1 z2 … zm+n.
Ml. [Начальная установка.].Установить i l, j l, k l.
М2. [Найти наименьший элемент.] Если xi yj, перейти к шагу М3; в противном случае перейти к шагу М5.
М3. [Вывести xi] Установить zk xi, k k + l, i i + l. Если i m, вернуться к шагу М2.
М4. [Передать yj,...,yn.] Установить (zk, …, zm+n) (yj,..., yn) и завершить выполнение алгоритма.
М5. [Вывести yj.] Установить zk yj, k k + 1, j j + 1. Если j n, вернуться к шагу M2.
М6. [Передать xi,..., хm.] Установить (zk,..., zm+n) (xi,..., xm) и завершить выполнение алгоритма.
Рис. 2. Слияние
Эта простая процедура, по существу, - наилучший из возможных способов слияния на компьютере с обычной архитектурой, когда m n. (Но, если m гораздо меньше n, можно разработать более эффективные алгоритмы сортировки, хотя в общем случае они довольно сложны.) Алгоритм М без существенной потери эффективности можно немного упростить, добавив в конец исходных массивов искусственных "стражей" (ограничивающие элементы xm+1 = ym+1 = ) и остановившись перед выводом .
Общий объем операций, выполняемых алгоритмом М, по существу, пропорционален m + n, откуда понятно, почему считается, что слияние - более простая задача, чем сортировка. Однако задачу сортировки можно свести к слияниям, сливая все более длинные подмассивы до тех пор, пока не будет рассортирован весь массив. Такой подход можно рассматривать как развитие идеи сортировки методом вставок: вставка нового элемента в упорядоченный массив - частный случай слияния при n = 1. Чтобы ускорить процесс вставок, можно рассмотреть вставку нескольких элементов за один раз, группируя несколько операций, а это естественным образом приведет к общей идее сортировки методом слияния. С исторической точки зрения метод слияний - один из самых первых методов сортировки при помощи компьютеров; он был предложен Джоном фон Нейманом.
- Введение
- 1. Назначение системы
- 2. Анализ предметной области
- 3. Алгоритмическая часть
- 3.1 Работа с файлами
- 3.2 Структурированные типы данных
- 3.3 Сортировка
- 3.4 Алгоритм работы программы
- 4. Программная реализация
- 4.1 Назначение программы
- 4.2 Лингвистическое обеспечение
- 4.3 Техническое и программное обеспечение
- 4.4 Описание данных
- 4.5 Проектирование интерфейса
- 4.6 Структура программы
- 4.7 Структура программного комплекса
- 4.8 Инструкция пользователя
- 4.9 Результаты работы программы
- Заключение