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

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

Цифровая сортировка DigitalSort, слайд №1

Цифровая сортировка DigitalSort, слайд №2

Цифровая сортировка DigitalSort, слайд №3

Цифровая сортировка DigitalSort, слайд №4

Цифровая сортировка DigitalSort, слайд №5

Цифровая сортировка DigitalSort, слайд №6

Цифровая сортировка DigitalSort, слайд №7

Цифровая сортировка DigitalSort, слайд №8

Цифровая сортировка DigitalSort, слайд №9

Цифровая сортировка DigitalSort, слайд №10

Цифровая сортировка DigitalSort, слайд №11

Цифровая сортировка DigitalSort, слайд №12

Цифровая сортировка DigitalSort, слайд №13

Цифровая сортировка DigitalSort, слайд №14

Содержание ▲

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

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

Слайд 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) велика, то метод может проигрывать обычным методам сортировки (например, методу Хоара).