next up previous index
Next: Place element in Up: Sorting and related Previous: Sorting and related

Sort a range (unstably, stably, or partially)

Source code

Declaration

template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
          Compare comp);

template <class RandomAccessIterator>
inline void stable_sort(RandomAccessIterator first,
                        RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
inline void stable_sort(RandomAccessIterator first,
                        RandomAccessIterator last, Compare comp);

template <class RandomAccessIterator>
inline void partial_sort(RandomAccessIterator first,
                         RandomAccessIterator middle,
                         RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
inline void partial_sort(RandomAccessIterator first,
                         RandomAccessIterator middle,
                         RandomAccessIterator last, Compare comp);

template <class InputIterator, class RandomAccessIterator>
inline RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
                  RandomAccessIterator result_first,
                  RandomAccessIterator result_last);

template <class InputIterator, class RandomAccessIterator, class Compare>
inline RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
                  RandomAccessIterator result_first,
                  RandomAccessIterator result_last, Compare comp);

Description The sort functions sort the elements in the range [ first, last) , but does not preserve the order of equal elements. The first sort function determines the ordering using operator< and the second sort function determines the ordering using the function object comp.

The stable_sort functions sort the elements in the range [ first, last) , preserving the relative ordering of equal elements. The first stable_sort function determines the ordering using operator< and the second stable_sort function determines the ordering using the function object comp.

The partial_sort functions sorts the elements in the range [ first, last) \ to the extent that the range [ first, middle) contains the first n elements of the fully sorted sequence, where n is the size of the range [ first, middle) . The elements in the range [ middle, last) are placed in an undefined order. The first partial_sort function determines the ordering using operator< and the second partial_sort function determines the ordering using the function object comp.

The partial_sort_copy functions place the first n sorted elements from the range [ first, last) into the range of size n beginning at result_first, where n is the smaller size of the ranges [ first, last) and [ result_first, result_last) . The contents of the range [ first, last) remain unchanged. The first partial_sort_copy function determines the ordering using operator< and the second partial_sort_copy function determines the ordering using the function object comp.

Type requirements

Group Sorting and related operations

Time complexity average for the sort functions, at most for the stable_sort functions, and for the partial_sort and partial_sort_copy functions, where n is the size of the range [ first, last) . For the partial_sort functions, m is the size of the range [ middle, last) . For the partial_sort_copy functions, m is the smaller size of the ranges [ first, last) and [ result_first, result_last) .

The sort functions make comparisons on the average. In the worst case, it takes time and makes comparisons. If the worst case behavior is important, then the stable_sort or partial_sort functions should be used.

The stable_sort functions make at most comparisons. However, if enough memory is available for the buffer required by the adaptive version of the algorithm, the time and number of comparisons are .

The partial_sort functions make approximately comparisons.

The partial_sort_copy functions make approximately

comparisons.

Space complexity Logarithmic for the sort functions, at most linear for the stable_sort functions, and constant for the partial_sort and partial_sort_copy functions.

The sort functions require space for recursive calls, where n is the size of the range [ first, last) .

The stable_sort functions require linear space for buffer if the adaptive algorithm is used and the buffer is large enough to have half of the sequence placed in it, otherwise logarithmic space is required for recursive function calls (linear space may also be used for some buffer size that is not large enough to contain half of the sequence).

The partial_sort functions and the partial_sort_copy functions require constant space.

Mutative? Yes.

Example Select here to view the source code for the example.

 

Implementation Select here to view source code (Copyright (C) 1994, Hewlett-Packard Company) for this algorithm.



next up previous index
Next: Place element in Up: Sorting and related Previous: Sorting and related



Kenny Zalewski
Mon May 13 04:03:40 EDT 1996