Sortings - 1

Covered in this section:

• Sorting
• C++ STL related to sorting
• Special sorting problems

Sorting algorithms are well known and hence the most efficient way to sort will be to use pre built extremely efficient modules present in C++ stl.

Ascending sort on vector "v":

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

Descending sort on vector "v":

    sort(v.rbegin(),v.rend());
    

But when you need to sort based on certain properties, we use comparative functions in conjunction with sort(), like the one used with priority_queue in Introduction section.

    sort(v.rbegin(),v.rend(), cmp);
    

Special sorting problems

Inversion Index

For this we need to learn merge sort first. GFG has a very good article on merge sort and this GFG article goes in depth on what this problem is and how to tackle it.

counting sort

This is a special case o(1) sorting method. Used when range of numbers is not large. This YT video tells us how counting sort works.