Структуры данных и модели вычислений



             

Применение приоритетных очередей в задаче сортировки


Под задачей сортировки в простейшем случае понимают следующее: дана последовательность

из элементов некоторого линейно упорядоченного множества, например целых или вещественных чисел, записанных в массив . Требуется переставить элементы массива так, чтобы после перестановки выполнялись неравенства:

Уточнения этой задачи связаны с теми средствами, с помощью которых предполагается ее решение. Нас интересуют алгоритмы с точки зрения их компьютерной реализации. Оценивая качество различных алгоритмов, обычно интересуются тем, как зависит время счета от длины сортируемой последовательности и требуется ли для этого дополнительная память, размер которой определяется параметром . Существенную роль при этом играет метод доступа к элементам памяти. При сортировке во внутренней (оперативной) памяти обычно используется прямой доступ, а во внешней — последовательный.




Содержание  Назад  Вперед