Сортировка в C++

В С++ существует встроенный алгоритм сортировки sort (библиотека algorithm.h). Как же ею пользоваться?

Задача 1. Сортировка целочисленного массива А[n] по возрастанию:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int A[n];
    for (int i=0; i<n; i++)
        cin >> A[i];

    sort (A,A+n);

    for (int i=0; i<n; i++)
        cout<<A[i]<<" ";
    return 0;
}
В самой функции sort нужно указывать указатель на начало массива и на конец. Так как имя массива в С++ хранит адрес начала массива, то логично, что переход на конец массива - это сдвиг на n адресов, т.е. A+n.

Задача 2. Сортировка вещественного массива А[n] по убыванию:

#include <iostream>
#include <algorithm>

using namespace std;
bool comp(float a, float b)
{
    if (a>b) return true;
    else return false;
}
int main()
{
    int n;
    cin >> n;
    float A[n];
    for (int i=0; i<n; i++)
        cin >> A[i];

    sort (A,A+n,comp);

    for (int i=0; i<n; i++)
        cout<<A[i]<<" ";
    return 0;
}

Чтобы отсортировать в обратном порядке, нужно этого порядка придерживаться, т.е. добиться того, чтобы первый в паре элемент был больше второго. Для этого введем логическую функцию bool comp(float a, float b), где это условие и пропишем. Само название функции надо добавить в список sort (A,A+n,comp). Если необходимо поменять следование элементов по возрастанию, то в функции comp просто поменяйте знак больше на меньше. Другой вариант записи функции

bool comp(float a, float b)
{
    return (a>b)? 1 : 0;
}

Теперь легко написать решение следующей задачи:
Задача 3. Сортировка строкового массива А[n] по возрастанию:

#include <iostream>
#include <algorithm>

using namespace std;
bool comp(string a, string b)
{
    if (a<b) return true;
    else return false;
}
int main()
{
    int n;
    cin >> n;
    string A[n];
    for (int i=0; i<n; i++)
        cin >> A[i];
        
    sort (A,A+n,comp);
    
    for (int i=0; i<n; i++)
        cout<<A[i]<<" ";
    return 0;
}

Задача 4. Сортировка массива А[n] записей по двум и более критериям. Например, записи о среднем балле учеников по классам, необходимо отсортировать по классам в порядке возрастания, по баллам в порядке убывания, а если баллы совпадают, то по фамилиям в алфавитном порядке:

#include <iostream>
#include <algorithm>

using namespace std;
struct TStudent{
    string fio;
    int nomer_class;
    int ball;
};

bool comp(TStudent a, TStudent b)
{
    if (a.nomer_class < b.nomer_class ||
        a.nomer_class==b.nomer_class && a.ball>b.ball ||
        a.nomer_class==b.nomer_class && a.ball==b.ball && a.fio<=b.fio)
    return true;
    else return false;
}
int main()
{
    int n;
    cin >> n;
    TStudent A[n];
    for (int i=0; i<n; i++)
        cin >> A[i].fio >> A[i].nomer_class >> A[i].ball;

    sort (A,A+n,comp);

    for (int i=0; i<n; i++)
        cout<<A[i].nomer_class<<" "<< A[i].fio<<" "<<A[i].ball<<endl;
    return 0;
}

Задача 5. Сортировка динамического массива А[n], заданного как вектор:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef vector<char> Tc;//дадим имя динамическому массиву 

bool comp(char a, char b)
{
   return (a>b)?1:0;
}

int main()
{
    Tc A;
    char c;
    cin>>c;
    while (c!='.')//ввод символов до точки.
    {
       A.push_back(c);
       cin>>c;
    }

    sort (A.begin(),A.end());//по возрастанию

    for (int i=0; i<A.size(); i++)
        cout<<A[i]<<" ";
    cout<<endl;

    sort (A.begin(),A.end(),comp);//по убыванию

    for (int i=0; i<A.size(); i++)
        cout<<A[i]<<" ";

    return 0;
}

Для указателя начала и конца массива используются функции begin() и end(). В функции comp параметром ставим тот тип, который указан как в типе vector.

Задача 6. Сортировка первой половины целочисленного массива А[n] по возрастанию, а второй половины - по убыванию:

#include <iostream>
#include <algorithm>

using namespace std;
bool comp(int a, int b)
{
   return (a>b)?1:0;
}

int main()
{
    int n=10;
    int A[10]={1,5,0,8,9,1,3,4,2,7};
    
    sort (A,A+n/2);
    
    sort (A+n/2,A+n,comp);

    for (int i=0; i<n; i++)
        cout<<A[i]<<" ";

    return 0;
}

Упражнение:

1. Отсортируйте массив натуральных чисел по возрастанию последней цифры числа.
2. Отсортируйте массив записей, содержащих информацию о численности населения городов разных стран, по убыванию численности в каждой стране. Страны сортируем в порядке возрастания.

Еще одна задача. Даны n пар целых чисел. Вывести сначала все пары, в которых значения идут от меньшего к большему, затем те пары, в которых значения равны, и потом пары, в которых значения идут от большего к меньшему. В каждом блоке сортируем по возрастанию первого числа в паре.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

typedef pair<int, int>Tp;

typedef vector<Tp> Tc;

bool comp_l(Tp a, Tp b)

{

   if(a.first<=b.first && (a.first<a.second && b.first<b.second))

   return 1;

   else return 0;

}

bool comp_e(Tp a, Tp b)

{

   if(a.first<b.first && (a.first==a.second && b.first==b.second))

   return 1;

   else return 0;

}

bool comp_r(Tp a, Tp b)

{

   if(a.first<b.first && (a.first>a.second && b.first>b.second))

   return 1;

   else return 0;

}

int main()

{

    int n;

    cin >>n;

    Tc A, B, C;

    int a,b;

    for (int i=0; i<n; i++)

    {

        cin>>a>>b;

        if (a<b) A.push_back({a,b});

        if (a==b)B.push_back({a,b});

        if (a>b) C.push_back({a,b});

    }

    sort (A.begin(),A.end(),comp_l);

    sort (B.begin(),B.end(),comp_e);

    sort (C.begin(),C.end(),comp_r);

    for (int i=0; i<A.size(); i++)

        cout<<A[i].first<<" "<<A[i].second<<endl;

    for (int i=0; i<B.size(); i++)

        cout<<B[i].first<<" "<<B[i].second<<endl;

    for (int i=0; i<C.size(); i++)

        cout<<C[i].first<<" "<<C[i].second<<endl;

    return 0;

}