The C++ function partial_sort is employed to reorganize the elements within the specified range [first, last). This operation ensures that the elements positioned between the first and middle are sorted, while the elements between the middle and last remain in an undetermined arrangement.
The elements are evaluated with the < operator in the initial version, and with comp in the subsequent version.
Syntax
default (1) template <class RandomAccessIterator>
void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,
RandomAccessIterator last);
custom (2) template <class RandomAccessIterator, class Compare>
void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,
RandomAccessIterator last, Compare comp);
Parameter
A random access iterator pointing to the initial element within the range intended for partial sorting.
last : A random access iterator indicating the element that comes after the last one to be included in the partial sorting process.
middle: A random access iterator indicating the element immediately after the last one in the specific sub-range intended for sorting.
A custom binary predicate function named comp is defined by the user. This function takes two arguments and evaluates to true if the two arguments are in a specific order, otherwise it returns false. It adheres to the strict weak ordering principle to arrange the elements.
Return value
Complexity
The average complexity remains below linearithmic based on the distance between the initial and final points. It conducts a maximum of N*log (M) comparisons of elements, where N equals the difference between the last and first elements, and M represents the distance between the middle and first elements.
Data races
The elements within the range [first, last) undergo modifications.
Exceptions
This function will raise an exception if any comparison between elements, the swapping or moving of elements, or any operation involving iterators triggers an exception.
Note: The invalid parameters cause an undefined behavior.
Example 1
Let's explore a basic illustration to showcase the functionality of partial_sort:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v = {3, 1, 4, 2, 5};
cout<<"Before sorting: ";
for_each(v.begin(), v.end(), [](int x) {
cout << x << " ";
});
partial_sort(v.begin(), v.begin() + 2, v.end());
cout<<"\nAfter sorting: ";
for_each(v.begin(), v.end(), [](int x) {
cout << x << " ";
});
return 0;
}
Output:
Before sorting: 3 1 4 2 5
After sorting: 1 2 4 3 5
Example 2
Let's see another simple example:
#include <iostream> // std::cout
#include <algorithm> // std::partial_sort
#include <vector> // std::vector
using namespace std;
bool myfunction (int i,int j) { return (i<j); }
int main () {
int myints[] = {9,8,7,6,5,4,3,2,1};
vector<int> myvector (myints, myints+9);
// using default comparison (operator <):
partial_sort (myvector.begin(), myvector.begin()+5, myvector.end());
// using function as comp
partial_sort (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);
// print out content:
cout << "myvector contains:";
for (vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
cout << ' ' << *it;
cout << '\n';
return 0;
}
Output:
myvector contains: 1 2 3 4 5 9 8 7 6
Example 3
Let's see a simple example for default version:
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std ;
int main()
{
const int VECTOR_SIZE = 8 ;
// Define a template class vector of int
typedef vector<int> IntVector ;
//Define an iterator for template class vector of strings
typedef IntVector::iterator IntVectorIt ;
IntVector Numbers(VECTOR_SIZE) ;
IntVectorIt start, end, it ;
// Initialize vector Numbers
Numbers[0] = 4 ;
Numbers[1] = 10;
Numbers[2] = 70 ;
Numbers[3] = 30 ;
Numbers[4] = 10;
Numbers[5] = 69 ;
Numbers[6] = 96 ;
Numbers[7] = 7;
start = Numbers.begin() ; // location of first
// element of Numbers
end = Numbers.end() ; // one past the location
// last element of Numbers
cout << "Before calling partial_sort\n" << endl ;
// print content of Numbers
cout << "Numbers { " ;
for(it = start; it != end; it++)
cout << *it << " " ;
cout << " }\n" << endl ;
// sort the smallest 4 elements in the sequence
partial_sort(start, start+4, end) ;
cout << "After calling partial_sort\n" << endl ;
cout << "Numbers { " ;
for(it = start; it != end; it++)
cout << *it << " " ;
cout << " }\n" << endl ;
return 0;
}
Output:
Before calling partial_sort
Numbers { 4 10 70 30 10 69 96 7 }
After calling partial_sort
Numbers { 4 7 10 10 70 69 96 30 }
Example 4
Let's examine a basic illustration for a custom (predicate) version:
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std ;
int main()
{
const int VECTOR_SIZE = 8 ;
// Define a template class vector of int
typedef vector<int> IntVector ;
//Define an iterator for template class vector of strings
typedef IntVector::iterator IntVectorIt ;
IntVector Numbers(VECTOR_SIZE) ;
IntVectorIt start, end, it ;
// Initialize vector Numbers
Numbers[0] = 4 ;
Numbers[1] = 10;
Numbers[2] = 70 ;
Numbers[3] = 30 ;
Numbers[4] = 10;
Numbers[5] = 69 ;
Numbers[6] = 96 ;
Numbers[7] = 7;
start = Numbers.begin() ; // location of first
// element of Numbers
end = Numbers.end() ; // one past the location
// last element of Numbers
cout << "Before calling partial_sort\n" << endl ;
// print content of Numbers
cout << "Numbers { " ;
for(it = start; it != end; it++)
cout << *it << " " ;
cout << " }\n" << endl ;
// sort the smallest 4 elements in the sequence
partial_sort(start, start+4, end, less<int>()) ;
cout << "After calling partial_sort\n" << endl ;
cout << "Numbers { " ;
for(it = start; it != end; it++)
cout << *it << " " ;
cout << " }\n" << endl ;
return 0;
}
Output:
Before calling partial_sort
Numbers { 4 10 70 30 10 69 96 7 }
After calling partial_sort
Numbers { 4 7 10 10 70 69 96 30 }
