• Choose a category
• All
• Classic-Fiction

Once you have sorted the elements in a range, you can apply the binary_search() algorithm to find elements in logarithmic instead of linear time. It requires a start and end iterator specifying the range, a value to search, and optionally a comparison callback. It returns true if the value is found in the specified range, false otherwise.

The merge() function allows you to merge two sorted ranges together, while maintaining the sorted order. The result is a sorted range containing all the elements of the two source ranges. It works in linear time. The following parameters are required:

start and end iterator of first source range

start and end iterator of second source range

start iterator of destination range

optionally, a comparison callback

Without merge(), you could still achieve the same effect by concatenating the two ranges and applying sort() to the result, but that would be less efficient [O(N log N) instead of linear].

Always ensure that you supply a big enough destination range to store the result of the merge!

Here is an example of sorting and merging:

// The populateContainer() function is identical to the one shown earlier

// for comparison algorithms, so it is omitted here.

vector vectorOne, vectorTwo, vectorMerged;

cout << "Enter values for first vector:" << endl;

populateContainer(vectorOne);

cout << "Enter values for second vector:" << endl;

populateContainer(vectorTwo);

// Sort both containers

sort(vectorOne.begin(), vectorOne.end());

sort(vectorTwo.begin(), vectorTwo.end());

// Make sure the destination vector is large enough to hold the values

// from both source vectors.

vectorMerged.resize(vectorOne.size() + vectorTwo.size());

merge(vectorOne.cbegin(), vectorOne.cend(), vectorTwo.cbegin(),

vectorTwo.cend(), vectorMerged.begin());

cout << "Merged vector: ";

for_each(vectorMerged.cbegin(), vectorMerged.cend(),

[](int i){cout << i << " ";});

cout << endl;

while (true) {

int num;

cout << "Enter a number to find (0 to quit): ";

cin >> num;

if (num == 0) {

break;

}

if (binary_search(vectorMerged.cbegin(), vectorMerged.cend(), num)) {

cout << "That number is in the vector." << endl;

} else {

cout << "That number is not in the vector." << endl;

}

}

Code snippet from SortingAlgorithms\SortingAndMerging.cpp

Other Sorting Algorithms

If you need to write your own sort algorithm, which is unlikely, there are several sorting routines that can be used as building blocks, including partition(), partition_copy() (C++11), partial_sort(), partial_sort_copy() (C++11), and nth_element(). C++11 also introduces is_sorted() and is_sorted_until() algorithms; is_sorted() returns true if the given range is sorted, while is_sorted_until() returns an iterator in the given range such that everything before this iterator is sorted. However, writing your own sort algorithm is a very exotic problem domain not usually operated in, and therefore we do not discuss these further.

The Standard Library Reference resource on the website contains the details in case the need arises to use one of these algorithms.

random_shuffle

The final “sorting” algorithm is technically more of an “anti-sorting” algorithm; random_shuffle() rearranges the elements of a range in a random order with a linear complexity. It’s useful for implementing tasks like shuffling a deck of cards. There are two versions of random_shuffle(). The first version requires a start and end iterator for the range that you want to shuffle. For this version, the C++ standard does not define which random number generator the implementation has to use. Most compilers use rand() from the standard C library. Note that this requires you to seed the random number generator using srand(). The second version of random_shuffle() requires a start and end iterator for the range to shuffle and also accepts a third parameter which is a random number generator object that can be specified to adapt the randomness to suit your problem domain, for example uniform distribution,