Большие списки - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Большие списки. Доклад-сообщение содержит 24 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Большие списки Очень большие списки можно разбить на подсписки и выбрать один подсписок, в котором содержатся интересующие нас элементы.

Слайд 2

Описание слайда:

Находим в массиве наибольший элемент и помещаем его в буфер Находим в массиве наибольший элемент и помещаем его в буфер Сдвигаем правую часть массива на одну ячейку влево Наибольший элемент из буфера перемещаем в конец массива

Слайд 3

Описание слайда:

Находим в массиве второй по величине элемент и помещаем его в буфер Находим в массиве второй по величине элемент и помещаем его в буфер Сдвигаем правую часть массива на одну ячейку влево (кроме последнего элемента) Второй по величине элемент из буфера перемещаем в конец массива на освободившееся место

Слайд 4

Описание слайда:

Далее процесс повторяется до расположения к-го по величине элемента на нужном месте

Слайд 5

Описание слайда:

В массиве задаем опорный элемент “P1” В массиве задаем опорный элемент “P1” Просматриваем массив слева направо, располагая элементы меньшие P1 слева от него, а большие элементы - справа от него Исключаем из рассмотрения левую часть массива

Слайд 6

Описание слайда:

В оставшейся части массива задаем опорный элемент “P2” В оставшейся части массива задаем опорный элемент “P2” Просматриваем массив слева направо, располагая элементы меньшие P2 слева от него, а большие элементы - справа от него Исключаем из рассмотрения правую часть массива

Слайд 7

Описание слайда:

Продолжаем этот процесс. Возможны два варианта завершения: На очередной итерации опорный элемент Pi располагается на К-ой позиции. Процесс сокращения интервала идет до логического конца – остается подинтервал из двух элементов, один из которых располагается на К-ой позиции.

Слайд 8

Описание слайда:

Алгоритмы сортировки Есть последовательность , ... и функция сравнения, которая на любых двух элементах последовательности принимает одно из трех значений: меньше, больше или равно. Задача сортировки состоит в перестановке членов последовательности таким образом, чтобы выполнялось условие: для всех i от 0 до n.

Слайд 9

Описание слайда:

Возможна ситуация, когда элементы состоят из нескольких полей: Возможна ситуация, когда элементы состоят из нескольких полей: Если значение функции сравнения зависит только от поля x , то x называют ключом, по которому производится сортировка. На практике, в качестве x часто выступает число, а поле y хранит какие-либо данные, никак не влияющие на работу алгоритма.

Слайд 10

Описание слайда:

Критерии эффективности работы алгоритмов Время сортировки - основной параметр, характеризующий быстродействие алгоритма. Память - ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.

Слайд 11

Описание слайда:

Устойчивость - устойчивая сортировка не меняет взаимного расположения равных элементов. Устойчивость - устойчивая сортировка не меняет взаимного расположения равных элементов. Расположение дополнительных полей "a", "b", "c" осталось прежним Взаимное расположение равных элементов с ключом 1 и дополнительными полями "a", "b", "c" изменилось

Слайд 12

Описание слайда:

Естественность поведения - эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведет себя естественно, если учитывает эту характеристику входной последовательности.

Слайд 13

Описание слайда:

Сравнение времени сортировок

Слайд 14

Описание слайда:

Быстрая сортировка Метод основан на подходе "разделяй-и-властвуй". Общая схема такова: из массива выбирается некоторый опорный элемент a[i], запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо, теперь массив состоит из двух подмножеств, причем левое меньше (либо равно) правого, для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.

Слайд 15

Описание слайда:

Разделение массива Разделение массива На входе массив a[0]...a[N] и опорный элемент p, по которому будет производиться разделение. Введем два указателя: i и j. В начале алгоритма они указывают, соответственно, на левый и правый конец последовательности. Будем двигать указатель i с шагом в 1 элемент по направлению к концу массива, пока не будет найден элемент a[i] >= p. Затем аналогичным образом начнем двигать указатель j от конца массива к началу, пока не будет найден a[j]

Слайд 16

Описание слайда:

Исходный массив Исходный массив Первый обмен Второй обмен

Слайд 17

Описание слайда:

Третий обмен Третий обмен Четвертый обмен Конечный результат

Слайд 18

Описание слайда:

Конечный результат Конечный результат Разделённые массивы Для разделённых массивов процедура повторяется

Слайд 19

Описание слайда:

Общее быстродействие метода - хорошее. Общее быстродействие метода - хорошее. Метод неустойчив. Поведение довольно естественно, если учесть, что при частичной упорядоченности повышаются шансы разделения массива на более равные части. Сортировка использует дополнительную память, так как данные о рекурсивных подвызовах каждый раз запоминать.

Слайд 20

Описание слайда:

Сортировка слиянием Сортировка слиянием также построена на принципе "разделяй-и-властвуй", однако реализует его несколько по-другому, нежели быстрая сортировка. Вместо разделения по опорному элементу массив просто делится пополам.

Слайд 21

Описание слайда:

Рекурсивный алгоритм обходит получившееся дерево слияния в прямом порядке. Каждый уровень представляет собой проход сортировки слияния - операцию, полностью переписывающую массив. Деление происходит до массива из единственного элемента. Такой массив можно считать упорядоченным. Один из способов состоит в слиянии двух упорядоченных последовательностей при помощи вспомогательного буфера, равного по размеру общему количеству имеющихся в них элементов. Элементы последовательностей будут перемещаться в этот буфер по одному за шаг.

Слайд 22

Описание слайда:

Исходный массив Исходный массив Первый проход – пары Второй проход – четвёрки

Слайд 23

Описание слайда:

Третий проход – восьмёрки Третий проход – восьмёрки Процесс слияния в буфер

Слайд 24

Описание слайда:

Сортировку слиянием используют для упорядочения массивов, лишь если требуется устойчивость метода (которой нет у быстрой сортировки). Сортировка слиянием является одним из наиболее эффективных методов для списков, когда есть лишь последовательный доступ к элементам. Несмотря на хорошее общее быстродействие и учитывая отсутствие "худшего случая", у сортировки слиянием есть и серьезный минус: она требует дополнительную память.

Теги Большие списки

Похожие презентации