Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Сортировка методом слияния.(двухпутевое слияние)

Int data; | Динамическое распределение памяти | Free(newPtr); | Очереди | Алгоритм как абстрактная машина | Сопоставление алгоритмических моделей | Формы рекурсивных процедур. | Пример рекурс алгоритмаЗадача о Ханойских башнях. | Program Hanoi_Towers; | Анализ сложных алгоритмов |


Читайте также:
  1. Oslash; Выберете команду Сортировка и группировка из пункта меню Вид.
  2. А. Выявления антигенов вируса гриппа в мокроте методом ИФА.
  3. Алгоритм расчета переходного процесса частотным методом
  4. Алгоритм расчета переходных процессов методом интеграла Дюамеля
  5. Алгоритм решения транспортной задачи методом потенциалов.
  6. Анализ структуры ВВП: определение, факторы, структурная динамика ВВП, рассчитанного методом конечного использования
  7. АНАЛИЗ ТЕХНИЧЕСКОГО ОБРАЗЦА СОЛИ МОРА МЕТОДОМ ПЕРМАНГАНАТОМЕТРИИ.

Слияние означает объединение двух или более упорядоченных массивов в один упорядоченный массив.

Самый простой способ сделать это – сравнить два наименьших элемента, вывести наименьшее из них и повторить процедуру

Слияние означает объединение двух или более упорядоченных массивов в один упорядоченный массив.

Самый простой способ сделать это – сравнить два наименьших элемента, вывести наименьшее из них и повторить процедуру

структура

М1. Установить i←1, j←1, k←1.

М2. Если xi ≤ yj,, перейти к М3, в противном случае к М5.

М3. Установить zk ← xi, k ← k+1, i←i+1. Если i ≤ m, вернуться к М2.

М4. Установить (zk, …, z(m+n)) ← (yj, …, yn) и завершить выполнение.

М5. Установить zk ← yj,,, k ← k+1, j←j+1. Если j≤n, вернуться к шагу М2.

М6. Установить (zk, …, z(m+n))←(xi, …,xm) и завершить алгоритм.

А) Алгоритмы быстрой сортировки.
(Сортировка Хоара или сортировка с помощью разделения)

Этот алгоритм является примером использования рекурсии. Он был разработан в 1962 году, профессором Оксфордского университета Хоаром. (Основан на алгоритме сортировки обменами).

Принцип метода: для достижения наилучшей эффективности сначала лучше производить перестановки на большие расстояния. Выберем наугад какой-либо элемент (х) и будем просматривать слева массив до тех пор, пока не обнаружим элемент Ri> x, затем будем просматривать массив справа, пока не встретим Rj<x. Теперь поменяем их местами и продолжим процесс просмотра и обмена, пока оба просмотра не встретятся в середине массива. В результате массив окажется разбитым на левую часть с ключами ≤ x, и правую – с ключами ≥ x.

Таким образом, относительно значения x массив получается отсортированным, но левая и правая части ещё не упорядочены.


Дата добавления: 2015-07-16; просмотров: 99 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Сортировка посредством выбора| Сортировка с помощью включений с уменьшающимися расстояниями (Сортировка Шелла)

mybiblioteka.su - 2015-2024 год. (0.005 сек.)