Презентация на тему: Алгоритмы сортировки. Сортировка Шелла Выполнила: студентка 1-го курса группа

Алгоритмы сортировки. Сортировка Шелла Выполнила: студентка 1-го курса группа
Алгоритмы сортировки. Сортировка Шелла Выполнила: студентка 1-го курса группа
Алгоритмы сортировки. Сортировка Шелла Выполнила: студентка 1-го курса группа
Алгоритмы сортировки. Сортировка Шелла Выполнила: студентка 1-го курса группа
Алгоритмы сортировки. Сортировка Шелла Выполнила: студентка 1-го курса группа
Алгоритмы сортировки. Сортировка Шелла Выполнила: студентка 1-го курса группа
Алгоритмы сортировки. Сортировка Шелла Выполнила: студентка 1-го курса группа
Алгоритмы сортировки. Сортировка Шелла Выполнила: студентка 1-го курса группа
Алгоритмы сортировки. Сортировка Шелла Выполнила: студентка 1-го курса группа
Алгоритмы сортировки. Сортировка Шелла Выполнила: студентка 1-го курса группа
Алгоритмы сортировки. Сортировка Шелла Выполнила: студентка 1-го курса группа
Алгоритмы сортировки. Сортировка Шелла Выполнила: студентка 1-го курса группа
Алгоритмы сортировки. Сортировка Шелла Выполнила: студентка 1-го курса группа
Алгоритмы сортировки. Сортировка Шелла Выполнила: студентка 1-го курса группа
1/14
Средняя оценка: 4.2/5 (всего оценок: 65)
Код скопирован в буфер обмена
Скачать (350 Кб)
1

Первый слайд презентации

Алгоритмы сортировки. Сортировка Шелла Выполнила: студентка 1-го курса группа МП-12-2 Баландина Анна Федеральное агентство по образованию РФ Национальный исследовательский технологический университет «МИСиС» 1

Изображение слайда
2

Слайд 2

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. Сортировка  - это процесс упорядочивания информации по определенному признаку. Цель сортировки - облегчение последующего поиска элементов. Это почти универсальный вид обработки информации, с которым мы встречаемся в жизни повсеместно. 2

Изображение слайда
3

Слайд 3

Параметры, по которым производиться оценка алгоритмов. Время сортировки – основной параметр, характеризующий быстродействие алгоритма. Память – один из параметров, который характеризуется тем, что ряд алгоритмов сортировки требуют выделения дополнительной памяти под временное хранение данных. Устойчивость – это параметр, который отвечает за то, что сортировка не меняет взаимного расположения равных элементов. Естественность поведения – параметр, который указывает на эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведет себя естественно, если учитывает эту характеристику входной последовательности и работает лучше. 3

Изображение слайда
4

Слайд 4

4 Виды алгоритмов: Алгоритмы устойчивой сортировки Сортировка выбором ( Selection sort ) Сортировка пузырьком (англ. Bubble sort ) Сортировка перемешиванием ( Cocktail sort, bidirectional bubble sort ) Гномья сортировка Сортировка слиянием ( Merge sort ) Сортировка с помощью двоичного дерева (англ. Tree sort ) Алгоритм сортировки Timsort (англ. Timsort ) Алгоритмы неустойчивой сортировки Сортировка выбором ( Selection sort) Сортировка Шелла ( Shell sort) Сортировка расчёской ( Comb sort) Пирамидальная сортировка (Сортировка кучи, Heapsort ) Плавная сортировка ( Smoothsort )

Изображение слайда
5

Слайд 5

1. Функция сравнения пары элементов сортируемого массива 2. Процедура перестановки, меняющая местами пару элементов 3. Сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены. #define less( x,y ) (x < y) функция сравнения элементов # define swap( x,y ) { int t=x; x=y; y=t;} процедура перестановки элементов 5 Составные части алгоритмов.

Изображение слайда
6

Слайд 6

6 Сортировка Шелла. Основная идея алгоритма заключается в том, чтобы вначале устранить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места. Эффективность сортировки Шелла сильно зависит от следующих факторов: 1. начального шага 2. от дальнейшей последовательности шагов.

Изображение слайда
7

Слайд 7

7

Изображение слайда
8

Слайд 8

8 Сортировка Шелла является довольно интересной модификацией алгоритма сортировки простыми вставками. Рассмотрим следующий алгоритм сортировки массива a[0].. a[15]. 1. Вначале сортируем простыми вставками каждые 8 групп из 2-х элементов (a[0], a[8[), (a[1], a[9]),..., (a[7], a[15]).

Изображение слайда
9

Слайд 9

9 2. Потом сортируем каждую из четырех групп по 4 элемента (a[0], a[4], a[8], a[12]),..., (a[3], a[7], a[11], a[15]). В нулевой группе будут элементы 4, 12, 13, 18, в первой - 3, 5, 8, 9 и т.п. 3. Далее сортируем 2 группы по 8 элементов, начиная с (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14]).

Изображение слайда
10

Слайд 10

10 4. В конце сортируем вставками все 16 элементов. Очевидно, лишь последняя сортировка необходима, чтобы расположить все элементы по своим местам. Так зачем нужны остальные ?

Изображение слайда
11

Слайд 11

11 Основной характеристикой сортировки Шелла является приращение - расстояние между сортируемыми элементами, в зависимости от прохода. В конце приращение всегда равно единице. Использованный в примере набор..., 8, 4, 2, 1 - неплохой выбор, особенно, когда количество элементов - степень двойки. Однако гораздо лучший вариант предложил Р.Седжвик.

Изображение слайда
12

Слайд 12

12 Сортировка Шелла оказывается лишь красивым теоретическим методом, потому что на практике использовать его нецелесообразно: он сложен в реализации, но не дает такой скорости, какую дают сравнимые с ним по сложности программной реализации методы.

Изображение слайда
13

Слайд 13

13 http://democoder.ru/article/9 http://ru.wikipedia.org/ http://z0mbie.daemonlab.org/sort.html Используемые сайты:

Изображение слайда
14

Последний слайд презентации: Алгоритмы сортировки. Сортировка Шелла Выполнила: студентка 1-го курса группа

14

Изображение слайда