PermSort

#include <iostream>

using namespace std;

// Проверка: отсортирован ли массив
bool issorted(int* list, int len)
{
    for (int j = 0; j < len - 1; j++)
    {
        if (list[j] > list[j + 1])
        {
            return false;
        }
    }
    return true;
}

bool PermutationSort(int* list, int i, int len)
{
    if (issorted(list, len)) // Проверяем отсортирован ли массив,
    {
        return true; // если да, то запускается механизм возврата из рекурсии
    }
    if (i >= len) // На всякий случай, потому что в теории такой ситуации быть не может
    {
        return false;
    }
    for (int j = 0; j < len; j++)
    {
        for (int k = j + 1; k < len; k++)
        {
            swap(list[j], list[k]); // Перестановка
            if (PermutationSort(list, i + 1, len))
            {
                return true; // Механизм возврата из рекурсии
            }
            swap(list[j], list[k]); // Возвращаем обратно
        }
    }
    return false;
}

int main()
{
    int count;
    cin >> count; // Вводим кол-во элементов
    int* a = new int[count];
    for (int i = 0; i < count; i++) { // Вводим значения элементов
        cin >> a[i];
    }
    PermutationSort(a, 0, count); // Сортируем
    for (int i = 0; i < count; i++) { // Выводим отсортированный массив
        cout << a[i] << " ";
    }
}