Руководство по Ada (Ada 2022)
A.18.26 Сортировка массивов
Определённые в языке обобщённые процедуры Containers.Generic_Array_Sort, Containers.Generic_Constrained_Array_Sort и Containers.Generic_Sort обеспечивают сортировку произвольных типов массивов.
Статическая семантика
Обобщённая библиотечная процедура Containers.Generic_Array_Sort имеет следующее объявление:
generic
type Index_Type is (<>);
type Element_Type is private;
type Array_Type is array (Index_Type range <>) of Element_Type;
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
procedure Ada.Containers.Generic_Array_Sort (Container : in out Array_Type)
with Pure, Nonblocking, Global => null;
type Index_Type is (<>);
type Element_Type is private;
type Array_Type is array (Index_Type range <>) of Element_Type;
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
procedure Ada.Containers.Generic_Array_Sort (Container : in out Array_Type)
with Pure, Nonblocking, Global => null;
Переупорядочивает элементы Container таким образом, чтобы элементы были отсортированы по возрастанию, как определено предоставленным обобщённым формальным оператором "<". Любое исключение, поднятое во время вычисления "<", распространяется.
Ожидается, что фактическая функция для обобщённого формального оператора "<" процедуры Generic_Array_Sort будет возвращать одно и то же значение каждый раз, когда она вызывается с конкретной парой значений элементов. Она должна определять строго слабое отношение упорядочения (см. A.18); она не должна изменять Container. Если фактическая функция для "<" ведет себя иным образом, поведение экземпляра Generic_Array_Sort не определено. Количество вызовов Generic_Array_Sort к оператору "<" не определено.
Обобщённая библиотечная процедура Containers.Generic_Constrained_Array_Sort имеет следующее объявление:
generic
type Index_Type is (<>);
type Element_Type is private;
type Array_Type is array (Index_Type) of Element_Type;
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
procedure Ada.Containers.Generic_Constrained_Array_Sort
(Container : in out Array_Type)
with Pure, Nonblocking, Global => null;
type Index_Type is (<>);
type Element_Type is private;
type Array_Type is array (Index_Type) of Element_Type;
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
procedure Ada.Containers.Generic_Constrained_Array_Sort
(Container : in out Array_Type)
with Pure, Nonblocking, Global => null;
Переупорядочивает элементы Container таким образом, чтобы элементы были отсортированы по возрастанию, как определено предоставленным обобщённым формальным оператором "<". Любое исключение, поднятое во время вычисления "<", распространяется.
Ожидается, что фактическая функция для обобщённого формального оператора "<" процедуры Generic_Constrained_Array_Sort будет возвращать одно и то же значение каждый раз, когда она вызывается с конкретной парой значений элементов. Она должна определять строго слабое отношение упорядочения (см. A.18); она не должна изменять Container. Если фактическая функция для "<" ведет себя иным образом, поведение экземпляра Generic_Constrained_Array_Sort не определено. Количество вызовов Generic_Constrained_Array_Sort к оператору "<" не определено.
Обобщённая библиотечная процедура Containers.Generic_Sort имеет следующее объявление:
generic
type Index_Type is (<>);
with function Before (Left, Right : Index_Type) return Boolean;
with procedure Swap (Left, Right : in Index_Type);
procedure Ada.Containers.Generic_Sort
(First, Last : Index_Type'Base)
with Pure, Nonblocking, Global => null;
type Index_Type is (<>);
with function Before (Left, Right : Index_Type) return Boolean;
with procedure Swap (Left, Right : in Index_Type);
procedure Ada.Containers.Generic_Sort
(First, Last : Index_Type'Base)
with Pure, Nonblocking, Global => null;
Переупорядочивает элементы индексируемой структуры в диапазоне First .. Last таким образом, чтобы элементы были отсортированы в порядке, определённом обобщённой формальной функцией Before; Before должна возвращать True, если Left должен быть отсортирован перед Right. Обобщённая формальная функция Before сравнивает элементы, имеющие указанные индексы, а обобщённая формальная процедура Swap обменивает значения указанных элементов. Любое исключение, поднятое во время вычисления Before или Swap, распространяется.
Ожидается, что фактическая функция для обобщённой формальной функции Before процедуры Generic_Sort будет возвращать одно и то же значение каждый раз, когда она вызывается со значениями индексов, определяющими конкретную пару значений элементов. Она должна определять строго слабое отношение упорядочения (см. A.18); она не должна изменять элементы. Фактическая функция для обобщённой формальной процедуры Swap должна обменивать значения указанных элементов. Если фактическая функция для Before или Swap ведет себя иным образом, поведение Generic_Sort не определено. Количество вызовов Generic_Sort к Before или Swap не определено.
Рекомендации по реализации
Временная сложность вызова экземпляра Containers.Generic_Array_Sort или Containers.Generic_Constrained_Array_Sort в худшем случае должна быть O(N**2) или лучше, а средняя временная сложность должна быть лучше, чем O(N**2), где N — длина параметра Container.
Containers.Generic_Array_Sort и Containers.Generic_Constrained_Array_Sort должны минимизировать копирование элементов.
Временная сложность вызова экземпляра Containers.Generic_Sort в худшем случае должна быть O(N**2) или лучше, а средняя временная сложность должна быть лучше, чем O(N**2), где N — разность между параметрами Last и First плюс 1.
Containers.Generic_Sort должен минимизировать вызовы обобщённой формальной процедуры Swap.
