![]() Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Методические указания. Одно из важнейших семейств методов сортировки основано на использовании следующей идеи: предполагается
Одно из важнейших семейств методов сортировки основано на использовании следующей идеи: предполагается, что перед рассмотрением записи aj предыдущие записи a1, …, aj-1 уже упорядочены, и aj вставляется в соответствующее место. На основе этой схемы возможны несколько вариаций. В лабораторной работе изучается разновидность, которая называется методом простых вставок. Алгоритм сортировки методом простых вставок заключается в следующем. Пусть Удобно совмещать операции сравнения и перемещения, перемежая их друг с другом. Поскольку запись aj как бы “проникает на положенный ей уровень”, этот способ называют “просеиванием” или “погружением”. Приведем пример сортировки массива из 5 чисел: Исходный массив 5 2 4 1 3
Массив упорядочен 1 2 3 4 5 Знак “: ” означает сравнение. Стрелкой показана пересылка элемента. Эффективность алгоритма зависит от числа сравнений и пересылок. Грубую оценку среднего числа сравнений можно произвести очень просто. Действительно, когда обрабатывается j-я запись, ее ключ сравнивается в среднем примерно с j/2 ранее отсортированными ключами; поэтому общее число сравнений приблизительно равно
Можно более точно оценить количество сравнений, используя понятие инверсии. Число проверок условий Кi< Kj зависит от числа инверсий в сортируемом множестве. Количество сравнений
где aj – число инверсий (число элементов, больших Кj и стоящих слева от него). Так число инверсий aj и аj связано с номером следующим соотношением: Пусть Забиваем Сайты В ТОП КУВАЛДОЙ - Уникальные возможности от SeoHammer
Каждая ссылка анализируется по трем пакетам оценки: SEO, Трафик и SMM.
SeoHammer делает продвижение сайта прозрачным и простым занятием.
Ссылки, вечные ссылки, статьи, упоминания, пресс-релизы - используйте по максимуму потенциал SeoHammer для продвижения вашего сайта.
Что умеет делать SeoHammer
— Продвижение в один клик, интеллектуальный подбор запросов, покупка самых лучших ссылок с высокой степенью качества у лучших бирж ссылок. — Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта. — Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы). — SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание. SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Зарегистрироваться и Начать продвижение
Минимальное количество сравнений определяется формулой
где aj = 0, т.е. массив упорядочен. Среднее количество сравнений определяется из предположения, что среднее количество инверсий равно
Тогда среднее количество сравнений задается формулой
Усовершенствованиями метода простых вставок являются методы: бинарных вставок, двухпутевые вставки, метод Шелла, вставки в список и др. Познакомиться с этими методами и их сравнительными оценками можно по литературе. Блок-схема данного метода представлена в Приложении 3.
|