Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
21 ошибка прогр... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Имитационное мо... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Реклама
Сейчас на сайте
Гостей: 29
На сайте нет зарегистрированных пользователей

Пользователей: 13,361
новичок: uehuat
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Моделирование вычислительного центра на GPSS + Отчет + Блок схема
Файл записей с выводом обратного заголовка на Turbo Pascal
Моделирование работы крупного аэропорта на GPSS + Пояснительная записка

Сортировка данных специального вида
Выше было показано, как следует использовать так называемые универсальные алгоритмы сортировки, пригодные для любого вида данных, подлежащих сравнению. Однако, зачастую информация о множестве значений, которые могут принимать элементы массива, может в корне изменить подход к сортировке. Пусть, например, требуется отсортировать 100000 цифр, вводимых, например, из стандартного потока ввода (это типичная задача для районных или городских олимпиад по информатике). Как уже говорилось в лекции 3, максимальный размер массива даже однобайтовых элементов не может превышать 64 килобайта. Кроме того, время работы любого из универсальных “эффективных” (то есть выполняющих порядка Nlog2N действий) для 100000 элементов скорее всего будет превышать допустимое по условию время решения задачи. Поэтому обратим внимание на то, что элементами массива, подлежащего сортировке, являются не произвольные числа, а цифры, то есть целые числа от 0 до 9. В этом случае алгоритм сортировки фактически заключается в подсчете количества каждой из цифр и записи результата согласно полученным результатам подсчета. Реализовать этот алгоритм можно так:
var d:array[0..9] of longint; {массив для подсчета} a:byte;{переменная для ввода цифр} n,i,j:longint; begin read(n);{n - количество цифр} fillchar(d,sizeof(d),0); for i := 1 to n do
begin
read(a); d[a] := d[a] + 1
end;
for j := 0 to 9 do {печатаем результат} for i := 1 to d[j] do write(j:2) end.


Заметим, что эта программа работает верно и в случае, когда какой либо из цифр во вводимой последовательности нет совсем. Подобный алгоритм называют сортировкой подсчетом или “карманной” сортировкой [1, 5]. Его трудоемкость составляет O(N+m) (а именно, 2N + m операций), где m — количество различных элементов в массиве. Очевидно, что если M<=N и мы можем отвести память для подсчета количества каждого из m возможных значений для элементов массива, то алгоритм окажется линейным относительно N. Если же m<N, то алгоритм может как выигрывать, так и проигрывать по сравнению с универсальными эффективными алгоритмами. Например, для массива из 1000 положительных чисел типа integer сортировка подсчетом выполняется за 32767*2 + 1000 = 66534 операции, а, например, сортировка слиянием, — за 2*1000*[log21000]=20000 операций. Но уже для 10000 таких же чисел сортировка подсчетом выполняется за 75534 операции, а слиянием — за 280000.
В качестве упражнения, иллюстрирующего ту же самую идею, что и сортировка подсчетом, реализуйте программу, определяющую, какая буква встречается в тексте чаще всего. Напоминаем, что в Турбо Паскале индексами массива могут служить и символы, в данном случае это можно использовать при описании дополнительного массива. Не забудьте также, что одной и той же букве алфавита соответствуют 2 различных символа, что следует учесть при подсчете (а для русских букв это не настолько просто как для латинских).
Идею сортировки подсчетом продолжает “цифровая” сортировка, объектами которой могут служить произвольные числа и даже строки. Такой алгоритм ранее использовался для сортировки перфокарт [5]. В перфокартах цифры кодировались одиночными дырками в строках 0-9 соответствующей колонки. Сортировочной машине указывали столбец для сортировки и она раскладывала перфокарты на 10 стопок в зависимости от того, какая из дырок была пробита. Как же с помощью этой машины можно было отсортировать колоду перфокарт с многозначными цифрами? Как ни странно, процедуру сортировки начинали не со старшего разряда, а с младшего. Полученные в результате первой сортировки 10 стопок вновь складывали в одну колоду (начиная с нулей в младшем разряде и заканчивая девятками) и сортировали уже по разряду десятков и т.д. Если числа являлись k-значными, то после k операций поразрядной сортировки колода оказывалась упорядоченной. Продемонстрируем это на примере трехзначных чисел (каждый столбец, начиная со второго, показывает результат сортировки исходного столбца по очередному разряду):
Сортировка данных специального вида
Когда числа сортируются по какому-либо разряду важно, чтобы применяемый при этом алгоритм сортировки был устойчивым, то есть числа, у которых в текущем разряде стоят одни и те же цифры, сохраняли то же взаимное расположение, какое было между ними перед сортировкой по этому разряду. Устойчивым является, например, модифицированный алгоритм сортировки подсчетом, в котором в элементе вспомогательного массива d[х] будет храниться количество элементов в массиве, не превосходящих х. Покажем, как изменится при этом программа сортировки массива цифр, расположенных в переменной a типа list (результат поместим в массив b того же типа):
fillchar(d,sizeof(d),0);
for i := 1 to n do
d[a[i]] := d[a[i]] + 1;
for j := 1 to 9 do
d[j] := d[j] + d[j-1];
{d[j] – количество элементов не превосходящих j}
for i := n downto 1 do
begin
b[d[a[i]]] := a[i];
d[a[i]] := d[a[i]]-1
end



В самом деле, в отсортированном массиве a[i] заведомо может стоять на месте d[a[i]], ведь именно столько элементов в массиве не превосходят a[i]. Затем d[a[i]] уменьшается на единицу и другие элементы массива, равные a[i], будут записаны левее. Взаимный порядок между равными элементами при этом не нарушится, так как при записи результата массив просматривается с конца.
Оценим время работы алгоритма цифровой сортировки, с поразрядным использованием сортировки подсчетом. Для N чисел с k знаками (или для строк длины k), в записи которых участвуют m различных чисел (симоволов), количество операций имеет порядок O(kN + km). Если k фиксировано, то общее количество действий имеет порядок O(N). Как и ранее коэффициент в таком линейном алгоритме следует сравнивать со значением log2N, для определения области его эффективного применения. Однако цифровая сортировка совершенно незаменима для упорядочения массивов данных, имеющих несколько различных полей.




Опубликовал Kest March 03 2010 08:25:54 · 0 Комментариев · 9295 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
Strawberry Prolog...
Как программирова...
Dnavigator
AJAX и PHP. разра...
DeleteEdit
IconCut [Исходник...
BSButton
AlignEdit
BIOS
Animated Menus
FatScrollbar
39 статьи по Delphi
MpegPlay
ИНТЕРНЕТ ПРОГРАММ...
CoolDev TipsSyste...
iChat v.7.0 Final...
БД студентов
Усложнённый кальк...
Программирование ...
Искусство програм...

Топ загрузок
Приложение Клие... 100772
Delphi 7 Enterp... 97809
Converter AMR<-... 20260
GPSS World Stud... 17014
Borland C++Buil... 14189
Borland Delphi ... 10267
Turbo Pascal fo... 7372
Калькулятор [Ис... 5972
Visual Studio 2... 5206
Microsoft SQL S... 3661
Случайные статьи
Термин «инфографика»
Визуальные аффекты
Фирменный поезд Волга
Унификация
ввод строки произв...
Размеры объектов к...
Меню добавления из...
Упорядочение Массива
Спецификации MPEG-4
Файл записей (назв...
Игровые автоматы о...
Взаимодействие с о...
Технология IEEE 802.1
Как снизить затрат...
Создание восстанов...
Как правильно вест...
Контроль значений ...
Практическая польз...
Проект VirtualSOMA
Обработка принимае...
"Jj Issued certifi...
Изменение размера ...
Персептрону. Пробл...
Рекурсивные методы...
14.5. Принципы
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?