sort(3C++)


sort -- sort an array in place

Synopsis

   template <class T>
   void sort(T* b,T* e);
   template <class T>
   void sort_r(int (*rel)(const T*,const T*),T* b,T* e);
   template <class T>
   void sort_rs(int (*rel)(const T*,const T*),T* b,T* e);
   template <class T>
   void sort_s(T* b,T* e);

Assumptions

(1) For the non-relational versions, T::operator< defines a total ordering relation on T.

(2) For the relational version, rel defines a total ordering relation on T.

(3) T has operator=.

Description

These functions sort an array in place.

   template <class T>
   void sort(T* b,T* e);

Uses T::operator< to define the ordering relation used by the sorting algorithm sort is not stable; that is, it does not preserve the relative order of equal elements.

   template <class T>
   void sort_r(int (*rel)(const T*,const T*),T* b,T* e);

Uses rel to define the ordering relation used by the sorting algorithm.

   template <class T>
   void sort_rs(int (*rel)(const T*,const T*),T* b,T* e);

Like sort_r except that it uses a stable algorithm. That is, the relative order of equal elements is preserved.

   template <class T>
   void sort_s(T* b,T* e);

Like sort except that it uses a stable algorithm. That is, the relative order of equal elements is preserved.

Complexity

If N is the size of the array, then complexity is O(NlgN) on average. Complexity is O(N*N) in the worst case, which is highly improbable.

Notes

The non-stable versions use drand48(3C) to obtain pseudo-random numbers.

Because a Block (see Block(3C++)) can always be used wherever an array is called for, Array Algorithms can also be used with Blocks. In fact, these two components were actually designed to be used together.

References

   Array_alg(3C++)
   drand48(3C)
   ins_sort(3C++)
   merge_sort(3C++)
   Block(3C++)

© 2004 The SCO Group, Inc. All rights reserved.
UnixWare 7 Release 7.1.4 - 25 April 2004