Навигация
Главная
Поиск
Форум
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
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65535
Имитационное мо... 61570
Реклама
Сейчас на сайте
Гостей: 4
На сайте нет зарегистрированных пользователей

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

Моделирование процесса передачи данных по магистрали с основным и резерв...
Выбор наилучших альтернатив с использованием методов оптимизации на Delp...
Моделирование работы аэропорта на GPSS + Пояснительная записка

Реклама



Подписывайся на 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 Март 03 2010 11:25:54 · 0 Комментариев · 8479 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Bitmap [для кнопок]
iComm v.6.1 - выв...
DAlarm
THttpScan v4.1
Rss Parser
ЯЗЫК ПРОГРАММИРОВ...
Размещение элемен...
Assembler. Практикум
Цветной Grid
Email
DiskInfo
PHP в примерах
XPButtons
Delphi 2005. Разр...
C# 2005 и платфор...
Illusion
Proeffectimage
Delphix Sample [И...
Mass Photo Upload
Animation Effect ...

Топ загрузок
Приложение Клие... 100552
Delphi 7 Enterp... 93023
Converter AMR<-... 20116
GPSS World Stud... 15855
Borland C++Buil... 13350
Borland Delphi ... 9346
Turbo Pascal fo... 7133
Калькулятор [Ис... 5300
Visual Studio 2... 5047
FreeSMS v1.3.1 3570
Случайные статьи
Когда посетитель п...
Формирование прогр...
SEO-копирайтинг в ...
Особенности практи...
4.3.1. Подтвержде...
Соединения должны ...
использование SNMP...
Введение в создани...
Сертификация специ...
Основные понятия п...
Базис I, B, C, S
Создание документа
Экспертные системы...
НЕОДНОЗНАЧНЫЕ ГРУППЫ
Ввидеоизображение ...
2.1. Вездесущий дв...
Преобразование иде...
Временные меры чис...
11.5. Задачи
Поиск минимума фун...
История языков про...
Списки определений
фальсифицированным...
Практическая реали...
Управление Выводом...
Статистика



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


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