Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Алгоритмы и структуры данных

СОРТИРОВКА

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

Сортировкой называют процесс перегруппировки заданного множества объектов в некотором определенном порядке. Сортировка (sorting) — распределение по сортам, деление на категории. Программисты используют более узкий термин — упорядочение (ordering), однако использование этого слова может привести к путанице из-за перегруженности слова «порядок». Ранжирование (sequencing) не всегда отражает суть дела, особенно если есть равные элементы. Часто используются все три термина с одним и тем же смыслом.

Цель сортировки — облегчение последующего поиска элементов в отсортированном множестве во внутренней или внешней памяти. В последнем случае она особенно важна, если имеется только последовательный доступ к файлам (появляется возможность приемлемой замены прямого доступа).

Сортировка и поиск в той или иной мере присутствуют во всех приложениях. При обработке больших объемов данных эффективность именно этих операций определяет эффективность, а иногда и работоспособность всей системы.

Зависимость выбора алгоритма сортировки от структуры данных настолько сильна, что методы сортировки обычно разделяют на две категории: сортировка массивов и сортировка последовательных файлов. Их также называют внутренней и внешней сортировкой.

Постановка задачи. Пусть задана последовательность элементов ах2,...,ап . Сортировка означает перестановку элементов в таком порядке akl,ak2,...,akn , что при заданной функции упорядочения/ справедливы отношения: f(ak[)< /(ak2)<...< /(akn). Функция упорядочения задает отношение порядка. Ее значение f(aki) называется ключом элемента и, как правило, содержится в каждом элементе в виде явной компоненты (поля). В простейшем случае ключом может являться само значение я,.

Для представления элемента сортируемой последовательности хорошо подходит такая структура данных, как запись, одной из компонент которой является ключ элемента, а другими компонентами являются все существенные данные об элементе. Исходную последовательность при этом можно описать как массив из п записей-элементов.

Метод сортировки называется устойчивым, если исходный порядок расположения элементов с равными ключами не изменяется при сортировке.

Поведение сортировки называется естественным, если наибольшие затраты на сортировку необходимы в случае обратной упорядоченности исходной последовательности.

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ   След >
 

Популярные страницы