## partial_sort

    Algorithm

- Summary
- Data Type and Member Function Indexes
- Synopsis
- Description
- Complexity
- Example
- Warnings
- See Also

### Summary

Templatized algorithm for sorting collections of entities.

### Data Type and Member Function Indexes
(exclusive of constructors and destructors)

None

### Synopsis

    #include <algorithm>
    template <class RandomAccessIterator>
     void partial_sort (RandomAccessIterator first,
                        RandomAccessIterator middle,
                        RandomAccessIterator last);

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

### Description

The partial_sort algorithm takes the range `[first,last)` and places the first `middle - first` values into sorted order. The result is that the range `[first, middle)` is sorted like it would be if the entire range `[first,last)` were sorted. The remaining elements in the range (those in `[middle, last)`) are not in any defined order. The first version of the algorithm uses less than (`operator<`) as the comparison operator for the sort. The second version uses the comparison function `comp.`

### Complexity

partial_sort does approximately `(last - first) * log(middle-first)` comparisons.

### Example

    //
    // partsort.cpp
    //
    #include <vector>
    #include <algorithm>
    #include <iostream>
    using namespace std;

    int main()
     {
       int d1[20] = {17, 3,  5,  -4, 1, 12, -10, -1, 14, 7,
                     -6, 8, 15, -11, 2, -2,  18,  4, -3, 0};
       //
       // Set up a vector.
       //
       vector<int> v1(d1+0, d1+20);
       //
       // Output original vector.
       //
       cout << "For the vector: ";
       copy(v1.begin(), v1.end(),
            ostream_iterator<int,char>(cout," "));
       //
       // Partial sort the first seven elements.
       //
       partial_sort(v1.begin(), v1.begin()+7, v1.end());
       //
       // Output result.
       //
       cout << endl << endl << "A partial_sort of seven elements
                                gives: "
            << endl << "     ";
       copy(v1.begin(), v1.end(),
            ostream_iterator<int,char>(cout," "));
       cout << endl;
       //
       // A vector of ten elements.
       //
       vector<int> v2(10, 0);
       //
       // Sort the last ten elements in v1 into v2.
       //
       partial_sort_copy(v1.begin()+10, v1.end(), v2.begin(),
                         v2.end());
       //
       // Output result.
       //
       cout << endl << "A partial_sort_copy of the last ten
             elements gives: "
            << endl << "     ";
       copy(v2.begin(), v2.end(),
            ostream_iterator<int,char>(cout," "));
       cout << endl;

       return 0;
     }

Program Output

    For the vector: 17 3 5 -4 1 12 -10 -1 14 7 -6 8 15 -11 2 -2 18 4 -3 0
    A partial_sort of seven elements gives:
         -11 -10 -6 -4 -3 -2 -1 17 14 12 7 8 15 5 3 2 18 4 1 0
    A partial_sort_copy of the last ten elements gives:
         0 1 2 3 4 5 7 8 15 18

### Warnings

If your compiler does not support default template parameters, then you always need to include the `Allocator` template argument. For instance, you need to write:

`vector<int, allocator<int> >`

instead of:

`vector<int>`

If your compiler does not support namespaces, then you do not need the using declaration for `std`.

### See Also

sort, stable_sort, partial_sort_copy

Copyright (c) 1998, Rogue Wave Software, Inc.
Send mail to report errors or comment on the documentation.
OEM Release, June 1998