Поразрядная сортировка - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

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

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

Слайд 1

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

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

Слайд 2

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

Рассматриваемый алгоритм имеет следующие особенности. Рассматриваемый алгоритм имеет следующие особенности. не использует сравнений сортируемых элементов. ключ, по которому происходит сортировка, необходимо разделить на части, разряды ключа. Например, слово можно разделить по буквам, число - по цифрам... До сортировки необходимо знать два параметра: k и m, где k - количество разрядов в самом длинном ключе m - разрядность данных: количество возможных значений разряда ключа При сортировки чисел m = 10 (0.1 . . 9) , k = наибольшему количеству цифр в числах ) Эти параметры нельзя изменять в процессе работы алгоритма.

Слайд 3

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

Слайд 4

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

Слайд 5

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

Сортировка вставками Рассмотрим действия на i-м шаге алгоритма. Последовательность к этому моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n]. На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте(вставка завершена) либо они меняются местами и процесс повторяется.

Слайд 6

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

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

Слайд 7

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

В процессе вставки "просеиваем" элемент a[i] к началу массива, останавливаясь в случае, когда 1. Hайден элемент, меньший a[i], 2. Достигнуто начало последовательности. Дополнительная память не используется. Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро. Метод устойчив.

Слайд 8

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

Сортировка Шелла Сортировка Шелла является модификацией алгоритма сортировки простыми вставками. Исходный массив Объединение парами Сортировка внутри пар вставками

Слайд 9

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

Объединение «четвёрками» Объединение «четвёрками»

Слайд 10

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

Объединение «восьмерками» Объединение «восьмерками» Сортировка внутри «восьмерок» вставками Объединение заключительное

Слайд 11

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

Сортировка вставками заключительная

Слайд 12

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

Сортировка выбором Отсортированная последовательность создается путем присоединения к ней одного элемента за другим в правильном порядке. Готовая последовательность строится, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от первого и заканчивая (n-1)-м. На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i].

Слайд 13

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

Шаг-1 (Исходная последовательность ) Шаг-1 (Исходная последовательность ) Нахождение минимального a[m1] элемента из последовательности a[1] ÷ a[n]. Меняем местами a[1] и a[m1].

Слайд 14

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

Шаг-2 Шаг-2 Нахождение минимального a[m2] элемента из последовательности a[2] ÷ a[n]. Меняем местами a[2] и a[m2].

Слайд 15

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

Шаг-3 Шаг-3 Нахождение минимального a[m3] элемента из последовательности a[3] ÷ a[n]. Меняем местами a[3] и a[m3].

Слайд 16

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

Шаг-4 Шаг-4 Нахождение минимального a[m4] элемента из последовательности a[4] ÷ a[n]. Меняем местами a[4] и a[m4]. (в данном случае элемент не смещается)

Слайд 17

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

Вне зависимости от номера текущего шага i, последовательность a[1]...a[i] является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево. Вне зависимости от номера текущего шага i, последовательность a[1]...a[i] является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево. Для нахождения наименьшего элемента из n рассматриваемых алгоритм совершает n сравнений. С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций: n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n ) Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки растет квадратично относительно количества элементов.

Слайд 18

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

Алгоритм не использует дополнительной памяти: все операции происходят "на месте". Алгоритм не использует дополнительной памяти: все операции происходят "на месте". Метод неустойчив. Если входная последовательность почти упорядочена, то сравнений будет столько же, значит алгоритм ведет себя неестественно.

Слайд 19

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

Сортировка пузырьком Расположим массив сверху вниз, от нулевого элемента - к последнему. Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

Слайд 20

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

Нулевой проход Нулевой проход Нет обмена 2 6 2 7 2 9 2 4

Слайд 21

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

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

Слайд 22

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

Номер прохода i=0 i=1 i=2 i=3 i=4 i=5

Слайд 23

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

Дополнительная памятьне требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.

Слайд 24

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

Шейкер-сортировка Улучшение алгоритма можно получить из следующего наблюдения. Легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Чтобы избежать подобного эффекта, можно менять направление следующих один за другим проходов. Получившийся алгоритм иногда называют "шейкер-сортировкой".