A.18.16 Array Sorting
The language-defined generic procedures Containers.Generic_Array_Sort
and Containers.Generic_Constrained_Array_Sort provide sorting on arbitrary
array types.
Static Semantics
The generic library
procedure Containers.Generic_Array_Sort has the following declaration:
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);
Reorders the elements of Container such that the
elements are sorted smallest first as determined by the generic formal
"<" operator provided. Any exception raised during evaluation
of "<" is propagated.
The actual function for the generic formal function
"<" of Generic_Array_Sort is expected to return the same
value each time it is called with a particular pair of element values.
It should define a strict ordering relationship, that is, be irreflexive,
asymmetric, and transitive; it should not modify Container. If the actual
for "<" behaves in some other manner, the behavior of the
instance of Generic_Array_Sort is unspecified. How many times Generic_Array_Sort
calls "<" is unspecified.
The generic library
procedure Containers.Generic_Constrained_Array_Sort has the following
declaration:
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);
Reorders the elements of Container such that the
elements are sorted smallest first as determined by the generic formal
"<" operator provided. Any exception raised during evaluation
of "<" is propagated.
The actual function for the generic formal function
"<" of Generic_Constrained_Array_Sort is expected to return
the same value each time it is called with a particular pair of element
values. It should define a strict ordering relationship, that is, be
irreflexive, asymmetric, and transitive; it should not modify Container.
If the actual for "<" behaves in some other manner, the
behavior of the instance of Generic_Constrained_Array_Sort is unspecified.
How many times Generic_Constrained_Array_Sort calls "<"
is unspecified.
Implementation Advice
The worst-case time complexity of a call on an instance
of Containers.Generic_Array_Sort or Containers.Generic_Constrained_Array_Sort
should be O(N**2) or better, and the average time complexity
should be better than O(N**2), where N is the length
of the Container parameter.
Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort
should minimize copying of elements.
Sponsored by Ada-Europe