Презентация Цифровая сортировка DigitalSort онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Цифровая сортировка DigitalSort абсолютно бесплатно. Урок-презентация на эту тему содержит всего 14 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:14 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:113.70 kB
- Просмотров:71
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Пример. Дана последовательность S из 8 чисел:
Пример. Дана последовательность S из 8 чисел:
S : 31 03’ 20 02 03” 33 30 21
Q0 : 20 30
Q1 : 31 21
Q2 : 02
Q3 : 03’ 03” 33
S : 20 30 31 21 02 03’ 03” 33
Q0 : 02 03’ 03”
Q1 :
Q2 : 20 21
Q3 : 30 31 33
S : 02 03’ 03” 20 21 30 31 33
№2 слайд
Содержание слайда: Цифровая сортировка (DigitalSort)
Вначале числа из списка S распределяются по очередям, причём номер очереди определяется последней цифрой каждого числа.
Затем полученные очереди соединяются в список, для которого все действия повторяются, но распределение по очередям производится в соответствии со следующей цифрой и т. д.
В примере использованы 4 очереди, т.к. каждая цифра принимает значение от 0 до 3, т.е. числа представлены в четверичной системе счисления.
Для сортировки десятичных чисел понадобится 10 очередей.
№3 слайд
Содержание слайда: В общем случае:
В общем случае:
Дана последовательность из S чисел,
представленных в m-ичной системе счисления.
Каждое число состоит из L цифр d1 d2 … dL
(первая цифра – старшая, L-тая – младшая).
Тогда для каждой цифры d выполняется неравенство:
0 ≤ d ≤ m –1
Поэтому для проведения сортировки потребуется
m очередей Q0 , Q1 , …, Qm-1.
№4 слайд
Содержание слайда: Цифровая сортировка (DigitalSort)
Пример.
Необходимо сортировать последовательность целых чисел типа longint (32 бита).
Сколько потребуется очередей?
Можно рассматривать каждый байт числа как цифру, принимающую значения от 0 до 255.
Таким образом, целое число: d1 d2 d3 d4 , L = 4 цифры, m = 256 очередей.
№5 слайд
Содержание слайда: Цифровая сортировка (DigitalSort)
Укрупненная схема алгоритма
DO ( j := L , L–1 , …, 1 )
< Инициализация очередей Q >
< Расстановка элементов из списка S в очереди Q
по j –той цифре >
< Соединение очередей Q в список S >
OD
Элемент списка: Next
Пусть в элементе списка поле data имеет тип tdata.
m = 256, отдельной цифрой ключа является байт
№6 слайд
Содержание слайда: Цифровая сортировка (DigitalSort)
Рассмотрим основные операции:
1) Определение j-той цифры ключа сортировки
Задача: выделение произвольного байта в поле Data
Решение: необходимо в структуре элемента списка определить массив байтов, который накладывается в памяти компьютера на компоненту Data.
Удобно использовать описатель union (объединение).
Тогда структура элемента списка:
struct tLE { tLE * Next;
union { tData Data;
byte Digit [ sizeof (tData) ];
}
}
Доступ к каждому k-тому байту поля Data: Digit[k].
№7 слайд
Содержание слайда: Цифровая сортировка (DigitalSort)
Рассмотрим особенности реализации цифровой сортировки для сложных структур:
Пример:
struct tData { char Name [5];
long Phone;
};
sizeof (tData) = ?
№8 слайд
Содержание слайда: sizeof (tData) = 10 байтов
sizeof (tData) = 10 байтов
старш. млад. млад. старш.
name phone
Используем индексацию для удобства выбора байта.
Введем индексный массив KDI ( Key Digit Index ):
byte KDI [ sizeof (tData) ];
Пример: 1) ключ = Name, KDI = (1,2,3,4,5), L=5
2) ключ = Phone, KDI = (10,9,8,7), L=4
3) ключ = Phone +Name, KDI = (10,9,8,7,1,2,3,4,5)
4) ключ = 3 младших байта Phone +
+3 первых буквы Name,
KDI = (9,8,7,1,2,3), L=6
№9 слайд
Содержание слайда: Тогда KDI [j] - номер байта, соответствующего j-той цифре ключа сортировки, j := L, L–1, …,1.
Тогда KDI [j] - номер байта, соответствующего j-той цифре ключа сортировки, j := L, L–1, …,1.
Операция выбора j-той цифры:
d := Digit [ KDI [j] ]
В алгоритме цифровой сортировки операция выполняется в два этапа:
k := KDI [j]
d := Digit [k]
№10 слайд
Содержание слайда: 2) Соединение очередей. Имеется очередь Q
(возможно, пустая) и непустая очередь S.
1) S.tail -> next := Q.head
2) S.tail := Q. tail
Трудоемкость соединения очередей не зависит от количества элементов в очередях.
Если очередь Q пуста, выполнять присоединение нельзя
( условие пустоты очереди Q : Q. tail = & Q. head ).
№11 слайд
Содержание слайда: Алгоритм на псевдокоде
Алгоритм на псевдокоде
DO ( j := L, L-1, … 1 )
DO ( i := 0, 1, … 255 )
Q i . Tail := & Q i . Head
OD
p := S
k := KDI [j]
DO ( p ≠ NIL )
d := p → Digit [k]
Q d .Tail → Next := p
Q d .Tail := p
p := p → Next
OD
№12 слайд
Содержание слайда: Алгоритм на псевдокоде
Алгоритм на псевдокоде
(продолжение)
p := & S
DO ( i := 0, 1, … 255 )
IF ( Q i . Tail ≠ & Q i . Head )
p → Next := Q i . Head
p := Q i . Tail
FI
OD
p → Next := NIL
OD
№13 слайд
Содержание слайда: Трудоемкость метода
Трудоемкость метода
T = O( L( n + m ) )
Замечания:
1) Цифровая сортировка устойчива.
2) Чтобы изменить направление сортировки на обратное, нужно очереди присоединять в обратном порядке.
3) При фиксированных m и L: T = O(n) < O(n logn)
Границы применимости метода:
1) Метод применим, если задача сортировки сводится к задаче упорядочивания чисел, что не всегда возможно.
2) Если длина чисел (L) велика, то метод может проигрывать обычным методам сортировки (например, методу Хоара).
№14 слайд
Содержание слайда:
Скачать все slide презентации Цифровая сортировка DigitalSort одним архивом:
