Навигация
Главная
Поиск
Форум
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
Имитационное мо... 59618
Реклама
Сейчас на сайте
Гостей: 3
На сайте нет зарегистрированных пользователей

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

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

Реклама



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

ПОДПИСЫВАЙСЯ на канал о программировании
Постановка задачи сортировки данных
Задача сортировки часто возникает при создании различных систем автоматизации обработки данных на базе ЭВМ. В настоящее время известно множество алгоритмов сортировки, свойства которых достаточно хорошо изучены. Прежде чем рассмотреть основные из них, необходимо ввести базовые исходные понятия и сформулировать задачу.
Под данными в системах обработки данных понимаются описания фактов и понятий предметной области на формализованном входном языке описания данных. Средствами языка данные представляются в виде наборов (совокупностей) различных символов из некоторого исходного конечного множества символов, называемого алфавитом. Отдельные символы, входящие в эти наборы, являются элементами данных (простейшими данными). Они могут группироваться (объединяться), образуя различные структуры данных.
Под структурой данных в широком смысле понимается группа простейших данных, между которыми по определенному принципу установлены различные отношения. Структура данных, состоящая из элементов, связанных друг с другом по смыслу и обрабатываемых совместно, называется записью данных. Записи обычно делятся на части, которые называются полями. В ряде задач обработки данных к записям добавляется специальное поле, служащее для идентификации (определения) каждой записи по отношению к другим записям. Содержимое такого поля называется ключом записи. Конечная совокупность нескольких поименованных записей, в каждой из которых хранится однотипная информация на некотором внешнем носителе, например, магнитном, образует структуру данных, называемую файлом. Подобная же совокупность записей, хранящаяся в памяти, называется массивом.
Задача сортировки данных, решаемая для массивов и файлов, может быть сформулирована следующим образом.
Пусть имеется массив (файл) записей R1, R2, …, RN с ключами K1, K2, …, KN . На множестве ключей Ki, i=1, N вводится такое отношение порядка типа “≤”, что для любых трех значений ключей a, b, c выполняются следующие условия:
1) рефлексивность: a≤a;
2) антисимметричность: если a≤b, b≤a, то a=b;
3) транзитивность: если a≤b, b≤c, то a≤c;
4) линейность: для произвольных a и b
Любое множество записей, ключи которых удовлетворяют свойствам 1-4, называется полностью (линейно) упорядоченным (или совершенно упорядоченным).
Задача упорядочения (сортировки) данных состоит в том, чтобы найти такую перестановку записей, т.е. такую комбинацию их взаимного расположения, при которой ключи Ki расположились бы в неубывающем порядке:
K1 ≤ K2 ≤ … KN.
Если имеется возможность переставлять записи в произвольном порядке (в случае, когда все Ki различны, получится N! таких перестановок), то процесс переразмещения записей в упорядоченную последовательность называется сортировкой. Сортировка называется устойчивой, если она сохраняет упорядоченность записей и в случае равенства ключей отдельных записей. Сортировка записей, хранящихся в памяти, называется внутренней. Сортировка, которая выполняется для записей в файлах, называется внешней.
В дальнейшем рассматриваются методы внутренней сортировки на примере упорядочения простой последовательности целых чисел (x1, x2, …,xn), для которых значение ключа совпадает со значением элемента последовательности.
Примечание. Помимо понятия линейного упорядочения существует понятие лексикографического упорядочения, которое используется в задачах обработки буквенно-символьной информации. В узком смысле лексикографический порядок – это порядок слов в словаре, определяемый последовательностью букв некоторого алфавита. В общем случае рассматривается некоторое множество символов S={xi}, i=1, n, на котором существует отношение порядка “≤”. Для n>0 вводится множество T n-кортежей (x1, x2, …,xn), для которых определяется отношение упорядочения:
(x1, x2, …,xn) < (y1, y2, …,yn)
тогда и только тогда, когда существует некоторое значение k, 1≤k≤n, для которого xi=yi при 1≤i Если все кортежи расположены в соответствии с указанным отношением, то множество T считается лексикографически упорядоченным. Рассмотренное понятие может быть обобщено и для кортежей (строк) неодинаковой длины. При этом порядок строк будет совпадать с порядком слов в словаре.
Опубликовал Kest December 24 2009 22:42:42 · 0 Комментариев · 11189 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
PrevInst
oTextrackBar
Bitmap [для кнопок]
Pirc
3d Tank [Исходник...
RSS Feeds
Приемы программир...
45 уроков по дельфи
Графика в проекта...
Проигрыватель Mp3
AlnComponents
Архив Апгрейтов с...
Tag Игра "Пятнашк...
Изучаем Ассемблер
Программирование ...
Шейдеры в Delphi
TrayIcon
Работа с картотеками
Email
Модифицированная ...

Топ загрузок
Приложение Клие... 100515
Delphi 7 Enterp... 90481
Converter AMR<-... 20093
GPSS World Stud... 15031
Borland C++Buil... 12761
Borland Delphi ... 8967
Turbo Pascal fo... 7097
Калькулятор [Ис... 5140
Visual Studio 2... 5020
FreeSMS v1.3.1 3555
Случайные статьи
Шкафы-купе в Гомеле
Эталонная модель п...
Модуль Link. Прило...
Терминология языка...
Как происходит пер...
Системные числовые...
14.6. Задачи
WDTABLE (РАЗНОСТНА...
Тестирование
Файловый ввод-выво...
Обеспечение достав...
Как быть, если при...
Палитра VGA: управ...
Под категориями ст...
Что входит в Servi...
Аккуратно работаем...
Многострочный реда...
Второй этап маршру...
5 способов повышен...
К головоломке
Управляющий термин...
На вход поступает ...
Бюджетные цветные ...
5.5. Объявление о...
Процедура итерацио...
Статистика



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


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