ins_sort(3C++)


ins_sort -- sort an array using an insertion sort algorithm

Synopsis

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

Assumptions

(1) For the plain version, 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 stably sort an array in place using an insertion sort algorithm.

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

Uses T::operator< to define the ordering relation used by the sorting algorithm.

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

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

Complexity

If N is the size of the array, then complexity is O(N*N). On average, N*N/4 tests of the ordering relation and N*N/4 assignments are done.

Notes

Insertion sorting is the algorithm of choice when either: 1) the size of the array is small; OR 2) the number of elements out of order is small; OR 3) the average distance between the original position of an element and its final destination is small. (By "small" we mean less than 16.)

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++), merge_sort(3C++), sort(3C++), Block(3C++)
© 2004 The SCO Group, Inc. All rights reserved.
UnixWare 7 Release 7.1.4 - 25 April 2004