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

Sorting by two criteria

Original: Sortarea după două criterii

O(n²)C++1752 lines1 example

The idea

We order the numbers increasingly by their last digit, and numbers with the same last digit decreasingly by value. The sorting algorithm stays the same (here we compare every v[i] with all v[j] after it); only the condition that says when two elements are in the wrong order changes: a larger last digit, or the same last digit and a smaller value.

Original description (Romanian)

Ordonăm numerele crescător după ultima cifră, iar numerele cu aceeași ultimă cifră descrescător după valoare. Algoritmul de sortare rămâne același (aici comparăm fiecare v[i] cu toate v[j] de după el); se schimbă doar condiția care spune când două elemente sunt în ordine greșită: ultima cifră mai mare, sau aceeași ultimă cifră și valoare mai mică.

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

Examples

Example 1

Input

7
31 20 41 12 5 15 70

Expected output

70 20 41 31 12 15 5

The code

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

sortare-dupa-doua-criterii.cpp
/*
 * Titlu: Sortarea după două criterii
 * Clasa: 9
 * Capitol: Sortare și căutare
 * Descriere: Ordonăm numerele crescător după ultima cifră, iar numerele cu
 *            aceeași ultimă cifră descrescător după valoare. Algoritmul de
 *            sortare rămâne același (aici comparăm fiecare v[i] cu toate v[j] de
 *            după el); se schimbă doar condiția care spune când două elemente sunt în
 *            ordine greșită: ultima cifră mai mare, sau aceeași ultimă cifră și
 *            valoare mai mică.
 * Complexitate: O(n²)
 *
 * Exemplu
 * Intrare:
 * 7
 * 31 20 41 12 5 15 70
 * Ieșire: 70 20 41 31 12 15 5
 */
#include <iostream>
using namespace std;

int v[1001];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            int ci = v[i] % 10, cj = v[j] % 10;
            if (ci > cj || (ci == cj && v[i] < v[j]))
            {
                int aux = v[i];
                v[i] = v[j];
                v[j] = aux;
            }
        }
    }
    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.