1

Сортировка - 3
Отсортировать матрицу n*n по схеме расположения с помощью алгоритма сортировки из Сорт-1.

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


// Создание динамической матрицы
void newMatrix(int**& a, int n)
{
    a = new int* [n];
    for (int i = 0; i < n; i++)
        a[i] = new int[n];
}

// Вывод матрицы на консоль
void printMatrix(int** a, int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cout << setw(4) << a[i][j];
        cout << endl;
    }
}

// Заполнение матрицы случайнми числами
void randomMatrix(int** a, int n)
{
    srand(time(NULL));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            a[i][j] = rand() % (n * n);
}

// копирование из матрицы в массив
int* mass(int** a, int n) {
    int* b = new int[n * n];
    int Ai = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            b[Ai] = (a[i][j]);
            Ai++;
        }
    return b;
    }
}
// Функция сортирует массив а по неубыванию методом подсчета
void sortArray(int* a, int n)
{
    int* c = new int[n];
    for (int i = 0; i < n; i++) //обнуление счётчиков
        c[i] = 0;
    //Подсчет
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] >= a[j])
                c[i]++;
            else
                c[j]++;
    //Расстановка
    int* b = new int[n];
    for (int i = 0; i < n; i++) {
        b[c[i]] = a[i];
    }

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

}
// Фукнция заполняет матрицу по схеме расположения (по строкам)
void fillSnakeMatrix(int** a, int* b, int n)
{
    int k = 0;

    for (int i = n - 1; i >= 0; i--)
    {
        if (i % 2 == 0) {

            for (int j = (n / 2) - 1; j >= 0; j--) {
                a[i][j] = k++;
            }

        }

        else
            for (int j = 0; j < n / 2; j++) {
                a[i][j] = k++;
            }
    }

    for (int j = n / 2; j < n; j++)
    {
        if (j % 2 == 0) {
            for (int i = 0; i < n; i++) {
                a[i][j] = k++;
            }

        }

        else
            for (int i = n - 1; i >= 0; i--) {
                a[i][j] = k++;
            }
    }
}




int main()
{
    setlocale(LC_ALL, "Russian");
    int n;
    do {
        cout << "Input n" << endl;
        cin >> n;
    } while (n < 1 || n > 10);

    int** a = new int*[n];



    newMatrix(a, n);

    randomMatrix(a, n);

    cout << "1 Matrix:" << endl;
    printMatrix(a, n);

    int* b = mass(a, n);
    

    sortArray(b, n*n);


    //int* ar = NULL;


    fillSnakeMatrix(a, b, n);

    cout << "2 Matrix:" << endl;
    printMatrix(a, n);

    system("pause");
    return 0;

} ```
2
  • В этот вопрос следует включить больше подробностей и уточнить проблему. 2 июн 2022 в 5:20
  • Разгадка в том что fillSnakeMatrix не использует аргумент b. Вместо этого она заполняет матрицу последовательными целыми числами (k++). 2 июн 2022 в 7:21

2 ответа 2

1

А они и не должны выводиться. Потому что этот код не имеет никакого отношения к сортировке подсчетом.
Сортировка подсчетом:

  • первый проход по массиву - подсчет количества чисел в массиве, в отдельный массив счетчиков, в котором число является индексом
  • второй проход - запись в массив чисел, исходя из их количества

А у Вас в sortArray() совсем иное:
По алгоритму нужно подсчитывать количество чисел. А у вас подсчитывается что-то не понятное. А с расстановкой тем более непонятно что делается.

    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] >= a[j])  // подсчет неизвестно чего
                c[i]++;
            else
                c[j]++;

Просто ради интереса выведите в консоль массивы b[] и c[]и посмотрите на их содержимое!
В общем вся эта функция должна выглядеть гораздо проще:

void sortArray(int* a, int n) // n - размерность матрицы
{
    int* c = new int[n*n];
    for (int i = 0; i < n * n; i++) //обнуление счётчиков можно сделать через memset()
        c[i] = 0;
    //Подсчет
    for (int i = 0; i < n; i++)
        c[ a[i] ]++;  // изначальные числа a[i] являются индексами в массиве счетчиков c[i]

    //Расстановка
    int l = 0;
    for (int i = 0; i < n *n; i++) // проход по массиву счетчиков
       for (int j = 0; i < c[i]; j++) // запись c[i] элементов i в массив a
          { 
             a[l] = i;
             l++;
          }
    delete[] c;
}

Кроме всего прочего:

  • нигде не освобождается ранее выделенная память
  • производится множественное копирование матрицы в массив, массивов в матрицу, хотя можно сортировать сразу матрицу.
    Дальше не смотрел.
3
  • Алгоритм ТС считает некоторое число инверсий. Эту логику можно довести до рабочей: если вы знаете сколько в массиве элементов меньше данного, вы знаете на каком месте данный элемент окажется после сортировки. Ругаться в данном случае - не метод. :) 2 июн 2022 в 7:05
  • @Stanislav Volodarskiy А я и не ругаюсь. :) Я описываю косяки в коде. И в комментарии - сортировка методом подсчета.
    – DmitryK
    2 июн 2022 в 7:12
  • Автор не знает терминологии: подсчитывается число элементов меньше данного. Не тестировал, но, возможно, этот код вполне рабочий. 2 июн 2022 в 7:14
0

Спасибо за комментарий @Stanislav Volodarskiy.
Если рассматривать через подсчет элементов, меньших текущего, то код действительно рабочий. Ошибка только в одном месте - return b; стоит до закрывающей скобки цикла, а должен быть после. Если использовать другой стиль оформления кода, то она сразу же стала бы заметна:

// копирование из матрицы в массив
int* mass(int** a, int n) 
{
    int* b = new int[n * n];
    int Ai = 0;
    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < n; j++) 
        {
            b[Ai] = (a[i][j]);
            Ai++;
        }
    // return b;  // был здесь - функция заканчивалась после обработки 1 строки матрицы
    }
    return b;  // должен быть здесь
} 
14
  • Ещё fillSnakeMatrix с ошибкой. 2 июн 2022 в 7:57
  • fillSnakeMatrix() даже не смотрел - вопрос был ошибка в сортировке
    – DmitryK
    2 июн 2022 в 8:14
  • а как добавить аргумент b если он не является матрицей
    – Дина
    2 июн 2022 в 10:09
  • Куда добавить и что Вы хотите с ним делать? Как использовать?
    – DmitryK
    2 июн 2022 в 10:31
  • fillSnakeMatrix не использует аргумент b. я так понимаю ошибка в этом. но я не понимаю как добавить у меня матрица заполняется последовательными целыми числами (k++) а так не должно быть
    – Дина
    2 июн 2022 в 17:28

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.