Как сделать функцию Heapsort для 2D массива

Question

Тема: Разработка программы на С++ для сортировки массива методом (Heapsort). Задание:

Разработать функцию на С++ для сортировки массива по методу Heapsort.
Создать матрицу (3х5) и заполнить ее случайными числами.
Произвести сортировку матрицы, используя разработанную функцию.

Сначала я сделал просто массив в формате 1D, сделав его динамическим я мог вставить его размер (15) и затем просто через уже созданную функцию HeapSort все числа ставали в правильном порядке. Далее я создал 2D массив и заполнил его случайными числами и перешел на этап переделки функции в 2Д. Наткнулся на готовый код на Java (https://www.justinlog.com/heapsort-2d-and-option-for-min-max-heap), но в меру своих сил не могу адекватно проанализировать этот пример и перенести или реализовать его на C++.

     #include <iostream>
     #include<iomanip>
     #include<cstdlib>
     using namespace std;
                  
     int main()
    {
    int k, temp;
    const int n = 3, m = 5;
      int ar[n][m];
       srand(time(NULL));


        for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
         ar[i][j] = rand() % 90;
              }

          }
           for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
               cout << ar[i][j] << " ";
          }
        cout << endl;
        }
                                  //Функция для 1Д сортировки
           void heap()
        {
        int max = i;
       while (true)
        {
        int left = 2 * i + 1;  // left half
        if (left < n && a[left] > a[max])
            max = left;
        left++;               // raight half
        if (left < n && a[left]  > a[max])
            max = left;
        if (max == i)
            break;
        else {

            std::swap(a[max], a[i]);
            i = max;
        }


    }


}
                                  
  void heapsort() {

    for (int i = n / 2; i >= 0; i--)
        heap(a, i, n);     // create heap
    for (int i = n - 1; i >= 1; i--)
    {
        std::swap(a[0], a[i]);
        heap(a, 0, i);

    }

Answer 1

Двумерный массив в памяти располагается построчно как одномерный. Т.е. двумерный массив 3x4 в памяти выглядит точно так же как одномерный массив из 12 элементов.
Используйте арифметику указателей. Возьмите указатель на массив и работайте со смещениями указателей. Т.е. в функции одномерной сортировки вместо взятия значения по двум индексам, берите значение от указателя:

int* p = ar;
if (left < n && a[left] > a[max]) {} // аналогично
if (left < n && *(p + left) > *(p + max) ) {}

for (int i = 0; i < n; i++) 
   for (int j = 0; j < m; j++) 
   {
     ar[i][j] = rand() % 90;
   }
// аналогично
for (int i = 0; i < n*m; i++)
  {
    *(ar + i) = rand() % 90;
  }

Только не забывайте, что теперь размер одномерного массива - n*m.
Если для двумерной индексации, то индекс считается так:

ar[i][j] == *(ar + i*m + j)  // эти записи идентичны
                             // обращение к одному и тому же элементу

Если ещё учесть, что сортировка кучей (пирамидой) на самом деле сортирует бинарное дерево, которое просто записано (хранится в памяти) последовательно в массив то получается вообще красиво - вы сортируете двумерный массив, записанный как бинарное дерево в одномерный массив. :)

Answer 2

Странно, какие проблемы могли возникнуть? Вот ваша функция сортировки, как она написана в вопросе.

void heap()
{
    int max = i;
    while (true)
    {
        int left = 2 * i + 1;  // left half
        if (left < n && *(a + left) > *(a + max))
            max = left;
        left++;               // right half
        if (left < n && *(a + left)  > *(a + max))
            max = left;
        if (max == i)
            break;
        else 
        {
            std::swap(*(a + max), *(a + i));
            i = max;
        }
    }
}

В таком виде она конечно не работает - вы используете в функции переменные, которые туда никак не попадали. А в main() вы даже не вызываете эти функции.
Но! Вы написали, что у вас работает программа для одномерного массива. Вот и подставьте в работающую программу код функции сортировки и всё будет работать!
Вопрос был - для одномерного массива сортировка работает, а для двумерного не получается. Я написал как сделать для двумерного массива.
Если вопрос - "напишите мне программу сортировки", то вы зашли не на тот сайт.

БЛОГ НА HUSL

Как сделать функцию Heapsort для 2D массива

Ответы (2 шт):