1178139
столько раз учителя, ученики и родители
посетили сайт «Инфоурок»
за прошедшие 24 часа
+Добавить материал
и получить бесплатное
свидетельство о публикации
в СМИ №ФС77-60625 от 20.01.2015
Дистанционные курсы профессиональной переподготовки и повышения квалификации для педагогов

Дистанционные курсы для педагогов - курсы профессиональной переподготовки от 5.520 руб.;
- курсы повышения квалификации от 1.200 руб.
Престижные документы для аттестации

ВЫБРАТЬ КУРС СО СКИДКОЙ ДО 70%

ВНИМАНИЕ: Скидка действует ТОЛЬКО сейчас!

(Лицензия на осуществление образовательной деятельности № 5201 выдана ООО "Инфоурок")

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

Презентация по теме ««Алгоритмы сортировки»» для дисциплины ОП.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) в...
СРАВНИТЕЛЬНАЯ ТАБЛИЦА СОРТИРОВОК Сортировка	Худший случай	Средний случай	Лучш...

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

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)

Общая информация

Номер материала: ДВ-234854

Вам будут интересны эти курсы:

Курс повышения квалификации «Информационные технологии в деятельности учителя физики»
Курс повышения квалификации «Методика преподавания информатики в начальных классах»
Курс повышения квалификации «Современные информационные технологии и их использование в работе преподавателей. Системы автоматизированного проектирования одежды и организация технологического процесса»
Курс повышения квалификации «Основы создания интерактивного урока: от презентации до видеоурока»
Курс повышения квалификации «Внедрение системы компьютерной математики в процесс обучения математике в старших классах в рамках реализации ФГОС»
Курс повышения квалификации «Организация работы по формированию медиаграмотности и повышению уровня информационных компетенций всех участников образовательного процесса»
Курс повышения квалификации «Облачные технологии в образовании»
Курс «Фирменный стиль» (Corel Draw, Photoshop)
Курс «Оператор персонального компьютера»
Курс «1С: Предприятие 7.7»
Курс «3D Studio MAX»
Курс «WEB-ВЕРСТКА (HTML, CSS)»
Курс повышения квалификации «Сетевые и дистанционные (электронные) формы обучения в условиях реализации ФГОС по ТОП-50»
Курс повышения квалификации «Применение MS Word, Excel в финансовых расчетах»
Курс повышения квалификации «Современные языки программирования интегрированной оболочки Microsoft Visual Studio C# NET., C++. NET, VB.NET. с использованием структурного и объектно-ориентированного методов разработки корпоративных систем»

Благодарность за вклад в развитие крупнейшей онлайн-библиотеки методических разработок для учителей

Опубликуйте минимум 3 материала, чтобы БЕСПЛАТНО получить и скачать данную благодарность

Сертификат о создании сайта

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

Грамота за использование ИКТ в работе педагога

Опубликуйте минимум 10 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

Свидетельство о представлении обобщённого педагогического опыта на Всероссийском уровне

Опубликуйте минимум 15 материалов, чтобы БЕСПЛАТНО получить и скачать данное cвидетельство

Грамота за высокий профессионализм, проявленный в процессе создания и развития собственного учительского сайта в рамках проекта "Инфоурок"

Опубликуйте минимум 20 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

Грамота за активное участие в работе над повышением качества образования совместно с проектом "Инфоурок"

Опубликуйте минимум 25 материалов, чтобы БЕСПЛАТНО получить и скачать данную грамоту

Почётная грамота за научно-просветительскую и образовательную деятельность в рамках проекта "Инфоурок"

Опубликуйте минимум 40 материалов, чтобы БЕСПЛАТНО получить и скачать данную почётную грамоту

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