Проверка отсортированности массива

Question

Сама программа верная, мне нужно оптимизировать её.

#include <iostream>

using namespace std;

int main()
{
    int n, t, q, x, y;
    bool ans;
    cin >> n >> q;
    int a[n], b[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i]; 
        b[i] = a[i];
    }
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (a[j] > a[j+1])
            {
                t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }
    for (int i = 0; i < q; i++)
    {
        cin >> x >> y;
        ans = true;
        x = x - 1;
        y = y - 1;
        t = b[x];
        b[x] = b[y];
        b[y] = t;
        for (int j = 0; j < n; j++)
        {
            if (a[j] != b[j])
            {
                ans = false;
                break;
            }
        }
        if (ans == true)
        {
            cout << "Sorted!" << "\n";
        }
        else
        {
            cout << "Unsorted!" << "\n";
        }
    }
}

Пример ввода/вывода:

Sample Input 1:

5 4
1 2 5 3 4
3 4
4 5
1 5
5 1

Sample Output 1:

Unsorted!
Sorted!
Unsorted!
Sorted!

Sample Input 2:

2 3
2 10
1 2
1 2
1 2

Sample Output 2:

Unsorted!
Sorted!
Unsorted!

Answer 1

Для начала рекомендую вам прочитать где-нибудь о вычислительной сложности алгоритмов и о нотации О-большое. Если полностью огрубить, то высказывание "Программа имеет сложность O(n^2)" означает, что при количестве входных данных n программа произведет примерно n^2 элементарных операций. Вы можете считать, что C++ может произвести около 200 миллионов операций в секунду.

Ваша программа имеет именно такую вычислительную сложность. Поэтому на самых неприятных для вас тестах ваша программа должна будет совершить порядка 10^10 операций, что может быть обработано компьютером примерно за минуту, но никак не за требуемую секунду.

Существуют два конкретных места, которые сильно тормозят вашу программу:

Ваша самописная сортировка
Сам алгоритм обработки запросов

Первую проблему решить просто: либо напишите более быструю сортировку (собственно, quick sort или merge sort), либо используйте встроенные методы (что я вам очень сильно рекомендую):

#include "algorithm"

sort(begin(a), end(a));
// Или если точнее, то sort(begin(a), begin(a) + n)
// Потому что иначе будут отсортированы все числа в массиве, включая мусорные после n

(Кстати, рекомендую вам познакомиться со структурой std::vector).

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

Мой вариант решения - использовать счетчик количества элементов, которые стоят "на своих местах". То есть если какой-то b[i] == a[i], где a - отсортированный массив, то данный элемент стоит на своем месте, иначе нет. Из данного определения очевидным образом вытекает условие отсортированности массива - счетчик равен N (все элементы на своих местах). Также работая с счетчиком, легко производить операции обмена: если элемент убрали со своего места, то от счетчика нужно отнять единицу, а если он попал на свое место, то прибавить.

Тогда ваш код превращается во что-то подобное:

#include <iostream>
#include "algorithm"

using namespace std;

const int MAXN = 1e5 + 2;
int a[MAXN], b[MAXN];

int main()
{
    int n, q;
    cin >> n >> q;

    for (int i = 0; i < n; i++) 
    { 
        cin >> a[i]; 
        b[i] = a[i]; 
    }

    // Сортировка массива a встроенной функцией
    sort(begin(a), begin(a) + n);

    // Вычисление изначального значения счетчика
    int counter = 0;
    for (int i = 0; i < n; i++)
        if (b[i] == a[i])
            counter++;

    for (int i = 0; i < q; i++) 
    {
        int x, y;
        cin >> x >> y; 
        x--; y--;

        // Изменение значения счетчика после операции обмена
        if (b[x] == a[x])
            counter--;
        if (b[x] == a[y])
            counter++;
        if (b[y] == a[y])
            counter--;
        if (b[y] == a[x])
            counter++;
       
        swap(b[x], b[y]);

        if (counter == n) 
            cout << "Sorted!" << "\n"; 
        else 
            cout << "Unsorted!" << "\n"; 
    }

    return 0;
}

Answer 2

Без использования дополнительного массива и сортировки, алгоритм линейный:

При вводе определяем число упорядоченных пар (a[i]>=a[i-1])

При каждом обмене достаточно узнать, насколько изменилось число упорядоченных пар, проверяя только 4 или 3 (для случая соседних индексов) пары там, где был обмен. Когда это число достигает длины входных данных - массив отсортирован.

Пруф на Python

БЛОГ НА HUSL

Проверка отсортированности массива

Ответы (2 шт):