Сортировка элементов матрицы - C (СИ)
Формулировка задачи:
#include<stdio.h>
#include<conio.h>
#include<locale.h>
int main()
{
int i, j, s, A[s][s], y;
setlocale(LC_ALL, "Russian");
printf("Введите количество строк и столбцов:\n");
scanf("%d", &s);
for (i=0; i<s; i++)
{for (j=0; j<s; j++)
{
printf("A[%d][%d]=", i, j);
scanf("%d"), &A[i][j];
}
printf("\n");
}
system("pause");
}Решение задачи: «Сортировка элементов матрицы»
#include <stdio.h>
#include <stdlib.h>
//расположить в порядке возрастания ненулевые элементы правого верхнего треугольника матрицы
void triangle_sort(int R, int U, int N, int M)
{
int i, j, S = 0, k = 0, x = 0, t, l, min;
int **p = NULL, *q = NULL;
p = (int**)malloc(N * sizeof(int*));
for(i = 0; i < N; i++)
p[i] = (int*)malloc((M * sizeof(int)));
for(i = 0; i < N; i++)
for(j = 0; j < M; j++){
printf("Enter the value of the element A[%d][%d] = ", i, j);
scanf("%d", &p[i][j]);
}
puts("Sourse matrix:");
for(i = 0; i < N; i++){
for(j = 0; j < M; j++){
printf("%6d", p[i][j]);
}
printf("\n");
}
for(i = 0; i < R; i++)
S += R - i;
q = (int*)malloc((S * sizeof(int)));
for(i = 0; i < N; i++, x++){
for(j = U + x; j < M; j++, k++){
q[k] = p[i][j];
}
}
for(k = 0; k < S - 1; k++){
while(q[k] == 0)
k++;
min = k;
for(l = k + 1; l < S; l++){
if(q[l] != 0){
if(q[l] < q[min])
min = l;
}
}
t = q[k];
q[k] = q[min];
q[min] = t;
}
x = 0;
k = 0;
for(i = 0; i < N; i++, x++){
for(j = U + x; j < M; j++, k++){
p[i][j] = q[k];
}
}
puts("Sorted matrix:");
for(i = 0; i < N; i++){
for(j = 0; j < M; j++){
printf("%6d", p[i][j]);
}
printf("\n");
}
free(q);
for(i = 0; i < N; i++)
free(p[i]);
free(p);
}
int main()
{
int N, M;
puts("Input matrix size:");
puts("Quantity rows:");
scanf("%d", &N);
puts("Quantity columns:");
scanf("%d", &M);
if(M > N){
triangle_sort(N, M - N, N, M);
}
else{
triangle_sort(M, 0, N, M);
}
return 0;
}
Объяснение кода листинга программы
Код представлен в виде функции с названием triangle_sort, которая принимает 4 параметра типа int: R (количество строк в матрице), U (количество столбцов, начиная с которого находятся ненулевые элементы), N (общее количество строк в матрице) и M (общее количество столбцов в матрице).
Функция сначала инициализирует матрицу, заполняя её значениями по запросу пользователя. Затем выводит исходную матрицу на экран.
Далее функция приступает к сортировке. Она создает новый массив q, в который будут копироваться отсортированные значения. Изначально все элементы массива q равны нулю.
Затем функция начинает перебирать элементы матрицы, начиная с правого верхнего угла. Если элемент матрицы не равен нулю, то его значение добавляется в массив q. При этом в массиве q индексы элементов увеличиваются на единицу относительно текущего индекса. Это позволяет создать лестницу из ненулевых элементов, которую затем будет легко отсортировать.
После того, как все ненулевые элементы матрицы были добавлены в массив q, функция начинает сортировку этого массива. Она использует алгоритм сортировки с выбором (selection sort), который перебирает элементы массива и на каждом шаге находит минимальный элемент и меняет его местами с текущим элементом.
После сортировки массива q функция начинает заполнять отсортированными значениями исходную матрицу, начиная с правого верхнего угла.
В конце функция выводит отсортированную матрицу на экран и освобождает все выделенные ею ресурсы.
В функции main создается переменная N, которая содержит количество строк в матрице, и переменная M, которая содержит количество столбцов в матрице. Затем пользователю предлагается ввести размеры матрицы. Если количество столбцов больше количества строк, то функция triangle_sort сортирует строки, иначе - столбцы.