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