A.18.26 Array Sorting
{
AI95-00302-03}
{
AI05-0001-1}
The language-defined generic procedures Containers.Generic_Array_Sort,
Containers.Generic_Constrained_Array_Sort, and Containers.Generic_Sort
provide sorting on arbitrary array types.
Static Semantics
{
AI95-00302-03}
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.
{
AI05-0044-1}
{
AI05-0262-1}
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 weak ordering relationship (see
A.18);
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. The number of times Generic_Array_Sort calls "<"
is unspecified.
Ramification: This implies swapping the
elements, usually including an intermediate copy. This of course means
that the elements will be copied. Since the elements are nonlimited,
this usually will not be a problem. Note that there is Implementation
Advice below that the implementation should use a sort that minimizes
copying of elements.
The sort is not required to be stable (and the
fast algorithm required will not be stable). If a stable sort is needed,
the user can include the original location of the element as an extra
"sort key". We considered requiring the implementation to do
that, but it is mostly extra overhead -- usually there is something already
in the element that provides the needed stability.
{
AI95-00302-03}
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.
{
AI05-0044-1}
{
AI05-0262-1}
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 weak ordering relationship (see
A.18);
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. The number of times Generic_Constrained_Array_Sort calls
"<" is unspecified.
{
AI05-0001-1}
The generic library procedure Containers.Generic_Sort has the following
declaration:
{
AI12-0056-1}
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);
{
AI05-0001-1}
{
AI05-0248-1}
Reorders the elements of an indexable structure, over the range First
.. Last, such that the elements are sorted in the ordering determined
by the generic formal function Before; Before should return True if Left
is to be sorted before Right. The generic formal Before compares the
elements having the given indices, and the generic formal Swap exchanges
the values of the indicated elements. Any exception raised during evaluation
of Before or Swap is propagated.
The actual function for the generic formal function
Before of Generic_Sort is expected to return the same value each time
it is called with index values that identify a particular pair of element
values. It should define a strict weak ordering relationship (see
A.18);
it should not modify the elements. The actual function for the generic
formal Swap should exchange the values of the indicated elements. If
the actual for either Before or Swap behaves in some other manner, the
behavior of Generic_Sort is unspecified. The number of times the Generic_Sort
calls Before or Swap is unspecified.
Implementation Advice
{
AI95-00302-03}
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.
Implementation Advice: Containers.Generic_Array_Sort
and Containers.Generic_Constrained_Array_Sort should have an average
time complexity better than O(N**2) and worst case no worse
than O(N**2).
Discussion: In other words, we're requiring
the use of a sorting algorithm better than O(N**2), such
as Quicksort. No bubble sorts allowed!
{
AI95-00302-03}
Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort
should minimize copying of elements.
Implementation Advice: Containers.Generic_Array_Sort
and Containers.Generic_Constrained_Array_Sort should minimize copying
of elements.
To be honest: We do not mean “absolutely
minimize” here; we're not intending to require a single copy for
each element. Rather, we want to suggest that the sorting algorithm chosen
is one that does not copy items unnecessarily. Bubble sort would not
meet this advice, for instance.
{
AI05-0248-1}
The worst-case time complexity of a call on an instance of Containers.Generic_Sort
should be
O(
N**2) or better, and the average time complexity
should be better than
O(
N**2), where
N is the difference
between the Last and First parameters plus 1.
Implementation Advice: Containers.Generic_Sort
should have an average time complexity better than O(N**2)
and worst case no worse than O(N**2).
{
AI05-0248-1}
Containers.Generic_Sort should minimize calls to the generic formal Swap.
Implementation Advice: Containers.Generic_Sort
should minimize calls to the generic formal Swap.
Extensions to Ada 95
{
AI95-00302-03}
The generic procedures Containers.Generic_Array_Sort
and Containers.Generic_Constrained_Array_Sort are new.
Extensions to Ada 2005
Wording Changes from Ada 2005
{
AI05-0044-1}
Correction: Redefined "<" actuals to require a strict
weak ordering; the old definition allowed indeterminant comparisons that
would not have worked in a sort.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
