Sort, Binary Search, Merge Algorithms

Sort And Partial Sort

You can sort a range with std::sort or std::stable_sort or sort until a position with std::partial_sort. In addition std::partial_sort_copy copies the partially sorted range. With std::nth_element you can assign an element the sorted position in the range. You can check with std::is_sorted if a range is sorted. If you want to know until which position a range is sorted, use std::is_sorted_until.

std::string str{"RUdAjdDkaACsdfjwldXmnEiVSEZTiepfgOIkue"};
std::cout << std::is_sorted(str.begin(), str.end());        // false

std::partial_sort(str.begin(), str.begin()+30, str.end());
std::cout << str;           // AACDEEIORSTUVXZaddddeeffgiijjkwspnmluk

auto sortUntil= std::is_sorted_until(str.begin(), str.end());
std::cout << *sortUntil;                                   // s
for (auto charIt= str.begin(); charIt != sortUntil; ++charIt) 
    std::cout << *charIt;           // AACDEEIORSTUVXZaddddeeffgiijjkw

std::vector<int> vec{1, 0, 4, 3, 5};
auto vecIt= vec.begin();
while(vecIt != vec.end()){
  std::nth_element(vec.begin(), vecIt++, vec.end());
  std::cout << std::distance(vec.begin(), vecIt) << "-th ";
  for (auto v: vec) std::cout << v << "/";
}
// 1-th 01435/2-th 01435/3-th 10345/4-th 30145/5-th 10345

struct A{
    int v;
    bool operator<(const A& other){
        return this->v<other.v;
    }
};
int main(int argc, char *argv[])
{
    QCoreApplication a(argc,argv);
    QList<A> list{{8},{2},{3},{6},{5}};
    sort(list.begin(),list.end());
    for(const A& a:list){
        qDebug()<<a.v;
    }//2 3 5 6 8
    return a.exec();
}

Binary Search

The binary search algorithms use the fact that the ranges are already sorted. To search for an element, use std::binary_search. With std::lower_bound you get an iterator for the first element, being no smaller than the given value. With std::upper_bound you get an iterator back for the first element, which is bigger than the given value. std:::equal_range combines both algorithms.

binary_search : Searches the element val in the range
lower_bound : Returns the position of the first element of the range, being not smaller than val
upper_bound : Returns the position of the first element of the range, being bigger than val
equal_range : Returns the pair std::lower_bound and std::upper_bound for the element val

bool isLessAbs(int a, int b){
  return abs(a) < abs(b);
}
vector<int> vec{-3, 0, -3, 2, -3, 5, -3, 7, -0, 6, -3, 5, 
                -6, 8, 9, 0, 8, 7, -7, 8, 9, -6, 3, -3, 2};

sort(vec.begin(), vec.end(), isLessAbs);
for (auto v: vec) cout << v << " "; 
     // 0 0 0 2 2 -3 -3 -3 -3 -3 3 -3 5 5 -6 -6 6 7 -7 7 8 8 8 9 9
cout << binary_search(vec.begin(), vec.end(), -5, isLessAbs); // true
cout << binary_search(vec.begin(), vec.end(), 5, isLessAbs);  // true

auto pair= equal_range(vec.begin(), vec.end(), 3, isLessAbs);
cout << distance(vec.begin(), pair.first);                    // 5
cout << distance(vec.begin(), pair.second)-1;                 // 11

for (auto threeIt= pair.first;threeIt != pair.second; ++threeIt) 
     cout << *threeIt << " ";              // -3 -3 -3 -3 -3 3 -3

Merge Operation

Merge operations empower you to merge sorted ranges in a new sorted range. The algorithm requires that the ranges and the algorithm use the same sorting criterion. If not, the program is undefined. Per default the predefined sorting criterion std::less is used. If you use your sorting criterion, it has to obey the strict weak ordering. If not, the program is undefined.

You can merge two sorted ranges with std::inplace_merge and std::merge. You can check with std::includes if one sorted range is in another sorted range. You can merge with std::set_difference, std::set_intersection, std::set_symmetric_difference and std::set_union two sorted ranges in a new sorted range.

inplace_merge : Merges in place two sorted sub ranges [first, mid) and [mid, last)
merge : Merges two sorted ranges and copies the result to result
includes: Checks if all elements of the second range are in the first range
set_difference : Copies these elements of the first range to result, being not in the second range
set_intersection : Determines the intersection of the first with the second range and copies the result to result
set_symmetric_difference : Determines the symmetric difference of the first with the second range and copies the result to result
set_union : Determines the union of the first with the second range and copies the result to result

std::vector<int> vec1{1, 1, 4, 3, 5, 8, 6, 7, 9, 2};
std::vector<int> vec2{1, 2, 3};

std::sort(vec1.begin(), vec1.end());
std::vector<int> vec(vec1);

vec1.reserve(vec1.size() + vec2.size());
vec1.insert(vec1.end(), vec2.begin(), vec2.end());
for (auto v: vec1) std::cout << v << " ";       // 1 1 2 3 4 5 6 7 8 9 1 2 3

std::inplace_merge(vec1.begin(), vec1.end()-vec2.size(), vec1.end());
for (auto v: vec1) std::cout << v << " ";       //  1 1 1 2 2 3 3 4 5 6 7 8 9

vec2.push_back(10);
for (auto v: vec) std::cout << v << " ";        // 1 1 2 3 4 5 6 7 8 9
for (auto v: vec2) std::cout << v << " ";       // 1 2 3 10

std::vector<int> res;
std::set_symmetric_difference(vec.begin(), vec.end(), vec2.begin(), vec2.end(), 
                              std::back_inserter(res));
for (auto v : res) std::cout << v << " ";       // 1 4 5 6 7 8 9 10

res= {};
std::set_union(vec.begin(), vec.end(), vec2.begin(), vec2.end(),
std::back_inserter(res));
for (auto v : res) std::cout << v << " ";       // 1 1 2 3 4 5 6 7 8 9 10