Kwwiker

PermSort

Dec 11th, 2020
673
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. // Проверка: отсортирован ли массив
  6. bool issorted(int* list, int len)
  7. {
  8.     for (int j = 0; j < len - 1; j++)
  9.     {
  10.         if (list[j] > list[j + 1])
  11.         {
  12.             return false;
  13.         }
  14.     }
  15.     return true;
  16. }
  17.  
  18. bool PermutationSort(int* list, int i, int len)
  19. {
  20.     if (issorted(list, len)) // Проверяем отсортирован ли массив,
  21.     {
  22.         return true; // если да, то запускается механизм возврата из рекурсии
  23.     }
  24.     if (i >= len) // На всякий случай, потому что в теории такой ситуации быть не может
  25.     {
  26.         return false;
  27.     }
  28.     for (int j = 0; j < len; j++)
  29.     {
  30.         for (int k = j + 1; k < len; k++)
  31.         {
  32.             swap(list[j], list[k]); // Перестановка
  33.             if (PermutationSort(list, i + 1, len))
  34.             {
  35.                 return true; // Механизм возврата из рекурсии
  36.             }
  37.             swap(list[j], list[k]); // Возвращаем обратно
  38.         }
  39.     }
  40.     return false;
  41. }
  42.  
  43. int main()
  44. {
  45.     int count;
  46.     cin >> count; // Вводим кол-во элементов
  47.     int* a = new int[count];
  48.     for (int i = 0; i < count; i++) { // Вводим значения элементов
  49.         cin >> a[i];
  50.     }
  51.     PermutationSort(a, 0, count); // Сортируем
  52.     for (int i = 0; i < count; i++) { // Выводим отсортированный массив
  53.         cout << a[i] << " ";
  54.     }
  55. }
RAW Paste Data