// dllbridge@gmail.com
// 2021_December_08
// Bubble_sorting  &  comb_sorting

#include   <stdio.h>

int arr[99] =  { 17, 5, 0, 777, 11, -2, 198, -3, 7, 3 };        //  Этот массив требуется сортировать по возрастанию

int       length = 10,                                                                //  Кол-во элементов в массиве
     swap_counter = 0;                            //                    Суммарное число перестановок, при сортировке

void bubble_sorting(int *a, int size);            //                                            Сортировка пузырьком
void   comb_sorting(int *a, int size);
void           show(int *a, int size);            //                             Показать на экране элементы массива
void           swap(int &a, int   &b);            //                       Меняет местами содержимое двух переменных
int   chek_res_sort(int *a, int size);            //      Возвращает TRUE, если отсортировано верно. FALSE, если нет.
//                           Точка входа в программу
////////////////////////////////////////////////////
int main()                                        //
{

    show(arr, length);

    comb_sorting(arr, length);
    //bubble_sorting(arr, length);
    printf("- - - - - - - - - - - - - - - - - - - - - - -   \n");
    printf("In the sorting process, it took %d permutations.\n", swap_counter);
    if(chek_res_sort(arr, length) ) printf("Checked. The numbers are strictly ascending."      );
    else                            printf("Mistake! The values in the array are out of order.");

return 0;
}

//                              Сортировка "Расчёска"
/////////////////////////////////////////////////////
void comb_sorting(int *a,                          //                                Передаёте адрес элемента массива,
                                                   //              с которого начинаете упорядочивание по возрастанию.
                  int size)                        //       И передаёте кол-во элементов, которые будут отсортированы.
{

     int step = size - 1;

     while(step >= 1)
     {

         for(int i = 0; i + step < size; i++)
         {

             if(a[i] > a[i+step])
             {
                swap(a[i], a[i+step]);
                show( arr, length);                 //                                       Эта строка необязательна
             }                                      //                         Нужна для отслеживания хода сортировки
         }

         step /= 1.2473309;
     }
}


//                               Сортировка пузырьком
/////////////////////////////////////////////////////
void bubble_sorting(int *a,                        //                                Передаёте адрес элемента массива,
                                                   //              с которого начинаете упорядочивание по возрастанию.
                    int size)                      //       И передаёте кол-во элементов, которые будут отсортированы.
{

     int    i,                //  Счётчик в цикле  //
         Flag;              //  флаг перестановки  //

     do { Flag = 0;

          for(i = 0; i < size - 1; i++)
          {
             if(a[i] > a[i+1])
             {
                swap(a[i], a[i+1]);

                show(arr, length);                 //                                       Эта строка необязательна
                                                   //                         Нужна для отслеживания хода сортировки
                Flag = 1;                          //                     Была перестановка. Значит цикл продолжится
             }
          }
          printf("\n");

     } while(Flag == 1);                           //                          Если (Flag == 1), то цикл повторяется
}

//                Показать на экране элементы массива
/////////////////////////////////////////////////////
void show(int *a, int size)                        //
{
     int i = 0;

     for(; i < size; i++) printf("%2d, ", a[i]);

     printf("\n");
}


//           Меняет местами содержимое двух переменных
//////////////////////////////////////////////////////
void swap(int &a, int &b)                           //
{

     int buf = a;
     a = b;
     b = buf;

     swap_counter ++;                               //                                    Ещё одна (+1) перестановка
}



//            Проверка правильности сортировки массива
//////////////////////////////////////////////////////
int chek_res_sort(int *a,                           //                                        Передаёте адрес массива,
                                                    //                          который был упорядочен по возрастанию.
                  int size)                         //          И передаёте кол-во элементов, которые нужно проверить.
{

    for(int i = 0; i < size - 1; i++)
    {

        if(a[i] > a[i+1]) return 0;
    }

return 1;
}