Dahl-Programming-Lab11-16

#include <iostream>
#include <cstdlib>
using namespace std;

void fill_array(double* array, int size_of_array); // Prototype of function, which fill our array
void show_array(double* array, int size_of_array); // Prototype of function, which show our array
void show_array(double* array, int begin, int end); // Overweight for show_array
void show_array(int* array, int begin, int end); // Another overweight for show_array
void show_array(int* array, int size_of_array); // Yet another overweight for show_array
void sort_for_second(int* array, int size); // Prototype of function, which will sort array for second task

int main() {
    //Вариант 16
    // Задача 1. Упорядочить в порядке убывания модулей элементы, расположенные между пятым положительным и первым отрицательным
    // значениями массива.
    srand(time(0));

    // Variables
    int n, index_A = 0, index_B = n - 1 ;
    /*
     * Default Values:
     * n - amount of cells in array
     * index_A - index for first sorted element in array (Def: First Element)
     * index_B - index for last sorted element in array (Def: Last Element)
     * mid - middle index of array for qsort
     */
     cout << "Please, Enter amount of cells in the array: ";
     cin >> n; // Type amount of cells in our array
     auto *first_array = new double[n]; // New array for Qsort
     fill_array(first_array, n); // Fill our array
     show_array(first_array, n); // Show our array
     int positive = 0; // Amount of positive elements

    for (int i = 0; i < n; i++) { // Finding beginning of sorting
        if (first_array[i] > 0)
        {
            ++positive;
        }
        if (positive == 5)
        {
            index_A = i;
            break;
        }
    }

    for (int i = n-1; i > 0; i--) {
        // Finding the end of the sorting
        if (first_array[i] < 0)
        {
            index_B = i;
            break;
        }
    }

    show_array(first_array,index_A,index_B);


    if (index_A > index_B)
    {
        swap(index_A,index_B) ; // Swap values of end and beginning, if second greater than first
    }
    //! Creating new array, because old array must be filtrated from index_A to index_B
    int length_of_new_array = index_B - index_A; // Length from values from index_A to index_B
    auto *new_array = new double [length_of_new_array]; // New array with length index_A - index_B
    int index_transform = 0; // Index for translating cells from first array to the new array
    for (int i = index_A; i < index_B; i++)
    { // From old array to new array
        new_array[index_transform] = first_array[i]; //TODO Make normal transt_pointeronation from first array to new array
        index_transform++;
    }

    cout << "Showing new array: " << endl;
    show_array(new_array, length_of_new_array);

     /*
      * 1. Выбор опорного элемента из массива. (mid)
      * 2. Перераспределение элементов в массиве таким образом, что элементы меньше опорного помещаются перед ним,
      *    а больше или равные — после.
      * 3. Рекурсивное применение первых двух шагов к двум подмассивам слева и справа от опорного элемента.
      *    Рекурсия не применяется к массиву, в котором только один или отсутствуют элементы.
      */
     //qsort

     // Second step
    int * left_stack = new int[length_of_new_array], * right_stack = new int[length_of_new_array];

    int st_pointer = 1;
    right_stack[st_pointer] = length_of_new_array - 1;
    left_stack[st_pointer] = 0;

  while (st_pointer > 0)
  { // Выборка из стека последнего запроса
    int left = left_stack[st_pointer];
    int right = right_stack[st_pointer];
    st_pointer--;

    while (left < right)
    {
      int i = left, j = right; // 7
      float middle = new_array[(left + right) / 2];
      while (i < j)
      {
        while (new_array[i] < middle)
        {
          i++;
        }
        while (middle < new_array[j])
        {
          j--;
        }
        if (i <= j)
        {
          float temp = new_array[i];
          new_array[i] = new_array[j];
          new_array[j] = temp;
          i++; j--;
        }
      }

      if (i < right)
      {
        st_pointer++;
        left_stack[st_pointer] = i;
        right_stack[st_pointer] = right;
      }
      right = j; // Теперь left и right ограничивают левую часть
    }
  }
  cout << "Showing sorted array: " << endl;
  show_array(new_array,length_of_new_array);

    // Задача 2. Дана целочисленная квадратная матрица. Упорядочить по возрастанию элементы в тех строках,
    // которые содержат только кратные двум элементы.
    cout << endl << endl;
    const int cells = 5;
    int array_2[cells][cells];
    cout << "Another array from second task: \n";
    for (int i = 0; i < cells; i++) {
        for (int j = 0; j < cells; j++) {
            array_2[i][j] = rand() % 5 - 2; // [-4;4]
        }
    }

    for (int i = 0; i< cells; i++) {
        for (int j = 0; j < cells; j++) {
            cout << array_2[i][j] << " ";
        }
        cout << "\n";
    }

    // Filtering
    int divide_by_2;
    for (int j = 0; j < cells; j++) {
        divide_by_2 = 0;
        for (int i = 0; i < cells; i++) {
            if (array_2[j][i] % 2 == 0)
            {
                ++divide_by_2;
            }

            if (divide_by_2 == cells)
            {
                //Sorting row
                sort_for_second(array_2[i],cells);
                cout << "\n Sorted array: \n";
                show_array(array_2[i],cells);
            }

            if (j == cells - 1 && divide_by_2 == 0)
            {
                cout << "If array doesn't have any string which will be right for our task, we will sort last row\n Sorted array: \n";
                sort_for_second(array_2[i],cells);
                show_array(array_2[i],cells);
            }

        }
    }
    return 0;
}

void fill_array(double* array, int size_of_array)
{
    /* Fill array
     * Arg: array, size of array
     */
    for (int i = 0; i < size_of_array; i++) {
        array[i] = rand() % 21 - 5; // [-5;15]
    }
}
void show_array(double* array, int size_of_array)
{
    /*
     * Show array
     * Arg: array, size of array
     */
    for (int i = 0; i < size_of_array; i++) {
        cout << array[i] << " ";
    }
    cout << endl;
}

void show_array(double* array, int begin, int end)
{
    /* Show array from begin to end index
     * Arg: array, size of array, from index, to index
     */
    if (begin > end)
    {
        swap(begin,end);
    }
    for (int i = begin; i < end; i++) {
        cout << array[i] << " ";
    }
    cout << endl;
}

void sort_for_second(int* array, int size)
{
    int* left_stack = new int[size], *right_stack = new int[size];

    int st_pointer = 1;
    right_stack[st_pointer] = size - 1;
    left_stack[st_pointer] = 0;

  while (st_pointer > 0)
  { // Выборка из стека последнего запроса
    int left = left_stack[st_pointer];
    int right = right_stack[st_pointer];
    st_pointer--;

    while (left < right)
    {
      int i = left, j = right; // 7
      float middle = array[(left + right) / 2];
      while (i < j)
      {
        while (array[i] < middle)
        {
          i++;
        }
        while (middle < array[j])
        {
          j--;
        }
        if (i <= j)
        {
          float temp = array[i];
          array[i] = array[j];
          array[j] = temp;
          i++; j--;
        }
      }

      if (i < right)
      {
        st_pointer++;
        left_stack[st_pointer] = i;
        right_stack[st_pointer] = right;
      }
      right = j; // Теперь left и right ограничивают левую часть
    }
  }
}

void show_array(int* array, int begin, int end)
{
    /* Show array from begin to end index
     * Arg: array, size of array, from index, to index
     */
    if (begin > end)
    {
        swap(begin,end);
    }
    for (int i = begin; i < end; i++) {
        cout << array[i] << " ";
    }
    cout << endl;
}

void show_array(int* array, int size_of_array)
{
    /*
     * Show array
     * Arg: array, size of array
     */
    for (int i = 0; i < size_of_array; i++) {
        cout << array[i] << " ";
    }
    cout << endl;
}