ШИтак, сортдерево выгодно применять для выделения экстремального подмножества. Выгоды — те же. Запись с экстремальным значением окажется последней в массиве А, а все искомое подмножество займет г последних позиций массива А. Измените блок Ех. Частичная сортировка Иногда приемлема частичная сортировка . Представьте, что все они — во . Если на следующих шагах также возникают части, не перекрывающие ни одну из указанных позиций, то и они пропускаются, т. экономия времени может быть значительной. Она зависит от числа и равномерности размещения в массиве . Функция — правило сортировки Часто упорядочение записей выполняют по составному ключу. Например, штатный список предприятия выводят по отделам . Отдел определяет старшую часть ключа, фамилия — младшую. Для этой цели пригодна сопоставительная сортировка, должным образом приспособленная. Так как названия полей записи определяет пользователь, на него и возложим определение блока сравнения двух записей. Сортировка методом Шелла. оценки метода Шелла в п. записи копируются при входе в подблок. Массив А состоит из записей, содержащих фамилию сотрудника . Последнее поле имеет тип . Выведем список сотрудников — по отделам, а в отделах — сначала женщин, потом мужчин, причем в каждой такой группе установим порядок по убыванию стажа . В теле функции . Запишите программу примера . Сортировка СОРТЛЕСОМ виртуального массива Упорядочение наборов записей, занимающих в памяти более . Если же сортируемые данные не умещаются в памяти, большой размер исходных упорядоченных частей сократит время внешней сортировки этих данных. Специальная реализация метода СОРТЛЕСОМ позволяет довольно просто выполнять сортировку виртуального массива, занимающего несколько сегментов. Отсортированная последовательность будет начинаться в первом сегменте и заканчиваться — в последнем. Многократно производится выбор наибольшего из корневых элементов деревьев . С каждым из них выполняется пересыпка в том дереве, откуда был взят вытесняющий элемент. В конце концов сортдерево с наибольшим номером исчезнет и последний сегмент будет занят самыми большими элементами. Процесс продолжится вытеснением листьев предпоследнего дерева, а закончится пересыпкой листьев в единственном . Выбор наибольшего из корней выполняется с помощью наддерева . Надцерево — это специфическое сортдерево. Блок УпЩ, выполняющий сортировку записей, размещенных в кз сегментах памяти по тт штук в каждом, кроме, возможно, последнего, содержащего пр записей. Показаны также типы и константы, описанные вне блока, и функция Г — правило сортировки. Сопоставительная специальная сортировка Рассмотрим еще один пример необычной сортировки. Число ё таких уровней выполнения будем задавать и называть глубиной поиска. Такая сортировка встречается, например, при социологических исследованиях. Прикиньте, сколько потребуется актов поиска, если отказаться от сортировки. Данная сортировка может быть сопоставительной и отобразительной. Разделим записи в массиве на те, у которых первое требование выполнено . Способ разделения подобен способу в БЫСТРСОРТ. Аналогично разделим группу записей с выполненным . В конце концов, начало массива займут записи с максимальным числом выполненных требований. Все однако не так просто. В других, оставленных ранее группах, возможны записи с выполненным . Поэтому могут обнаружиться записи с таким же числом выполненных требований, как в неразделившейся группе. Логику их выявления путем . Группу, в которой очередное требование выполняется . Очередность шагов разделения показана номерами между расходящимися стрелками. Фигурные скобки обозначают . Их записи далее сортируются совместно. Пунктирной рамкой обозначается пустая группа. Откат изображен штриховой линией, идущей от пустой плюс. Происходит откат к минус. Они смыкаются с группой . Если бы далее проверялось еще и . Число таких откатов бывает равно числу требований минус фактический максимум выполненных в одной записи требований. Другой причиной откатов является неединичная глубина поиска . Конечно же, пример искусственный. В реальном применении требования могут относиться к разным полям записи и быть сложными. При рассмотрении процедуры . Вначале в качестве границ разделяемой группы берем . Получаемую точку раздела запоминаем в предпоследнем элементе массива . Нижние границы плюсгрупп, равные . Итак, переходя к делению новой плюс. При этом увеличиваем номер . Все это происходит во внутреннем . При этом возрастает счетчик . В нашем примере . Выход из внутреннего цикла произойдет по завершении . надо выделить еще одну группу записей, в которых выполняется . Фигурные скобки на схеме изображают смыкание, . внешняя граница как бы передвигается, захватывая вновь выявленные записи. Теперь о результате. В этом случае в . Обдумайте модификацию алгоритма для случая, когда выполнение некоторых заданных требований строго обязательно. Отобразительная специальная сортировка Прежде, чем рассмотреть другой путь выполнения той же сортировки, оценим первый. Его сложность зависит от частоты выполнения заданных требований в записях, наличия пустых плюс. Сумма ряда близка к . В самом деле, если учтем склеивания групп перед разделениями, получим следующий ряд размеров групп, анализируемых между . , , , . Сумма ряда близка к . Поскольку число откатов определяется глубиной ё . Здесь мы впервые будем сортировать не значения, взятые из записей, а значения функции от содержания записи. Этой функцией будет число выполненных в записи требований. Группа записей характеризуется общим рангом. Как в алгоритме из примера . при п кр равна О. Например, можно придать требованиям ту или иную значимость — вес, учитываемый при подсчете значения . При нецелых весах значение Г округляется. Запишите пример функции Г для случая взвешенных требований и укажите, что следует изменить в программе. Типичная обработка упорядоченных данных Разбиение множества записей на классы, выполняемое с помощью сортировки, типично.