C++ Tutorials

C++ Tutorials

Sorting a vector in C++. we will discuss how to sort a vector of integers in C++ in ascending order.

C++ tutorial for sort(). We are going to see the basic use of sort() as well as some other things we can do with it. Lets say we want to sort this array of integers in ascending order.

So all we need to do is use this sort() function available in algorithm header file. You can see, Now the array is sorted. Let’s say we wanted this array to be sorted in descending order instead of ascending order.

We can either reverse the (sorted) array or we can sort the array in descending order to begin with. We can do so by passing a* boolean function that checks if that elements are in descending order as argument for sort function.

Or even better we can pass this argument (greater()) which is already present in c++ library. So we can do a lots of crazy things using this boolean function. Let’s say I wanted my array to be sorted according to the digit in one’s place.

For that, I can do something like this. As You can see this sorted my array as I wanted. What if I wanted, my array to be sorted lexicographically. It is a sorting method used for making dictionaries. for example, ab comes before b in a dictionary.

Similarly, 12 will come before 2 even though twelve is greater than two For this type of sorting we can use the array of string instead of an array of integers. This will work with all the alpha-numeric characters.

Sort Vector C++ Descending

Given an array how to sort all even numbers in ascending order and odd numbers in descending order. Here’s the problem, given an integer array we need to sort all the odd integers in decreasing order first and then all the even integers in increasing order.

Let’s look at examples for this problem, if this is the input array, then we can see that the descending order of odd numbers is 7,5,3,1 and ascending order of even numbers is 2,4,10.

So, the output is this. Similarly for the second case, we will get this as output The first method to solve this problem is to move all odd numbers to the left and even numbers to the right. After this, we individually sort the left and right parts.

Here is an implementation of the given problem in C++. We keep 2 integers for left and right extremities. Then iterate and partition the odd and even numbers.

At last, we sort the odd numbers in descending order and even numbers in ascending order. Let’s look at another solution to this problem, we multiply all the odd numbers with -1 and then sort the entire array.

At last, we revert back to the changes made in step 1. Here’s the implementation for this problem. We first multiply all the odd numbers with -1. Then sort then entire array and atlast revert back the normal array. The time complexity for both the solutions is O(n log n).

Sort Vector of Strings C++

This is C++, not C. Sorting an array of strings is easy.

#include <string>
#include <vector>
#include <algorithm>

std::vector<std::string> stringarray;
std::sort(stringarray.begin(), stringarray.end());

Sort Vector of Vector C++

Sort a string vector. Actually, the vector is being sorted if all the strings start with the a capital/lower letter.

Sure it is. std::sort can take a third parameter which is the comparison function to use when sorting. For example, you could use a lambda function:

std::vector<std::vector<int>> vec;
// Fill it

std::sort(vec.begin(), vec.end(),
          [](const std::vector<int>& a, const std::vector<int>& b) {
  return a[2] < b[2];
});

Alternatively, you can pass anything else callable with signature bool(const std::vector<int>&, const std::vector<int>&), such as a functor or function pointer.


Response to edit: Simply apply your COST function to a and b:

std::sort(vec.begin(), vec.end(),
          [](const std::vector<int>& a, const std::vector<int>& b) {
  return COST(a) < COST(b);
});

Quick Sort Vector C++

  1. Always pick the first element as pivot.
  2. Always pick the last element as the pivot (implemented below)
  3. Pick a random element as a pivot.
  4. Pick median as a pivot.
#include <vector>
using namespace std;
void swap(vector<int>& v, int x, int y);

void quicksort(vector<int> &vec, int L, int R) {
    int i, j, mid, piv;
    i = L;
    j = R;
    mid = L + (R - L) / 2;
    piv = vec[mid];

    while (i<R || j>L) {
        while (vec[i] < piv)
            i++;
        while (vec[j] > piv)
            j--;

        if (i <= j) {
            swap(vec, i, j); //error=swap function doesnt take 3 arguments
            i++;
            j--;
        }
        else {
            if (i < R)
                quicksort(vec, i, R);
            if (j > L)
                quicksort(vec, L, j);
            return;
        }
    }
}

void swap(vector<int>& v, int x, int y) {
    int temp = v[x];
    v[x] = v[y];
    v[y] = temp;

}

int main() {
    vector<int> vec1;
    const int count = 10;

    for (int i = 0; i < count; i++) {
        vec1.push_back(1 + rand() % 100);
    }
    quicksort(vec1, 0, count - 1);

}

C++ Sort Vector of Objects

I would overload operator < and then sort using greater. Greater essentially means rhs < lhs. You then sort using sort(listOfPeople.begin(), listOfPeople.end(), greater<Information>());

If you decide to add operator< your class would play nicely with std::set and as a key in std::map in addition to allowing sort.

class Information {

private:
int age;
string name;

friend bool operator< (Information const& lhs, Information const& rhs){
    return lhs.age < rhs.age;
}
};

Sort Array C++

Learn about searching and sorting in an array. First let’s learn sorting. We do not need to write our own sort function for this. C++ comes with function to do so.

To sort an array we use the sort function which is present the algorithm library. The sort function takes 2 parameters, starting address and ending address of the array to be sorted.

Here, we have an array of length 10 and we are sorting the first 6 indices of this array using this statement. Let’s run this code, we can see that the first 6 elements of the array are sorted.

To sort the complete array, we just need to write the array name s starting index and ending index as starting index + length of the array. Let’s run this code again, we can see that the entire array is sorted.

We know that, we can search in a sorted array using binary search in O(log n).1 C++ has a function binary_search for searching. Binary_search takes 3 arguments, starting address, ending address and the value to be searched.

Let’s suppose we need to search for 7 in this array in the entire array. We can do it by writing binary_search (array name, arrayname + size, 7), let’s search for 8, 9 and 10 too like this. Let’s run this code, we can see that 7 and 8 are present in the array but 9 and 10 are not.