Ajutor urgent in c++ Creati o programa care sorteaza elementele de pe perimetru unei matrice crescator prin metoda interclasarea(Merge sort)
Răspunsuri la întrebare
Salut!
Ai rezolvarea in C++ mai jos
#include <iostream>
using namespace std;
const int N = 501;
const int M = 251000;
int aux[M];
//Functie MergeSort
void mergesort(int v[], int st, int dr)
{
if (st < dr)
{
int m = (st + dr) / 2;
mergesort(v, st, m);
mergesort(v, m + 1, dr);
//Interclasare
int i = st, j = m + 1, k = 0;
while (i <= m && j <= dr)
{
if (v[i] < v[j])
{
aux[++k] = v[i++];
}
else
{
aux[++k] = v[j++];
}
}
while (i <= m)
{
aux[++k] = v[i++];
}
while (j <= dr)
{
aux[++k] = v[j++];
}
for (i = st, j = 1; i <= dr; ++i, ++j)
{
v[i] = aux[j];
}
}
}
int main()
{
int n, m, mat[N][N], vec[M], ind = 0;
//Citire matrice
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
cin >> mat[i][j];
}
}
for (int j = 1; j <= m; ++j)
{
vec[++ind] = mat[1][j];
}
for (int i = 2; i <= n; ++i)
{
vec[++ind] = mat[i][m];
}
for (int j = m - 1; j >= 1; --j)
{
vec[++ind] = mat[n][j];
}
for (int i = 2; i <= n - 1; ++i)
{
vec[++ind] = mat[i][1];
}
//Sortare vector
mergesort(vec, 1, ind);
//Copiere vector inapoi in aceeasi matrice
int ind2 = 0;
for (int j = 1; j <= m; ++j)
{
mat[1][j] = vec[++ind2];
}
for (int i = 2; i <= n; ++i)
{
mat[i][m] = vec[++ind2];
}
for (int j = m - 1; j >= 1; --j)
{
mat[n][j] = vec[++ind2];
}
for (int i = 2; i <= n - 1; ++i)
{
mat[i][1] = vec[++ind2];
}
//Afisare matrice
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
cout << mat[i][j] << " ";
}
cout << '\n';
}
return 0;
}
- Explicatie:
Am folosit un vector pentru a copia perimetrul matricii in el, am sortat vectorul folosind algoritmul de sortare MergeSort, apoi am copiat inapoi vectorul in matrice si am afisat matricea cu perimetrul sortat.
- Ti-am lasat si fisierul mai jos
Adică ce funcție au
ind2 = acelasi lucru doar ca incepe de la 0