Передача двумерного массива на сортировку
Имеется двумерный массив 5*2. Надо сделать так, чтобы массив отсортировался в порядке возрастания по первому элементу каждой пары. По заданию для этого действия нужно обязательно использовать пирамидальную сортировку (сортировку кучей). На выводе меня ждал странный результат, в котором первый элемент одной пары мог поменяться со вторым элементом другой пары. Это совершенно не то.
Скорее всего я неправильно передаю массив в функцию или неправильно манипулирую с массивами в самих функциях, но я так и не понял как надо правильно.
Далее будет приведён код и некорректный вывод. Заранее спасибо!
#include <stdio.h>
#include <stdlib.h>
// Функция "просеивания" через кучу - формирование кучи
void siftDown(int *numbers, int root, int bottom)
{
int maxChild; // индекс максимального потомка
int done = 0; // флаг того, что куча сформирована
// Пока не дошли до последнего ряда
while ((root * 2 <= bottom) && (!done))
{
if (root * 2 == bottom) // если мы в последнем ряду,
maxChild = root * 2; // запоминаем левый потомок
// иначе запоминаем больший потомок из двух
else if (numbers[root * 2] > numbers[root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;
// если элемент вершины меньше максимального потомка
if (numbers[root] < numbers[maxChild])
{
int temp = numbers[root]; // меняем их местами
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
root = maxChild;
}
else // иначе
done = 1; // пирамида сформирована
}
}
// Функция сортировки на куче
void heapSort(int *numbers, int array_size)
{
// Формируем нижний ряд пирамиды
for (int i = (array_size / 2); i >= 0; i--)
siftDown(numbers, i, array_size - 1);
// Просеиваем через пирамиду остальные элементы
for (int i = array_size - 1; i >= 1; i--)
{
int temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
siftDown(numbers, 0, i - 1);
}
}
int main()
{
//объявление массива
int a[5][2]=
{
{2,5},
{3,6},
{9,8},
{7,4},
{5,1}
};
//вывод элементов массива перед сортировкой
for (int j = 0; j<5; j++)
{
for(int i = 0; i<2; i++)
{
printf("%d ",a[j][i]);
}
printf("\n");
}
printf("\n");
heapSort(a, 5); // вызов функции сортировки
//вывод элементов массива после сортировки
for (int j = 0; j<5; j++)
{
for(int i = 0; i<2; i++)
{
printf("%d ",a[j][i]);
}
printf("\n");
}
return 0;
}
Ответы (1 шт):
В начале массива, объявленного таким образом, лежат элементы 2,5,3,6,9,и они, как видно из вывода, нормально сортируются. При минимальном изменении кода можно добиться желаемого, если внутри сортировки использовать индексы numbers, умноженные на 2, и при обмене ещё обменивать следующий элемент, например
int temp = numbers[2*root]; // меняем их местами
numbers[2*root] = numbers[2*maxChild];
numbers[2*maxChild] = temp;
temp = numbers[2*root+1]; // меняем их местами
numbers[2*root+1] = numbers[2*maxChild+1];
numbers[2*maxChild+1] = temp;
Но по уму функция сортировки должна принимать аргумент - двумерный массив.
