Grade 9 · Sorting and searchingCitește în română

Sorting with std::sort

Original: Sortarea cu std::sort

O(n log n)C++1749 lines1 example

The idea

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.

Original description (Romanian)

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.

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

Examples

Example 1

Input

5
3 1 4 1 5

Expected output

1 1 3 4 5
5 4 3 1 1

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

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;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.