Презентация Методы сортировки данных онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Методы сортировки данных абсолютно бесплатно. Урок-презентация на эту тему содержит всего 78 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Методы сортировки данных
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:78 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:465.09 kB
- Просмотров:64
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№4 слайд
![Внутренняя сортировка](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img3.jpg)
Содержание слайда: Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке.
Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке.
Данные обычно сортируются на том же месте, без дополнительных затрат
№9 слайд
![Постановка задачи Пусть нужно](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img8.jpg)
Содержание слайда: Постановка задачи
Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом вставки
Вспомогательные переменные
j – номер первого элемента остатка.
i – номер перемещаемого элемента.
f – условие выхода из цикла (если f=1, то выход)
Val – промежуточное значение, используемое для перемещения элементов массив
№18 слайд
![Суть сортировки Суть](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img17.jpg)
Содержание слайда: Суть сортировки:
Суть сортировки:
Выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива.
Затем находится элемент с наименьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и т.д. до обмена двух последних элементов.
№20 слайд
![Постановка задачи Пусть нужно](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img19.jpg)
Содержание слайда: Постановка задачи
Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом выбора.
Вспомогательные переменные
j – номер первого элемента остатка.
i – номер перемещаемого элемента.
min – минимальное число в массиве.
Imin – номер минимального числа в массиве
№21 слайд
![Начало алгоритма. Начало](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img20.jpg)
Содержание слайда: Начало алгоритма.
Начало алгоритма.
Шаг 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 слайд
![Начало алгоритма. Начало](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img21.jpg)
Содержание слайда: Начало алгоритма.
Начало алгоритма.
Шаг 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 слайд
![Начало алгоритма. Начало](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img22.jpg)
Содержание слайда: Начало алгоритма.
Начало алгоритма.
Шаг 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.
Конец алгоритма.
№25 слайд
![Суть сортировки Суть](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img24.jpg)
Содержание слайда: Суть сортировки:
Суть сортировки:
Последовательно просматривается массив и сравнивается каждая пара элементов между собой.
При этом "неправильное" расположение элементов устраняется путем их перестановки.
Процесс просмотра и сравнения элементов повторяется до просмотра всего массива.
№27 слайд
![Постановка задачи Пусть нужно](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img26.jpg)
Содержание слайда: Постановка задачи
Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом обмена
Вспомогательные переменные
j – номер первого элемента остатка.
i – номер перемещаемого элемента.
Val – промежуточное значение, используемое для перемещения элементов массива
№37 слайд
![Постановка задачи Пусть нужно](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img36.jpg)
Содержание слайда: Постановка задачи
Пусть нужно отсортировать массив А по возрастанию, в котором N элементов методом Шелла
Вспомогательные переменные
j – номер первого элемента остатка.
i – номер перемещаемого элемента.
M- оптимальный шаг
P– промежуточное значение, используемое для перемещения элементов массива
№38 слайд
![Начало алгоритма. Начало](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img37.jpg)
Содержание слайда: Начало алгоритма.
Начало алгоритма.
Шаг 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 слайд
![Начало алгоритма. Начало](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img38.jpg)
Содержание слайда: Начало алгоритма.
Начало алгоритма.
Шаг 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
Конец алгоритма.
№45 слайд
![Суть сортировки Суть](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img44.jpg)
Содержание слайда: Суть сортировки:
Суть сортировки:
Выбирается некоторое значение (x)- барьерный элемент, который определяется округлением до целого деления количества сортируемых элементов на 2;
Просматриваем массив, двигаясь слева направо, пока не найдется элемент, больший x
Затем просматриваем его справа налево, пока не найдется элемент, меньший x
№46 слайд
![Суть сортировки Меняем](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img45.jpg)
Содержание слайда: Суть сортировки:
Меняем найденные элементы местами. В случае, если не найден наибольший или наименьший элементы, местами меняется средний элемент с найденным наибольшим или наименьшим элементом;
Дойдя до середины имеем 2 части массива;
Процесс продолжается для каждой части, пока массив не будет отсортирован
№48 слайд
![Постановка задачи Пусть нужно](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img47.jpg)
Содержание слайда: Постановка задачи
Пусть нужно отсортировать массив А по возрастанию, в котором n элементов быстрым методом
Вспомогательные переменные:
t –конечный элемент массива
m - начальный элемент массива
x – элемент относительно которого перемещаются все остальные элементы.
w – промежуточное значение, используемое для перемещения элементов массива
№49 слайд
![Начало алгоритма. Начало](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img48.jpg)
Содержание слайда: Начало алгоритма.
Начало алгоритма.
Шаг 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 слайд
![Начало алгоритма. Начало](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img49.jpg)
Содержание слайда: Начало алгоритма.
Начало алгоритма.
Шаг 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 слайд
![Начало алгоритма. Начало](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img50.jpg)
Содержание слайда: Начало алгоритма.
Начало алгоритма.
Шаг 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 слайд
![Начало алгоритма. Начало](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img51.jpg)
Содержание слайда: Начало алгоритма.
Начало алгоритма.
Шаг 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 слайд
![Начало алгоритма. Начало](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img52.jpg)
Содержание слайда: Начало алгоритма.
Начало алгоритма.
Шаг 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 слайд
![Начало алгоритма. Начало](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img53.jpg)
Содержание слайда: Начало алгоритма.
Начало алгоритма.
Шаг 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 слайд
![Начало алгоритма. Начало](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img54.jpg)
Содержание слайда: Начало алгоритма.
Начало алгоритма.
Шаг 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).
Конец алгоритма.
№60 слайд
![Оценка алгоритма сортировки](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img59.jpg)
Содержание слайда: Оценка алгоритма сортировки выбором
Общее количество сравнений
C =N-l + N-2 + ...+ 1 = (N2-N)/2
Общее количество операций
n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n ) = Theta(n2)
Число обменов < числа сравнений = время сортировки растет квадратично относительно количества элементов
№66 слайд
![Не эффективный метод, так как](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img65.jpg)
Содержание слайда: Не эффективный метод, так как включение элемента связано со сдвигом всех предшествующих элементов на одну позицию, а эта операция неэкономна
Не эффективный метод, так как включение элемента связано со сдвигом всех предшествующих элементов на одну позицию, а эта операция неэкономна
№73 слайд
![Оценка алгоритма быстрой](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img72.jpg)
Содержание слайда: Оценка алгоритма быстрой сортировки
Если размер массива равен числу, являющемуся степенью двойки (N=2g), и при каждом разделении элемент X находится точно в середине массива, тогда при первом просмотре выполняется N сравнений и массив разделится на две части размерами N/2. Для каждой из этих частей N/2 сравнений и т. д. Следовательно
C=N+2*(N/2)+4*(N/4)+...+N*(N/N).
Если N не является степенью двойки, то оценка будет иметь тот же порядок
№74 слайд
![Общее количество операций](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img73.jpg)
Содержание слайда: Общее количество операций Theta(n).
Общее количество операций Theta(n).
Количество шагов деления (глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n)
Если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности, тогда быстродействие O(n2)
№78 слайд
![Контрольные вопросы Какой](/documents_6/a68b782afa59efe3365d450a41e7f9b9/img77.jpg)
Содержание слайда: Контрольные вопросы
Какой алгоритм сортировки считается самым простым?
Какой алгоритм сортировки считается самым эффективным?
Сколько существует групп алгоритмов сортировки?
По каким признакам характеризуются алгоритмы сортировки?
Что нужно учитывать при выборе алгоритма сортировки?
Скачать все slide презентации Методы сортировки данных одним архивом:
Похожие презентации
-
Методы улучшения алгоритмов сортировок. Лекция 7
-
Метод сортировки пирамидой
-
Методы интеллектуального анализа данных Мартин Браун (Martin C. Brown)
-
Алгоритмы и структуры данных. Сортировка обменом Pump. Тема 5
-
Язык C. Введение. Базовые типы данных. Консоль. Классы и методы
-
Методы интеллектуального анализа данных и некоторые их приложения
-
Методы сортировки массивов. Сортировка методом «Пузырька»
-
Сортировка выбором. Методы сортировки массивов
-
Различные методы сортировки. Занятие 1
-
Методы сортировки