Annotated Ada Reference ManualLegal Information
Contents   Index   References   Search   Previous   Next 

A.18.16 Array Sorting

1/2
{AI95-00302-03} The language-defined generic procedures Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort provide sorting on arbitrary array types. 

Static Semantics

2/2
{AI95-00302-03} The generic library procedure Containers.Generic_Array_Sort has the following declaration: 
3/2
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);
4/2
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.
5/2
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.{unspecified [partial]}
5.a/2
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.
5.b/2
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. 
6/2
{AI95-00302-03} The generic library procedure Containers.Generic_Constrained_Array_Sort has the following declaration: 
7/2
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);
8/2
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.
9/2
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.{unspecified [partial]}

Implementation Advice

10/2
{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. 
10.a/2
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).
10.b/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! 
11/2
{AI95-00302-03} Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort should minimize copying of elements. 
11.a/2
Implementation Advice: Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort should minimize copying of elements.
11.b/2
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. 

Extensions to Ada 95

11.c/2
{AI95-00302-03} {extensions to Ada 95} The generic packages Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort are new. 

Contents   Index   References   Search   Previous   Next 
Ada-Europe Sponsored by Ada-Europe