TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

C++ algorithm partial_sort() function

C++ algorithm partial_sort() function with c++ tutorial for beginners and professionals with examples on adjacent_find(),any_of(), copy(), copy_if(), count(), count_if(), equal(), find(), find_end(), find_first_of(), find_if(), find_if_not(), for_each() etc.

<< Back to CPP

C++ Algorithm partial_sort()

C++ Algorithm partial_sort() function is used to rearrange the elements in the range[first, last), in such a way that the elements between the first and middle will be sorted and the elements between the middle and last will be in an unspecified order.

The elements are compared using operator < for the first version, and comp for the second 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

first: A random access iterator pointing to the first element in the range to be partially sorted.

last: A random access iterator pointing to the past last element in the range to be partially sorted.

middle: A random access iterator pointing to the one past the final element in the sub-range to be sorted.

comp: A user-defined binary predicate function that accepts two arguments and returns true if the two arguments are in order and false otherwise. It follows the strict weak ordering to order the elements.

Return value

None

Complexity

Average Complexity is less than linearithmic in the distance between first and last. Performs up to N*log (M) element comparisons where N = last - first and M = middle - first.

Data races

The objects in the range [first, last) are altered.

Exceptions

This function throws an exception if any of element comparisons, the element swaps (or moves) or an operation on iterator throws an exception.

Note: The invalid parameters cause an undefined behavior.

Example 1

Let's see the simple example to demonstrate the use 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 see a simple example for 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  }

Next TopicC++ Algorithm




Related Links:

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf