Справочник по Ada 2012
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);
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 возвращает одно и то же значение каждый раз, когда она вызывается с конкретной парой значений элементов. Она должна определять отношение строгой слабой упорядоченности (см. 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);
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 возвращает одно и то же значение каждый раз, когда она вызывается с конкретной парой значений элементов. Она должна определять отношение строгой слабой упорядоченности (см. 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);
pragma Pure(Ada.Containers.Generic_Sort);
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);
pragma Pure(Ada.Containers.Generic_Sort);
Переупорядочивает элементы индексируемой структуры в диапазоне 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.
