Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015

Опубликуйте свой материал в официальном Печатном сборнике методических разработок проекта «Инфоурок»

(с присвоением ISBN)

Выберите любой материал на Вашем учительском сайте или загрузите новый

Оформите заявку на публикацию в сборник(займет не более 3 минут)

+

Получите свой экземпляр сборника и свидетельство о публикации в нем

Инфоурок / Информатика / Презентации / Презентация по теме ««Алгоритмы сортировки»» для дисциплины ОП.08 Теория алгоритмов
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 24 мая.

Подать заявку на курс
  • Информатика

Презентация по теме ««Алгоритмы сортировки»» для дисциплины ОП.08 Теория алгоритмов

библиотека
материалов
ТЕМА УРОКА: «АЛГОРИТМЫ СОРТИРОВКИ» Дисциплина ОП.08 Теория алгоритмов Препод...
В чем состоит задача сортировки? Зачем нужно изучать сортировку? Сортировка п...
1. В ЧЕМ СОСТОИТ ЗАДАЧА СОРТИРОВКИ? Сортировка – упорядочЕние заданного списк...
1. В ЧЕМ СОСТОИТ ЗАДАЧА СОРТИРОВКИ? Устойчивый алгоритм – не меняет относител...
1. В ЧЕМ СОСТОИТ ЗАДАЧА СОРТИРОВКИ? Как правило, сортируются только ключи, ко...
2. ЗАЧЕМ НУЖНО ИЗУЧАТЬ СОРТИРОВКУ? Во многих приложениях нужно сортировать да...
СОРТИРОВКА ПУЗЫРЬКОМ (BUBBLE SORT)
3. СОРТИРОВКА ПУЗЫРЬКОМ Суть алгоритма: многократный проход по списку и сравн...
3. СОРТИРОВКА ПУЗЫРЬКОМ Алгоритм Bubble sort (A[0…n-1]) for i=0 to n-2 do for...
СОРТИРОВКА ВЫБОРОМ (SELECTION SORT)
4. СОРТИРОВКА ВЫБОРОМ Суть алгоритма: проходим по списку, ищем наименьший эле...
4. СОРТИРОВКА ВЫБОРОМ Алгоритм Selection sort (A[0…n-1]) for i=0 to n-2 do mi...
СОРТИРОВКА ВСТАВКАМИ (INSERTION SORT)
5. СОРТИРОВКА ВСТАВКАМИ Суть алгоритма: делим список на отсортированную часть...
5. СОРТИРОВКА ВСТАВКАМИ Алгоритм Insertion sort (A[0…n-1]) for i=1 to n-1 do...
5. СОРТИРОВКА ВСТАВКАМИ Время работы: O(n2) в худшем случае, O(n) в лучшем сл...
СОРТИРОВКА СЛИЯНИЕМ (MERGE SORT)
6. СОРТИРОВКА СЛИЯНИЕМ Суть алгоритма: список рекурсивно делится пополам, пос...
6. СОРТИРОВКА СЛИЯНИЕМ Алгоритм Mergesort (A[0…n-1]) if n>1 Копировать A[0…n/...
6. СОРТИРОВКА СЛИЯНИЕМ Алгоритм Merge (B[0…p-1], C[0…q-1], A[0…p+q-1) i=0; j=...
6. СОРТИРОВКА СЛИЯНИЕМ
6. СОРТИРОВКА СЛИЯНИЕМ Время работы: O(n log n) в худшем случае, O(n log n) в...
СРАВНИТЕЛЬНАЯ ТАБЛИЦА СОРТИРОВОК Сортировка	Худший случай	Средний случай	Лучш...
23 1

Описание презентации по отдельным слайдам:

№ слайда 1 ТЕМА УРОКА: «АЛГОРИТМЫ СОРТИРОВКИ» Дисциплина ОП.08 Теория алгоритмов Препод
Описание слайда:

ТЕМА УРОКА: «АЛГОРИТМЫ СОРТИРОВКИ» Дисциплина ОП.08 Теория алгоритмов Преподаватель Скряго О.С. Смоленск 2014

№ слайда 2 В чем состоит задача сортировки? Зачем нужно изучать сортировку? Сортировка п
Описание слайда:

В чем состоит задача сортировки? Зачем нужно изучать сортировку? Сортировка пузырьком Сортировка выбором Сортировка вставками Сортировка слиянием

№ слайда 3 1. В ЧЕМ СОСТОИТ ЗАДАЧА СОРТИРОВКИ? Сортировка – упорядочЕние заданного списк
Описание слайда:

1. В ЧЕМ СОСТОИТ ЗАДАЧА СОРТИРОВКИ? Сортировка – упорядочЕние заданного списка элементов. Вход: последовательность, состоящая из n чисел (a1, a2, …, an). Выход: перестановка (изменение порядка) (a1’, a2’,…, an’) входной последовательности таким образом, что a1’ ≤ a2’ ≤ … ≤ an’. Входная последовательность представляется в виде n-элементного массива.

№ слайда 4 1. В ЧЕМ СОСТОИТ ЗАДАЧА СОРТИРОВКИ? Устойчивый алгоритм – не меняет относител
Описание слайда:

1. В ЧЕМ СОСТОИТ ЗАДАЧА СОРТИРОВКИ? Устойчивый алгоритм – не меняет относительное расположение одинаковых элементов в массиве. Если номера двух одинаковых элементов i < j, то в отсортированном списке i’ < j’ Обменный (in-place) алгоритм – для его работы не требуется дополнительная память, которая зависит от размера массива.

№ слайда 5 1. В ЧЕМ СОСТОИТ ЗАДАЧА СОРТИРОВКИ? Как правило, сортируются только ключи, ко
Описание слайда:

1. В ЧЕМ СОСТОИТ ЗАДАЧА СОРТИРОВКИ? Как правило, сортируются только ключи, которые существуют в записях (строчка в таблице, список, объект) Базовая операция – сравнение двух элементов: ai ≤ aj (кроме некоторых специальных алгоритмов) Время работы: Ω(n log n) Рассматривается сортировка по возрастанию

№ слайда 6 2. ЗАЧЕМ НУЖНО ИЗУЧАТЬ СОРТИРОВКУ? Во многих приложениях нужно сортировать да
Описание слайда:

2. ЗАЧЕМ НУЖНО ИЗУЧАТЬ СОРТИРОВКУ? Во многих приложениях нужно сортировать данные Выдача информации (отчеты, списки) Сортировка для бинарного поиска Геометрические алгоритмы (вывод графики, поиск выпуклой оболочки) Многие алгоритмы требуют предварительную сортировку данных Алгоритмы сортировки – прекрасный способ изучения алгоритмов (большое количество алгоритмов, много техник).

№ слайда 7 СОРТИРОВКА ПУЗЫРЬКОМ (BUBBLE SORT)
Описание слайда:

СОРТИРОВКА ПУЗЫРЬКОМ (BUBBLE SORT)

№ слайда 8 3. СОРТИРОВКА ПУЗЫРЬКОМ Суть алгоритма: многократный проход по списку и сравн
Описание слайда:

3. СОРТИРОВКА ПУЗЫРЬКОМ Суть алгоритма: многократный проход по списку и сравнение двух соседних элементов. Если ai > ai+1, то элементы меняются местами. На первом проходе в конец списка перемещается («всплывает») самый большой элемент, на втором проходе – всплывает второй по величине элемент и т.д.

№ слайда 9 3. СОРТИРОВКА ПУЗЫРЬКОМ Алгоритм Bubble sort (A[0…n-1]) for i=0 to n-2 do for
Описание слайда:

3. СОРТИРОВКА ПУЗЫРЬКОМ Алгоритм Bubble sort (A[0…n-1]) for i=0 to n-2 do for j=0 to n-2-i do if A[j+1] < A[j] обмен A[j] и A[j+1] Время работы: O(n2) Разные случаи: нет Модификация: если при проходе нет обмена – список отсортирован

№ слайда 10 СОРТИРОВКА ВЫБОРОМ (SELECTION SORT)
Описание слайда:

СОРТИРОВКА ВЫБОРОМ (SELECTION SORT)

№ слайда 11 4. СОРТИРОВКА ВЫБОРОМ Суть алгоритма: проходим по списку, ищем наименьший эле
Описание слайда:

4. СОРТИРОВКА ВЫБОРОМ Суть алгоритма: проходим по списку, ищем наименьший элемент и меняем местами с первым элементом. Далее находим второй наименьший элемент и меняем его местами со вторым элементом и т.д. Есть другой вариант: ищем наибольший элемент и меняем местами с последним элементом.

№ слайда 12 4. СОРТИРОВКА ВЫБОРОМ Алгоритм Selection sort (A[0…n-1]) for i=0 to n-2 do mi
Описание слайда:

4. СОРТИРОВКА ВЫБОРОМ Алгоритм Selection sort (A[0…n-1]) for i=0 to n-2 do min=i for j=i+1 to n-1 do if A[j] < A[min] min=j обмен A[j] и A[min] Время работы: O(n2) Разные случаи: нет

№ слайда 13 СОРТИРОВКА ВСТАВКАМИ (INSERTION SORT)
Описание слайда:

СОРТИРОВКА ВСТАВКАМИ (INSERTION SORT)

№ слайда 14 5. СОРТИРОВКА ВСТАВКАМИ Суть алгоритма: делим список на отсортированную часть
Описание слайда:

5. СОРТИРОВКА ВСТАВКАМИ Суть алгоритма: делим список на отсортированную часть и неотсортированную. Изначально в отсортированную часть попадает первое значение списка. Далее сравниваем следующее значение со значениями в отсортированном списке и ставим его в нужном порядке, после чего отсортированная часть увеличивается на 1. Потом берем следующее значение и т.д.

№ слайда 15 5. СОРТИРОВКА ВСТАВКАМИ Алгоритм Insertion sort (A[0…n-1]) for i=1 to n-1 do
Описание слайда:

5. СОРТИРОВКА ВСТАВКАМИ Алгоритм Insertion sort (A[0…n-1]) for i=1 to n-1 do v=A[i] j=i-1 while j≥0 AND A[j]>v do A[j+1]=A[j] j=j-1 A[j+1]=v

№ слайда 16 5. СОРТИРОВКА ВСТАВКАМИ Время работы: O(n2) в худшем случае, O(n) в лучшем сл
Описание слайда:

5. СОРТИРОВКА ВСТАВКАМИ Время работы: O(n2) в худшем случае, O(n) в лучшем случае. Разные случаи: да, зависит от характера входных данных. Чем ближе входные данные к отсортированным – тем меньше сравнений.

№ слайда 17 СОРТИРОВКА СЛИЯНИЕМ (MERGE SORT)
Описание слайда:

СОРТИРОВКА СЛИЯНИЕМ (MERGE SORT)

№ слайда 18 6. СОРТИРОВКА СЛИЯНИЕМ Суть алгоритма: список рекурсивно делится пополам, пос
Описание слайда:

6. СОРТИРОВКА СЛИЯНИЕМ Суть алгоритма: список рекурсивно делится пополам, после чего каждая половина рекурсивно сортируется, после чего две половины сливаются в один отсортированный массив. Список рекурсивно делится пополам, пока все подмассивы не будут содержать 1 или 0 элементов. Если сортируемый список нечетный – один из подмассивов будет пустым.

№ слайда 19 6. СОРТИРОВКА СЛИЯНИЕМ Алгоритм Mergesort (A[0…n-1]) if n&gt;1 Копировать A[0…n/
Описание слайда:

6. СОРТИРОВКА СЛИЯНИЕМ Алгоритм Mergesort (A[0…n-1]) if n>1 Копировать A[0…n/2-1] в B[0…n/2-1] Копировать A[n/2…n-1] в С[0…n/2-1] Mergesort (B[0…n/2-1]) Mergesort (С[0…n/2-1]) Merge (B,C,A)

№ слайда 20 6. СОРТИРОВКА СЛИЯНИЕМ Алгоритм Merge (B[0…p-1], C[0…q-1], A[0…p+q-1) i=0; j=
Описание слайда:

6. СОРТИРОВКА СЛИЯНИЕМ Алгоритм Merge (B[0…p-1], C[0…q-1], A[0…p+q-1) i=0; j=0; k=0 While i<p AND j<q do if B[i]≤C[j] A[k]=B[i]; i=i+1 else A[k]=C[j]; j=j+1 k=k+1 if i=p Копировать C[j…q-1] в A[k…p+q-1] Else Копировать B[i…p-1] в A[k…p+q-1]

№ слайда 21 6. СОРТИРОВКА СЛИЯНИЕМ
Описание слайда:

6. СОРТИРОВКА СЛИЯНИЕМ

№ слайда 22 6. СОРТИРОВКА СЛИЯНИЕМ Время работы: O(n log n) в худшем случае, O(n log n) в
Описание слайда:

6. СОРТИРОВКА СЛИЯНИЕМ Время работы: O(n log n) в худшем случае, O(n log n) в лучшем случае. Разные случаи: да, зависит от характера входных данных, но не значительно Требует n дополнительной памяти для подмассивов

№ слайда 23 СРАВНИТЕЛЬНАЯ ТАБЛИЦА СОРТИРОВОК Сортировка	Худший случай	Средний случай	Лучш
Описание слайда:

СРАВНИТЕЛЬНАЯ ТАБЛИЦА СОРТИРОВОК Сортировка Худший случай Средний случай Лучший случай Пузырьковая O(n2) O(n2) O(n2) Пузырьковая (м) O(n2) O(n2) O(n) Вставками O(n2) O(n2) O(n) Выбором O(n2) O(n2) O(n2) Слиянием O(n log n) O(n log n) O(n log n)

Автор
Дата добавления 06.12.2015
Раздел Информатика
Подраздел Презентации
Просмотров504
Номер материала ДВ-234854
Получить свидетельство о публикации

Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Похожие материалы

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