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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Методы сортировки данных, слайд №1Методы сортировки данных, слайд №2Методы сортировки данных, слайд №3Методы сортировки данных, слайд №4Методы сортировки данных, слайд №5Методы сортировки данных, слайд №6Методы сортировки данных, слайд №7Методы сортировки данных, слайд №8Методы сортировки данных, слайд №9Методы сортировки данных, слайд №10Методы сортировки данных, слайд №11Методы сортировки данных, слайд №12Методы сортировки данных, слайд №13Методы сортировки данных, слайд №14Методы сортировки данных, слайд №15Методы сортировки данных, слайд №16Методы сортировки данных, слайд №17Методы сортировки данных, слайд №18Методы сортировки данных, слайд №19Методы сортировки данных, слайд №20Методы сортировки данных, слайд №21Методы сортировки данных, слайд №22Методы сортировки данных, слайд №23Методы сортировки данных, слайд №24Методы сортировки данных, слайд №25Методы сортировки данных, слайд №26Методы сортировки данных, слайд №27Методы сортировки данных, слайд №28Методы сортировки данных, слайд №29Методы сортировки данных, слайд №30Методы сортировки данных, слайд №31Методы сортировки данных, слайд №32Методы сортировки данных, слайд №33Методы сортировки данных, слайд №34Методы сортировки данных, слайд №35Методы сортировки данных, слайд №36Методы сортировки данных, слайд №37Методы сортировки данных, слайд №38Методы сортировки данных, слайд №39Методы сортировки данных, слайд №40Методы сортировки данных, слайд №41Методы сортировки данных, слайд №42Методы сортировки данных, слайд №43Методы сортировки данных, слайд №44Методы сортировки данных, слайд №45Методы сортировки данных, слайд №46Методы сортировки данных, слайд №47Методы сортировки данных, слайд №48Методы сортировки данных, слайд №49Методы сортировки данных, слайд №50Методы сортировки данных, слайд №51Методы сортировки данных, слайд №52Методы сортировки данных, слайд №53Методы сортировки данных, слайд №54Методы сортировки данных, слайд №55Методы сортировки данных, слайд №56Методы сортировки данных, слайд №57Методы сортировки данных, слайд №58Методы сортировки данных, слайд №59Методы сортировки данных, слайд №60Методы сортировки данных, слайд №61Методы сортировки данных, слайд №62Методы сортировки данных, слайд №63Методы сортировки данных, слайд №64Методы сортировки данных, слайд №65Методы сортировки данных, слайд №66Методы сортировки данных, слайд №67Методы сортировки данных, слайд №68Методы сортировки данных, слайд №69Методы сортировки данных, слайд №70Методы сортировки данных, слайд №71Методы сортировки данных, слайд №72Методы сортировки данных, слайд №73Методы сортировки данных, слайд №74Методы сортировки данных, слайд №75Методы сортировки данных, слайд №76Методы сортировки данных, слайд №77Методы сортировки данных, слайд №78
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Методы сортировки данных. Доклад-сообщение содержит 78 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Методы сортировки данных, слайд №1
Описание слайда:

Слайд 2


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

Слайд 3


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

Слайд 4


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

Слайд 5


Методы сортировки данных, слайд №5
Описание слайда:

Слайд 6


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

Слайд 7


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

Слайд 8


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

Слайд 9


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

Слайд 10


Начало алгоритма. Начало алгоритма. Шаг 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. Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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 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. Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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 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. Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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 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. Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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 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. Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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 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. Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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 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. Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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 элементов и делается его обмен со вторым элементом и т.д. до обмена двух последних элементов.
Описание слайда:
Суть сортировки: Суть сортировки: Выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива. Затем находится элемент с наименьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и т.д. до обмена двух последних элементов.

Слайд 19


Методы сортировки данных, слайд №19
Описание слайда:

Слайд 20


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

Слайд 21


Начало алгоритма. Начало алгоритма. Шаг 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. Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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 выполнять: Шаг 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. Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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 выполнять: Шаг 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. Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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


Методы сортировки данных, слайд №26
Описание слайда:

Слайд 27


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

Слайд 28


Начало алгоритма. Начало алгоритма. Шаг 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. Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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 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. Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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 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. Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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


Методы сортировки данных, слайд №33
Описание слайда:

Слайд 34


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

Слайд 35


Методы сортировки данных, слайд №35
Описание слайда:

Слайд 36


Методы сортировки данных, слайд №36
Описание слайда:

Слайд 37


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

Слайд 38


Начало алгоритма. Начало алгоритма. Шаг 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 Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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 выполнять Шаг 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 Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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


Методы сортировки данных, слайд №40
Описание слайда:

Слайд 41


Методы сортировки данных, слайд №41
Описание слайда:

Слайд 42


Методы сортировки данных, слайд №42
Описание слайда:

Слайд 43


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

Слайд 44


Методы сортировки данных, слайд №44
Описание слайда:

Слайд 45


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

Слайд 46


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

Слайд 47


Методы сортировки данных, слайд №47
Описание слайда:

Слайд 48


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

Слайд 49


Начало алгоритма. Начало алгоритма. Шаг 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). Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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+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). Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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+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). Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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+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). Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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+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). Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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+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). Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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+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). Конец алгоритма.
Описание слайда:
Начало алгоритма. Начало алгоритма. Шаг 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 + ...+ 1 = (N2-N)/2 Общее количество операций n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n ) = Theta(n2) Число обменов < числа сравнений = время сортировки растет квадратично относительно количества элементов
Описание слайда:
Оценка алгоритма сортировки выбором Общее количество сравнений 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 сравнение. Для массива 8 7 6 5 4 3 2 1 потребуется (N2-N)/2 сравнение. Общее количество операций Theta(n2)
Описание слайда:
Оценка алгоритма сортировки вставкой Для массива 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


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

Слайд 75


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

Слайд 76


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

Слайд 77


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

Слайд 78


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию