Справочник по Ada 2005
A.18.16 Сортировка массивов
Определяемые языком обобщенные процедуры Containers.Generic_Array_Sort и Containers.Generic_Constrained_Array_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);
pragma Pure(Ada.Containers.Generic_Array_Sort);
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);
pragma Pure(Ada.Containers.Generic_Array_Sort);
Переупорядочивает элементы Container таким образом, чтобы элементы были отсортированы по возрастанию, как определено предоставленным обобщенным формальным оператором "<". Любое исключение, возникшее во время вычисления "<", передается вверх.
Ожидается, что фактическая функция для обобщенного формального оператора "<" в Generic_Array_Sort возвращает одно и то же значение каждый раз при вызове с конкретной парой значений элементов. Она должна определять строгое отношение порядка, то есть быть антирефлексивной, антисимметричной и транзитивной; она не должна изменять 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);
pragma Pure(Ada.Containers.Generic_Constrained_Array_Sort);
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);
pragma Pure(Ada.Containers.Generic_Constrained_Array_Sort);
Переупорядочивает элементы Container таким образом, чтобы элементы были отсортированы по возрастанию, как определено предоставленным обобщенным формальным оператором "<". Любое исключение, возникшее во время вычисления "<", передается вверх.
Ожидается, что фактическая функция для обобщенного формального оператора "<" в Generic_Constrained_Array_Sort возвращает одно и то же значение каждый раз при вызове с конкретной парой значений элементов. Она должна определять строгое отношение порядка, то есть быть антирефлексивной, антисимметричной и транзитивной; она не должна изменять Container. Если фактическая функция для "<" ведет себя каким-либо иным образом, поведение экземпляра Generic_Constrained_Array_Sort не определено. Количество вызовов Generic_Constrained_Array_Sort оператора "<" не определено.
Рекомендации по реализации
Временная сложность в худшем случае вызова экземпляра 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 должны минимизировать копирование элементов.
