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

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

Сортировка простым слиянием.

Сортировки слиянием.

Метод Хоара.

Сортировка бинарными вставками.

Сортировка двухпутевыми вставками.

Пирамидальная сортировка.

Представление дерева в виде линейного массива. Дерево – это не пирамида. Нумеруем элементы дерева слева направо, порядковые номера в линейной записи одномерного массива. В пирамиде есть такое понятие как дочерний элемент и родительский. Значение рассчитывается по формулам 2i и 2i +1 и т.д. В исходном массиве достигается упорядоченность таким образом, чтобы родитель был больше детей. Оценка метода – о(N*log₂N).

Идея заключается в следующем: берется итоговый массив удвоенной длины. Первый элемент исходного массива помещается в середину массива, далее берется каждый последующий. Сортирует механизм вставок.

Есть упорядоченный массив. Очередной элемент, который нужно разместить, нужно найти позицию. Позиция N/2. Сравниваем элемент с тем, который расположен в середине левой части массива. Каждый раз берем пополам и т.д. Каждый раз сравниваем с элементом, расположенным в середине. Элемент либо совпадает, либо не совпадает. Если массив реализован в виде списка, то быстрее. Трудоемкость о(log₂N).

Быстрая сортировка Хоара или сортировка с разделением. На каждом этапе массив разбивается на две части и все элементы расположенные левее среднего – меньше среднего.

Есть два упорядоченных массива, из них нужно получить итоговый упорядоченный. N1 и N2. Граничный помещаем. (N1+N2)-1, пропорционально N. линейная зависимость.

Получаем упорядоченные пары. И «сливаем» их.

18.03.10 г.

Поиск è поиск среди упорядоченных данных и среди неупорядоченных данных.

1. Обычный поиск.

2. Быстрый последовательный поиск.

3. Поиск в самоорганизующейся последовательности данных.

Быстрый последовательный поиск.

Отличается тем, что перед началом поиска добавляется один искомый элемент в позицию n+1. В цикле будет выполняться только одна проверка, организуется как цикл с предусловием либо с постусловием. Проверяется условие совпадения ключа. Проверок будет в два раза меньше. Среднее число сравнений n/2.

Поиск в самоорганизующейся последовательности данных.

На примере стопки книг с неподписанными торцами. Ближе всего будет та книга, которая чаще всего используется.

25 14 18 42 15 6 è 14 25 18 42 15 6 è 42 14 25 18 15 6 è 25 42 14 18 15 6 è 42 25 14 18 15 6.

Группа методов сортировки среди упорядоченных данных.

1. Бинарный поиск.

2. Однородный бинарный поиск.

3. Фиббоначиев поиск.

4. Логарифмический поиск.

5. Поиск по дереву.