برنامه مرتب سازی ماتریس – راهنمای کاربردی
در این مطلب، روش نوشتن برنامه مرتب سازی ماتریس مورد بررسی قرار میگیرد. همچنین، پیادهسازی روش بیان شده، در زبانهای برنامهنویسی گوناگون شامل ++C، «جاوا» (Java)، «پایتون» (Python) و #C انجام شده است. برای مطالعه بیشتر راجع به ماتریسها، استفاده از دیگر مقالات مجله فرادرس پیرامون ماتریسها توصیه میشود. فرض میشود که یک ماتریس n × n داده شده است. مساله، مرتبسازی ماتریس مذکور است. در واقع، هدف نوشتن برنامهای است که ماتریس داده شده (مقادیر ماتریس) را مرتب کند. در اینجا، منظور از مرتبسازی آن است که همه عناصر در یک سطر به ترتیب صعودی باشند و برای سطر i، جایی که 1 <= i <= n-1، اولین عنصر از سطر i، بزرگتر یا مساوی آخرین عنصر از سطر i-1 است. مثال زیر در این راستا قابل توجه است.
Input : mat[][] = { {5, 4, 7}, {1, 3, 8}, {2, 9, 6} } Output : 1 2 3 4 5 6 7 8 9
برای حل مساله مذکور، ابتدا باید آرایه []temp با اندازه n2 ساخته شود. با شروع از اولین سطر، یکی یکی عناصر ماتریس داده شده در []temp کپی میشوند. سپس، []temp مرتب میشود. اکنون، عناصر []temp یکی یکی در ماتریس اصلی کپی میشوند. در ادامه، پیادهسازی روش ساده بیان شده، در زبانهای برنامهنویسی گوناگون انجام میشود. همچنین، خروجی قطعه کدها به منظور درک بهتر موضوع، در انتهای مطلب ارائه شده است.
برنامه مرتب سازی ماتریس در ++C
1// C++ implementation to sort the given matrix
2#include <bits/stdc++.h>
3using namespace std;
4
5#define SIZE 10
6
7// function to sort the given matrix
8void sortMat(int mat[SIZE][SIZE], int n)
9{
10 // temporary matrix of size n^2
11 int temp[n * n];
12 int k = 0;
13
14 // copy the elements of matrix one by one
15 // into temp[]
16 for (int i = 0; i < n; i++)
17 for (int j = 0; j < n; j++)
18 temp[k++] = mat[i][j];
19
20 // sort temp[]
21 sort(temp, temp + k);
22
23 // copy the elements of temp[] one by one
24 // in mat[][]
25 k = 0;
26 for (int i = 0; i < n; i++)
27 for (int j = 0; j < n; j++)
28 mat[i][j] = temp[k++];
29}
30
31// function to print the given matrix
32void printMat(int mat[SIZE][SIZE], int n)
33{
34 for (int i = 0; i < n; i++) {
35 for (int j = 0; j < n; j++)
36 cout << mat[i][j] << " ";
37 cout << endl;
38 }
39}
40
41// Driver program to test above
42int main()
43{
44 int mat[SIZE][SIZE] = { { 5, 4, 7 },
45 { 1, 3, 8 },
46 { 2, 9, 6 } };
47 int n = 3;
48
49 cout << "Original Matrix:\n";
50 printMat(mat, n);
51
52 sortMat(mat, n);
53
54 cout << "\nMatrix After Sorting:\n";
55 printMat(mat, n);
56
57 return 0;
58}
برنامه مرتب سازی ماتریس در جاوا
1// Java implementation to
2// sort the given matrix
3import java.io.*;
4import java.util.*;
5
6class GFG {
7
8 static int SIZE = 10;
9
10 // function to sort the given matrix
11 static void sortMat(int mat[][], int n)
12 {
13 // temporary matrix of size n^2
14 int temp[] = new int[n * n];
15 int k = 0;
16
17 // copy the elements of matrix
18 // one by one into temp[]
19 for (int i = 0; i < n; i++)
20 for (int j = 0; j < n; j++)
21 temp[k++] = mat[i][j];
22
23 // sort temp[]
24 Arrays.sort(temp);
25
26 // copy the elements of temp[]
27 // one by one in mat[][]
28 k = 0;
29 for (int i = 0; i < n; i++)
30 for (int j = 0; j < n; j++)
31 mat[i][j] = temp[k++];
32 }
33
34 // function to print the given matrix
35 static void printMat(int mat[][], int n)
36 {
37 for (int i = 0; i < n; i++) {
38 for (int j = 0; j < n; j++)
39 System.out.print( mat[i][j] + " ");
40 System.out.println();
41 }
42 }
43
44 // Driver program to test above
45 public static void main(String args[])
46 {
47 int mat[][] = { { 5, 4, 7 },
48 { 1, 3, 8 },
49 { 2, 9, 6 } };
50 int n = 3;
51
52 System.out.println("Original Matrix:");
53 printMat(mat, n);
54
55 sortMat(mat, n);
56
57 System.out.println("Matrix After Sorting:");
58 printMat(mat, n);
59
60 }
61}
62
63// This code is contributed by Nikita Tiwari.
برنامه مرتب سازی ماتریس در پایتون ۳
1# Python3 implementation to sort
2# the given matrix
3
4SIZE = 10
5
6# Function to sort the given matrix
7def sortMat(mat, n) :
8
9 # Temporary matrix of size n^2
10 temp = [0] * (n * n)
11 k = 0
12
13 # Copy the elements of matrix
14 # one by one into temp[]
15 for i in range(0, n) :
16
17 for j in range(0, n) :
18
19 temp[k] = mat[i][j]
20 k += 1
21
22 # sort temp[]
23 temp.sort()
24
25 # copy the elements of temp[]
26 # one by one in mat[][]
27 k = 0
28
29 for i in range(0, n) :
30
31 for j in range(0, n) :
32 mat[i][j] = temp[k]
33 k += 1
34
35
36# Function to print the given matrix
37def printMat(mat, n) :
38
39 for i in range(0, n) :
40
41 for j in range( 0, n ) :
42
43 print(mat[i][j] , end = " ")
44
45 print()
46
47
48# Driver program to test above
49mat = [ [ 5, 4, 7 ],
50 [ 1, 3, 8 ],
51 [ 2, 9, 6 ] ]
52n = 3
53
54print( "Original Matrix:")
55printMat(mat, n)
56
57sortMat(mat, n)
58
59print("\nMatrix After Sorting:")
60printMat(mat, n)
61
62
63# This code is contributed by Nikita Tiwari.
برنامه مرتب سازی ماتریس در #C
1// C# implementation to
2// sort the given matrix
3using System;
4
5class GFG {
6 static int SIZE = 10;
7
8 // function to sort the given matrix
9 static void sortMat(int[, ] mat, int n)
10 {
11 // temporary matrix of size n^2
12 int[] temp = new int[n * n];
13 int k = 0;
14
15 // copy the elements of matrix
16 // one by one into temp[]
17 for (int i = 0; i < n; i++)
18 for (int j = 0; j < n; j++)
19 temp[k++] = mat[i, j];
20
21 // sort temp[]
22 Array.Sort(temp);
23
24 // copy the elements of temp[]
25 // one by one in mat[][]
26 k = 0;
27 for (int i = 0; i < n; i++)
28 for (int j = 0; j < n; j++)
29 mat[i, j] = temp[k++];
30 }
31
32 // function to print the given matrix
33 static void printMat(int[, ] mat, int n)
34 {
35 for (int i = 0; i < n; i++) {
36 for (int j = 0; j < n; j++)
37 Console.Write(mat[i, j] + " ");
38 Console.WriteLine();
39 }
40 }
41
42 // Driver code
43 public static void Main()
44 {
45 int[, ] mat = { { 5, 4, 7 },
46 { 1, 3, 8 },
47 { 2, 9, 6 } };
48 int n = 3;
49
50 Console.WriteLine("Original Matrix:");
51 printMat(mat, n);
52
53 sortMat(mat, n);
54
55 Console.WriteLine("Matrix After Sorting:");
56 printMat(mat, n);
57 }
58}
59
60// This code is contributed by Sam007
خروجی قطعه کدهای بالا، به صورت زیر است.
Original Matrix: 5 4 7 1 3 8 2 9 6 Matrix After Sorting: 1 2 3 4 5 6 7 8 9
پیچیدگی زمانی روش ارائه شده در بالا از درجه (O(n2log2n است. پیچیدگی فضای کمکی این روش نیز از درجه (O(n2 است.
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامهنویسی
- آموزش برنامهنویسی C++
- مجموعه آموزشهای ریاضیات
- یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
- الگوریتم بازی مار و پله همراه با کد — به زبان ساده
- حل مساله n وزیر با الگوریتم پسگرد (Backtracking) — به زبان ساده
^^