Студопедия

Главная страница Случайная страница

Разделы сайта

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






  • Как продвинуть сайт на первые места?
    Вы создали или только планируете создать свой сайт, но не знаете, как продвигать? Продвижение сайта – это не просто процесс, а целый комплекс мероприятий, направленных на увеличение его посещаемости и повышение его позиций в поисковых системах.
    Ускорение продвижения
    Если вам трудно попасть на первые места в поиске самостоятельно, попробуйте технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Если ни один запрос у вас не продвинется в Топ10 за месяц, то в SeoHammer за бустер вернут деньги.
    Начать продвижение сайта
  • Методические указания. Одно из важнейших семейств методов сортировки основано на использовании следующей идеи: предполагается






    Одно из важнейших семейств методов сортировки основано на использовании следующей идеи: предполагается, что перед рассмотрением записи aj предыдущие записи a1, …, aj-1 уже упорядочены, и aj вставляется в соответствующее место. На основе этой схемы возможны несколько вариаций. В лабораторной работе изучается разновидность, которая называется методом простых вставок.

    Алгоритм сортировки методом простых вставок заключается в следующем. Пусть и записи a1, …, aj-1 уже размещены так, что . Будем сравнивать по очереди Кj c Кj-1, Кj-2, … до тех пор, пока не обнаружим, что запись aj следует вставить между ai и ai+1; тогда подвинем записи ai+1, …, aj+1 на одно место вправо и поместим новую запись в позицию i+1.

    Удобно совмещать операции сравнения и перемещения, перемежая их друг с другом. Поскольку запись aj как бы “проникает на положенный ей уровень”, этот способ называют “просеиванием” или “погружением”.

    Приведем пример сортировки массива из 5 чисел:

    Исходный массив 5 2 4 1 3

    Первое сравнение 5: 2

    2 5: 4

    2 4 5: 1

    1 2 4 5: 3

    Массив упорядочен 1 2 3 4 5

    Знак “: ” означает сравнение. Стрелкой показана пересылка элемента.

    Эффективность алгоритма зависит от числа сравнений и пересылок. Грубую оценку среднего числа сравнений можно произвести очень просто. Действительно, когда обрабатывается j-я запись, ее ключ сравнивается в среднем примерно с j/2 ранее отсортированными ключами; поэтому общее число сравнений приблизительно равно

    (2.5)

    Можно более точно оценить количество сравнений, используя понятие инверсии. Число проверок условий Кi< Kj зависит от числа инверсий в сортируемом множестве. Количество сравнений

    (2.6)

    где aj – число инверсий (число элементов, больших Кj и стоящих слева от него).

    Так число инверсий aj и аj связано с номером следующим соотношением:

    Пусть независимы, тогда максимальное количество сравнений определяется формулой

    (2.7)

    Минимальное количество сравнений определяется формулой

    (2.8)

    где aj = 0, т.е. массив упорядочен.

    Среднее количество сравнений определяется из предположения, что среднее количество инверсий равно

    (2.9)

    Тогда среднее количество сравнений задается формулой

    (2.10)

    Усовершенствованиями метода простых вставок являются методы: бинарных вставок, двухпутевые вставки, метод Шелла, вставки в список и др. Познакомиться с этими методами и их сравнительными оценками можно по литературе.

    Блок-схема данного метода представлена в Приложении 3.






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.