Clasa a IX-a · Sortare și căutareRead in English

Sortarea cu std::sort în C++

În engleză: Sorting with std::sort

O(n log n)C++1749 de linii1 exemplu

Ideea

Biblioteca <algorithm> are funcția sort, care ordonează în O(n log n). Primește începutul și sfârșitul zonei: pentru pozițiile 1..n scriem sort(v + 1, v + n + 1). Pentru ordine descrescătoare se adaugă al treilea argument greater<int>(). Se afișează vectorul sortat crescător, apoi descrescător.

Descrierea în engleză

The <algorithm> library has the sort function, which orders in O(n log n). It takes the start and the end of the range: for positions 1..n we write sort(v + 1, v + n + 1). For decreasing order we add the third argument greater<int>(). The array is printed sorted in increasing order, then in decreasing order.

Complexitate
O(n log n)
Clasa
Clasa a IX-a (Grade 9)

Exemple

Exemplul 1

Intrare

5
3 1 4 1 5

Ieșire așteptată

1 1 3 4 5
5 4 3 1 1

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

sortare-cu-std-sort.cpp
/*
 * Titlu: Sortarea cu std::sort
 * Clasa: 9
 * Capitol: Sortare și căutare
 * Descriere: Biblioteca <algorithm> are funcția sort, care ordonează în
 *            O(n log n). Primește începutul și sfârșitul zonei: pentru pozițiile
 *            1..n scriem sort(v + 1, v + n + 1). Pentru ordine descrescătoare se
 *            adaugă al treilea argument greater<int>(). Se afișează vectorul
 *            sortat crescător, apoi descrescător.
 * Complexitate: O(n log n)
 *
 * Exemplu
 * Intrare:
 * 5
 * 3 1 4 1 5
 * Ieșire:
 * 1 1 3 4 5
 * 5 4 3 1 1
 */
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

int v[100001];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    sort(v + 1, v + n + 1);
    for (int i = 1; i <= n; i++)
    {
        cout << v[i] << ' ';
    }
    cout << '\n';
    sort(v + 1, v + n + 1, greater<int>());
    for (int i = 1; i <= n; i++)
    {
        cout << v[i] << ' ';
    }
    cout << '\n';
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.