Навигация
Главная
Поиск
Форум
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
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65535
ТЕХНОЛОГИИ ДОСТ... 65296
Имитационное мо... 59116
Реклама
Сейчас на сайте
Гостей: 2
На сайте нет зарегистрированных пользователей

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

Создание последовательности окон и передвижение окон по экрану на Turbo ...
Калькулятор на Delphi с переводом в другую систему исчисления + Блок схемы
Лабораторная работа по динамическим спискам на Turbo Pascal (перемещение...

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
Сортировка данных специального вида
Выше было показано, как следует использовать так называемые универсальные алгоритмы сортировки, пригодные для любого вида данных, подлежащих сравнению. Однако, зачастую информация о множестве значений, которые могут принимать элементы массива, может в корне изменить подход к сортировке. Пусть, например, требуется отсортировать 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 11:25:54 · 0 Комментариев · 8273 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Паскаль и Дельфи....
Программа рисует ...
mp3tag
Battle.Net - мони...
AdBlaster v2.5 - ...
Цветной Grid
Flud Vkontakte.ru
Распознавание тек...
Последнее загруж...
TMS
Программирование ...
Панель для реклам...
MPTools
3D Тетрис [Исходн...
oTextrackBar
БД сеть компьютер...
Delphi 2005 для W...
Библия хакера 2 К...
45 уроков по дельфи
Geo-Whois

Топ загрузок
Приложение Клие... 100505
Delphi 7 Enterp... 89562
Converter AMR<-... 20090
GPSS World Stud... 14465
Borland C++Buil... 12519
Borland Delphi ... 8879
Turbo Pascal fo... 7082
Калькулятор [Ис... 5061
Visual Studio 2... 5016
FreeSMS v1.3.1 3552
Случайные статьи
НЕ ВСЕГДА БАЗА ДАН...
Содержание
Как поисковые сист...
PHP против ASP - В...
Краткая история Ni...
Инсталляция библио...
Принципы обработки...
Средство поиска
Интерфейс TPI
а: определение эфф...
Джампер
XV
Оценка точности оп...
Правила размещения...
Доставка суши
Также необходимо з...
Использование «умн...
Единственное, что ...
Наследование
Поиск максимальног...
Безопасная съемка ...
Способ достижения ...
Гармоники или моды
Импорт статических...
Установка указанны...
Статистика



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


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