PPt4Web Хостинг презентаций

Главная / Информатика / Методы сортировки данных
X Код для использования на сайте:

Скопируйте этот код и вставьте его на свой сайт

X

Чтобы скачать данную презентацию, порекомендуйте, пожалуйста, её своим друзьям в любой соц. сети.

После чего скачивание начнётся автоматически!

Кнопки:

Презентация на тему: Методы сортировки данных


Скачать эту презентацию

Презентация на тему: Методы сортировки данных


Скачать эту презентацию



№ слайда 1 Методы сортировки данных дисциплина «Основы алгоритмизации и программирования 2
Описание слайда:

Методы сортировки данных дисциплина «Основы алгоритмизации и программирования 2 курс Соколова Наталья Валентиновна, преподаватель спец. Дисциплин Sokolova_natali@list.ru

№ слайда 2 Сортировка объектов – расположение объектов по возрастанию или убыванию согласно
Описание слайда:

Сортировка объектов – расположение объектов по возрастанию или убыванию согласно определенному линейному отношению порядка Сортировка объектов – расположение объектов по возрастанию или убыванию согласно определенному линейному отношению порядка

№ слайда 3 Сортировка объектов:Сортировка объектов:ВнутренняяВнешняя
Описание слайда:

Сортировка объектов:Сортировка объектов:ВнутренняяВнешняя

№ слайда 4 Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной
Описание слайда:

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

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

№ слайда 6 Алгоритм сортировки вставкой
Описание слайда:

Алгоритм сортировки вставкой

№ слайда 7 Суть сортировки: Суть сортировки: Упорядочиваются два элемента массиваВставка тр
Описание слайда:

Суть сортировки: Суть сортировки: Упорядочиваются два элемента массиваВставка третьего элемента в соответствующее место по отношению к первым двум элементам. Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены.

№ слайда 8 Сортировка вставкой
Описание слайда:

Сортировка вставкой

№ слайда 9 Постановка задачиПусть нужно отсортировать массив А по возрастанию, в котором N
Описание слайда:

Постановка задачиПусть нужно отсортировать массив А по возрастанию, в котором N элементов методом вставкиВспомогательные переменныеj – номер первого элемента остатка.i – номер перемещаемого элемента.f – условие выхода из цикла (если f=1, то выход) Val – промежуточное значение, используемое для перемещения элементов массив

№ слайда 10 Начало алгоритма.Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j<=N выполнять:Шаг 2.
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j<=N выполнять:Шаг 2.1 i:=j; f:=0,Шаг 2.2 Пока i>=2 и f=0 выполнять:Шаг 2.2.1 Если A[i-1]>A[i] то Val:=A[i-1]; A[i-1]:=A[i]; A[i]:=Val, иначе f:=1,Шаг 2.2.2 i:=i-1,Шаг 2.3 j:=j+1.Конец алгоритма.

№ слайда 11 Начало алгоритма.Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j<=N выполнять:Шаг 2.
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j<=N выполнять:Шаг 2.1 i:=j; f:=0,Шаг 2.2 Пока i>=2 и f=0 выполнять:Шаг 2.2.1 Если A[i-1]>A[i] то Val:=A[i-1]; A[i-1]:=A[i]; A[i]:=Val, иначе f:=1,Шаг 2.2.2 i:=i-1,Шаг 2.3 j:=j+1.Конец алгоритма.

№ слайда 12 Начало алгоритма.Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j<=N выполнять:Шаг 2.
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j<=N выполнять:Шаг 2.1 i:=j; f:=0,Шаг 2.2 Пока i>=2 и f=0 выполнять:Шаг 2.2.1 Если A[i-1]>A[i] то Val:=A[i-1]; A[i-1]:=A[i]; A[i]:=Val, иначе f:=1,Шаг 2.2.2 i:=i-1,Шаг 2.3 j:=j+1.Конец алгоритма.

№ слайда 13 Начало алгоритма.Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j<=N выполнять:Шаг 2.
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j<=N выполнять:Шаг 2.1 i:=j; f:=0,Шаг 2.2 Пока i>=2 и f=0 выполнять:Шаг 2.2.1 Если A[i-1]>A[i] то Val:=A[i-1]; A[i-1]:=A[i]; A[i]:=Val, иначе f:=1,Шаг 2.2.2 i:=i-1,Шаг 2.3 j:=j+1.Конец алгоритма.

№ слайда 14 Начало алгоритма.Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j<=N выполнять:Шаг 2.
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j<=N выполнять:Шаг 2.1 i:=j; f:=0,Шаг 2.2 Пока i>=2 и f=0 выполнять:Шаг 2.2.1 Если A[i-1]>A[i] то Val:=A[i-1]; A[i-1]:=A[i]; A[i]:=Val, иначе f:=1,Шаг 2.2.2 i:=i-1,Шаг 2.3 j:=j+1.Конец алгоритма.

№ слайда 15 Начало алгоритма.Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j<=N выполнять:Шаг 2.
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j<=N выполнять:Шаг 2.1 i:=j; f:=0,Шаг 2.2 Пока i>=2 и f=0 выполнять:Шаг 2.2.1 Если A[i-1]>A[i] то Val:=A[i-1]; A[i-1]:=A[i]; A[i]:=Val, иначе f:=1,Шаг 2.2.2 i:=i-1,Шаг 2.3 j:=j+1.Конец алгоритма.

№ слайда 16 Начало алгоритма.Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j<=N выполнять:Шаг 2.
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 j:=2,Шаг 2 Пока j<=N выполнять:Шаг 2.1 i:=j; f:=0,Шаг 2.2 Пока i>=2 и f=0 выполнять:Шаг 2.2.1 Если A[i-1]>A[i] то Val:=A[i-1]; A[i-1]:=A[i]; A[i]:=Val, иначе f:=1,Шаг 2.2.2 i:=i-1,Шаг 2.3 j:=j+1.Конец алгоритма.

№ слайда 17 Алгоритм сортировки выбором
Описание слайда:

Алгоритм сортировки выбором

№ слайда 18 Суть сортировки:Суть сортировки:Выбирается элемент с наименьшим значением и дела
Описание слайда:

Суть сортировки:Суть сортировки:Выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива. Затем находится элемент с наименьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и т.д. до обмена двух последних элементов.

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

№ слайда 20 Постановка задачиПусть нужно отсортировать массив А по возрастанию, в котором N
Описание слайда:

Постановка задачиПусть нужно отсортировать массив А по возрастанию, в котором N элементов методом выбора. Вспомогательные переменныеj – номер первого элемента остатка.i – номер перемещаемого элемента.min – минимальное число в массиве.Imin – номер минимального числа в массиве

№ слайда 21 Начало алгоритма.Начало алгоритма.Шаг 1 j:=1,Шаг 2 Пока j<=N-1 выполнять: Шаг
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 j:=1,Шаг 2 Пока j<=N-1 выполнять: Шаг 2.1 min:=a[j], Imin:=j, i:=j+1 Шаг 2.2 Пока i<=N выполнять: Шаг 2.2.1 Если A[i]<min, то min:=a[i], Imin:=i Шаг 2.2.2 i:=i+1, Шаг 2.3 A[Imin]:=A[j], A[j]:=min Шаг 2.4 j:=j+1. Конец алгоритма.

№ слайда 22 Начало алгоритма.Начало алгоритма.Шаг 1 j:=1,Шаг 2 Пока j<=N-1 выполнять: Шаг
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 j:=1,Шаг 2 Пока j<=N-1 выполнять: Шаг 2.1 min:=a[j], Imin:=j, i:=j+1 Шаг 2.2 Пока i<=N выполнять: Шаг 2.2.1 Если A[i]<min, то min:=a[i], Imin:=i Шаг 2.2.2 i:=i+1, Шаг 2.3 A[Imin]:=A[j], A[j]:=min Шаг 2.4 j:=j+1. Конец алгоритма.

№ слайда 23 Начало алгоритма.Начало алгоритма.Шаг 1 j:=1,Шаг 2 Пока j<=N-1 выполнять: Шаг
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 j:=1,Шаг 2 Пока j<=N-1 выполнять: Шаг 2.1 min:=a[j], Imin:=j, i:=j+1 Шаг 2.2 Пока i<=N выполнять: Шаг 2.2.1 Если A[i]<min, то min:=a[i], Imin:=i Шаг 2.2.2 i:=i+1, Шаг 2.3 A[Imin]:=A[j], A[j]:=min Шаг 2.4 j:=j+1. Конец алгоритма.

№ слайда 24 Алгоритм сортировки обменом («пузырьковая»)
Описание слайда:

Алгоритм сортировки обменом («пузырьковая»)

№ слайда 25 Суть сортировки:Суть сортировки:Последовательно просматривается массив и сравнив
Описание слайда:

Суть сортировки:Суть сортировки:Последовательно просматривается массив и сравнивается каждая пара элементов между собой. При этом "неправильное" расположение элементов устраняется путем их перестановки. Процесс просмотра и сравнения элементов повторяется до просмотра всего массива.

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

№ слайда 27 Постановка задачиПусть нужно отсортировать массив А по возрастанию, в котором N
Описание слайда:

Постановка задачиПусть нужно отсортировать массив А по возрастанию, в котором N элементов методом обменаВспомогательные переменныеj – номер первого элемента остатка.i – номер перемещаемого элемента.Val – промежуточное значение, используемое для перемещения элементов массива

№ слайда 28 Начало алгоритма.Начало алгоритма.Шаг 1 j:=N,Шаг 2 Пока j>=2 выполнять:Шаг 2.
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 j:=N,Шаг 2 Пока j>=2 выполнять:Шаг 2.1 i:=1; ,Шаг 2.2 Пока i<=j-1выполнять:Шаг 2.2.1 Если A[i]>A[i+1] то Val:=A[i]; A[i]:=A[i+1]; A[i+1]:=Val, Шаг 2.2.2 i=i+1,Шаг 2.3 j:=j-1.Конец алгоритма.

№ слайда 29 Начало алгоритма.Начало алгоритма.Шаг 1 j:=N,Шаг 2 Пока j>=2 выполнять:Шаг 2.
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 j:=N,Шаг 2 Пока j>=2 выполнять:Шаг 2.1 i:=1; ,Шаг 2.2 Пока i<=j-1выполнять:Шаг 2.2.1 Если A[i]>A[i+1] то Val:=A[i]; A[i]:=A[i+1]; A[i+1]:=Val, Шаг 2.2.2 i=i+1,Шаг 2.3 j:=j-1.Конец алгоритма.

№ слайда 30 Начало алгоритма.Начало алгоритма.Шаг 1 j:=N,Шаг 2 Пока j>=2 выполнять:Шаг 2.
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 j:=N,Шаг 2 Пока j>=2 выполнять:Шаг 2.1 i:=1; ,Шаг 2.2 Пока i<=j-1выполнять:Шаг 2.2.1 Если A[i]>A[i+1] то Val:=A[i]; A[i]:=A[i+1]; A[i+1]:=Val, Шаг 2.2.2 i=i+1,Шаг 2.3 j:=j-1.Конец алгоритма.

№ слайда 31 Алгоритм сортировки Шелла
Описание слайда:

Алгоритм сортировки Шелла

№ слайда 32 Классифицируется как «слияние вставкой»;Классифицируется как «слияние вставкой»;
Описание слайда:

Классифицируется как «слияние вставкой»;Классифицируется как «слияние вставкой»;Называется «сортировкой с убывающим шагом»Общий метод, который использует сортировку вставкой, применяет принцип уменьшения расстояния между сравниваемыми элементами

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

№ слайда 34 Суть сортировки:Суть сортировки:Сначала сортируются все элементы, отстоящие друг
Описание слайда:

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

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

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

№ слайда 37 Постановка задачиПусть нужно отсортировать массив А по возрастанию, в котором N
Описание слайда:

Постановка задачиПусть нужно отсортировать массив А по возрастанию, в котором N элементов методом ШеллаВспомогательные переменныеj – номер первого элемента остатка.i – номер перемещаемого элемента.M- оптимальный шагP– промежуточное значение, используемое для перемещения элементов массива

№ слайда 38 Начало алгоритма.Начало алгоритма.Шаг 1. M=целая часть N/2Шаг 2. Пока M<>0
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1. M=целая часть N/2Шаг 2. Пока M<>0 выполнять Шаг 2.1. i:=M+1 Шаг 2.2. Пока i<=N выполнять Шаг 2.2.1. P=A[i] Шаг 2.2.2. j=i-M Шаг 2.2.3. Пока j>0 и P<A[j] выполнять Шаг 2.2.3.1 A[j+M]=A[j] Шаг 2.2.3.2 j=j-M Шаг 2.2.4. A[j+M]=P Шаг 2.2.5. i=i+1 Шаг 2.3. M=целая часть M/2Конец алгоритма.

№ слайда 39 Начало алгоритма.Начало алгоритма.Шаг 1. M=целая часть N/2Шаг 2. Пока M<>0
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1. M=целая часть N/2Шаг 2. Пока M<>0 выполнять Шаг 2.1. i:=M+1 Шаг 2.2. Пока i<=N выполнять Шаг 2.2.1. P=A[i] Шаг 2.2.2. j=i-M Шаг 2.2.3. Пока j>0 и P<A[j] выполнять Шаг 2.2.3.1 A[j+M]=A[j] Шаг 2.2.3.2 j=j-M Шаг 2.2.4. A[j]=P Шаг 2.2.5. i=i+1 Шаг 2.3. M=целая часть M/2Конец алгоритма.

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

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

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

№ слайда 43 Алгоритм быстрой сортировки
Описание слайда:

Алгоритм быстрой сортировки

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

№ слайда 45 Суть сортировки:Суть сортировки:Выбирается некоторое значение (x)- барьерный эле
Описание слайда:

Суть сортировки:Суть сортировки:Выбирается некоторое значение (x)- барьерный элемент, который определяется округлением до целого деления количества сортируемых элементов на 2;Просматриваем массив, двигаясь слева направо, пока не найдется элемент, больший x Затем просматриваем его справа налево, пока не найдется элемент, меньший x

№ слайда 46 Суть сортировки:Меняем найденные элементы местами. В случае, если не найден наиб
Описание слайда:

Суть сортировки:Меняем найденные элементы местами. В случае, если не найден наибольший или наименьший элементы, местами меняется средний элемент с найденным наибольшим или наименьшим элементом;Дойдя до середины имеем 2 части массива;Процесс продолжается для каждой части, пока массив не будет отсортирован

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

№ слайда 48 Постановка задачиПусть нужно отсортировать массив А по возрастанию, в котором n
Описание слайда:

Постановка задачиПусть нужно отсортировать массив А по возрастанию, в котором n элементов быстрым методом Вспомогательные переменные:t –конечный элемент массиваm - начальный элемент массиваx – элемент относительно которого перемещаются все остальные элементы.w – промежуточное значение, используемое для перемещения элементов массива

№ слайда 49 Начало алгоритма.Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i<=j выполнять:Шаг 3.1 Если A[i]<x то i:=i+1, иначе Если A[j]>x то j:=j-1 иначе w:=A[i]; A[i]:=A[j]; A[j]:=w i:=i+1, j:=j-1Шаг 4 Если m<j то Алгоритм (A, m, j); Шаг 5 Если i<t то Алгоритм (A, i, t).Конец алгоритма.

№ слайда 50 Начало алгоритма.Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i<=j выполнять:Шаг 3.1 Если A[i]<x то i:=i+1, иначе Если A[j]>x то j:=j-1 иначе w:=A[i]; A[i]:=A[j]; A[j]:=w i:=i+1, j:=j-1Шаг 4 Если m<j то Алгоритм (A, m, j); Шаг 5 Если i<t то Алгоритм (A, i, t).Конец алгоритма.

№ слайда 51 Начало алгоритма.Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i<=j выполнять:Шаг 3.1 Если A[i]<x то i:=i+1, иначе Если A[j]>x то j:=j-1 иначе w:=A[i]; A[i]:=A[j]; A[j]:=w i:=i+1, j:=j-1Шаг 4 Если m<j то Алгоритм (A, m, j); Шаг 5 Если i<t то Алгоритм (A, i, t).Конец алгоритма.

№ слайда 52 Начало алгоритма.Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i<=j выполнять:Шаг 3.1 Если A[i]<x то i:=i+1, иначе Если A[j]>x то j:=j-1 иначе w:=A[i]; A[i]:=A[j]; A[j]:=w i:=i+1, j:=j-1Шаг 4 Если m<j то Алгоритм (A, m, j); Шаг 5 Если i<t то Алгоритм (A, i, t).Конец алгоритма.

№ слайда 53 Начало алгоритма.Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i<=j выполнять:Шаг 3.1 Если A[i]<x то i:=i+1, иначе Если A[j]>x то j:=j-1 иначе w:=A[i]; A[i]:=A[j]; A[j]:=w i:=i+1, j:=j-1Шаг 4 Если m<j то Алгоритм (A, m, j); Шаг 5 Если i<t то Алгоритм (A, i, t).Конец алгоритма.

№ слайда 54 Начало алгоритма.Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i<=j выполнять:Шаг 3.1 Если A[i]<x то i:=i+1, иначе Если A[j]>x то j:=j-1 иначе w:=A[i]; A[i]:=A[j]; A[j]:=w i:=i+1, j:=j-1Шаг 4 Если m<j то Алгоритм (A, m, j); Шаг 5 Если i<t то Алгоритм (A, i, t).Конец алгоритма.

№ слайда 55 Начало алгоритма.Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+
Описание слайда:

Начало алгоритма.Начало алгоритма.Шаг 1 i=m j=tШаг 2 x=A[округление до целого(m+t)/2]Шаг 3 Пока i<=j выполнять:Шаг 3.1 Если A[i]<x то i:=i+1, иначе Если A[j]>x то j:=j-1 иначе w:=A[i]; A[i]:=A[j]; A[j]:=w i:=i+1, j:=j-1Шаг 4 Если m<j то Алгоритм (A, m, j); Шаг 5 Если i<t то Алгоритм (A, i, t).Конец алгоритма.

№ слайда 56 Основывается:Основывается:количестве необходимых сравнений количестве пересылок
Описание слайда:

Основывается:Основывается:количестве необходимых сравнений количестве пересылок

№ слайда 57 Параметры оценки алгоритмов Время сортировки - основной параметр, характеризующи
Описание слайда:

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

№ слайда 58 Параметры оценки алгоритмовУстойчивость – отсортированный массив не меняет поряд
Описание слайда:

Параметры оценки алгоритмовУстойчивость – отсортированный массив не меняет порядок элементов с одинаковыми значениями.

№ слайда 59 Параметры оценки алгоритмов Естественность поведения - эффективность метода при
Описание слайда:

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

№ слайда 60 Оценка алгоритма сортировки выбором Общее количество сравнений C =N-l + N-2 + ..
Описание слайда:

Оценка алгоритма сортировки выбором Общее количество сравнений C =N-l + N-2 + ...+ 1 = (N2-N)/2Общее количество операций n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n ) = Theta(n2)Число обменов < числа сравнений = время сортировки растет квадратично относительно количества элементов

№ слайда 61 Устойчив ли этот метод?
Описание слайда:

Устойчив ли этот метод?

№ слайда 62 Если входная последовательность почти упорядочена, то сравнений будет столько же
Описание слайда:

Если входная последовательность почти упорядочена, то сравнений будет столько жеЕсли входная последовательность почти упорядочена, то сравнений будет столько же

№ слайда 63 Оценка алгоритма сортировки вставкойДля массива 1 2 3 4 5 6 7 8 потребуется N-1
Описание слайда:

Оценка алгоритма сортировки вставкойДля массива 1 2 3 4 5 6 7 8 потребуется N-1 сравнение.Для массива 8 7 6 5 4 3 2 1 потребуется (N2-N)/2 сравнение.Общее количество операций Theta(n2)

№ слайда 64 Устойчив ли этот метод?
Описание слайда:

Устойчив ли этот метод?

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

№ слайда 66 Не эффективный метод, так как включение элемента связано со сдвигом всех предшес
Описание слайда:

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

№ слайда 67 Оценка алгоритма сортировки обменом
Описание слайда:

Оценка алгоритма сортировки обменом

№ слайда 68 Ответьте на следующие вопросы:Устойчив ли этот метод?Естественное ли поведение э
Описание слайда:

Ответьте на следующие вопросы:Устойчив ли этот метод?Естественное ли поведение этого алгоритма?

№ слайда 69 Очень медленен и малоэффективен. Очень медленен и малоэффективен. На практике, д
Описание слайда:

Очень медленен и малоэффективен. Очень медленен и малоэффективен. На практике, даже с улучшениями, работает, слишком медленно, поэтому почти не применяется.

№ слайда 70 Сравнение методов простой сортировки
Описание слайда:

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

№ слайда 71 Выбор метода сортировкиПри сортировке маленьких массивов (менее 100 элементов) л
Описание слайда:

Выбор метода сортировкиПри сортировке маленьких массивов (менее 100 элементов) лучше использовать метод «Всплывающего пузырька»;Если известно, что список уже почти отсортирован, то подойдет любой метод;

№ слайда 72 Оценка алгоритма ШеллаВремя выполнения пропорционально n1.2, т. к. при каждом пр
Описание слайда:

Оценка алгоритма ШеллаВремя выполнения пропорционально n1.2, т. к. при каждом проходе используется небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных

№ слайда 73 Оценка алгоритма быстрой сортировкиЕсли размер массива равен числу, являющемуся
Описание слайда:

Оценка алгоритма быстрой сортировкиЕсли размер массива равен числу, являющемуся степенью двойки (N=2g), и при каждом разделении элемент X находится точно в середине массива, тогда при первом просмотре выполняется N сравнений и массив разделится на две части размерами N/2. Для каждой из этих частей N/2 сравнений и т. д. Следовательно C=N+2*(N/2)+4*(N/4)+...+N*(N/N). Если N не является степенью двойки, то оценка будет иметь тот же порядок

№ слайда 74 Общее количество операций Theta(n). Общее количество операций Theta(n). Количест
Описание слайда:

Общее количество операций Theta(n). Общее количество операций Theta(n). Количество шагов деления (глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n)Если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности, тогда быстродействие O(n2)

№ слайда 75 Метод неустойчив. Метод неустойчив. Поведение довольно естественно, если учесть,
Описание слайда:

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

№ слайда 76 Итоги:Итоги:Предпочтительным является метод прямого включения;Сортировка методом
Описание слайда:

Итоги:Итоги:Предпочтительным является метод прямого включения;Сортировка методом простого обмена является наихудшей;Быстрая сортировка превосходит все остальные методы сортировки;

№ слайда 77 Контрольные вопросыЧто такое «сортировка»?В чем заключается метод сортировки отб
Описание слайда:

Контрольные вопросыЧто такое «сортировка»?В чем заключается метод сортировки отбором?В чем заключается метод сортировки вставками?В чем заключается метод пузырьковой сортировки?В чем заключается метод быстрой сортировки?В чем заключается метод сортировки Шелла?

№ слайда 78 Контрольные вопросыКакой алгоритм сортировки считается самым простым?Какой алгор
Описание слайда:

Контрольные вопросыКакой алгоритм сортировки считается самым простым?Какой алгоритм сортировки считается самым эффективным?Сколько существует групп алгоритмов сортировки?По каким признакам характеризуются алгоритмы сортировки?Что нужно учитывать при выборе алгоритма сортировки?

Скачать эту презентацию


Презентации по предмету
Презентации из категории
Лучшее на fresher.ru