برنامه مرتب سازی ماتریس — راهنمای کاربردی

در این مطلب، روش نوشتن برنامه مرتب سازی ماتریس مورد بررسی قرار می‌گیرد. همچنین، پیاده‌سازی روش بیان شده، در زبان‌های برنامه‌نویسی گوناگون شامل ++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 با اندازه n² ساخته شود. با شروع از اولین سطر، یکی یکی عناصر ماتریس داده شده در []temp کپی می‌شوند. سپس، []temp مرتب می‌شود. اکنون، عناصر []temp یکی یکی در ماتریس اصلی کپی می‌شوند. در ادامه، پیاده‌سازی روش ساده بیان شده، در زبان‌های برنامه‌نویسی گوناگون انجام می‌شود. همچنین، خروجی قطعه کدها به منظور درک بهتر موضوع، در انتهای مطلب ارائه شده است.

برنامه مرتب سازی ماتریس در ++C

// C++ implementation to sort the given matrix 
#include <bits/stdc++.h> 
using namespace std; 
  
#define SIZE 10 
  
// function to sort the given matrix 
void sortMat(int mat[SIZE][SIZE], int n) 
{ 
    // temporary matrix of size n^2 
    int temp[n * n]; 
    int k = 0; 
  
    // copy the elements of matrix one by one 
    // into temp[] 
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) 
            temp[k++] = mat[i][j]; 
  
    // sort temp[] 
    sort(temp, temp + k); 
      
    // copy the elements of temp[] one by one 
    // in mat[][] 
    k = 0; 
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) 
            mat[i][j] = temp[k++]; 
} 
  
// function to print the given matrix 
void printMat(int mat[SIZE][SIZE], int n) 
{ 
    for (int i = 0; i < n; i++) { 
        for (int j = 0; j < n; j++) 
            cout << mat[i][j] << " "; 
        cout << endl; 
    } 
} 
  
// Driver program to test above 
int main() 
{ 
    int mat[SIZE][SIZE] = { { 5, 4, 7 }, 
                            { 1, 3, 8 }, 
                            { 2, 9, 6 } }; 
    int n = 3; 
  
    cout << "Original Matrix:\n"; 
    printMat(mat, n); 
  
    sortMat(mat, n); 
  
    cout << "\nMatrix After Sorting:\n"; 
    printMat(mat, n); 
  
    return 0; 
}

برنامه مرتب سازی ماتریس در جاوا

// Java implementation to  
// sort the given matrix 
import java.io.*; 
import java.util.*; 
  
class GFG { 
      
    static int SIZE = 10; 
  
    // function to sort the given matrix 
    static void sortMat(int mat[][], int n) 
    { 
        // temporary matrix of size n^2 
        int temp[] = new int[n * n]; 
        int k = 0; 
      
        // copy the elements of matrix  
        // one by one into temp[] 
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < n; j++) 
                temp[k++] = mat[i][j]; 
      
        // sort temp[] 
        Arrays.sort(temp); 
          
        // copy the elements of temp[] 
        // one by one in mat[][] 
        k = 0; 
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < n; j++) 
                mat[i][j] = temp[k++]; 
    } 
      
    // function to print the given matrix 
    static void printMat(int mat[][], int n) 
    { 
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < n; j++) 
                System.out.print( mat[i][j] + " "); 
            System.out.println(); 
        } 
    } 
      
    // Driver program to test above 
    public static void main(String args[]) 
    { 
        int mat[][] = { { 5, 4, 7 }, 
                        { 1, 3, 8 }, 
                        { 2, 9, 6 } }; 
        int n = 3; 
      
        System.out.println("Original Matrix:"); 
        printMat(mat, n); 
      
        sortMat(mat, n); 
      
        System.out.println("Matrix After Sorting:"); 
        printMat(mat, n); 
      
    } 
} 
  
// This code is contributed by Nikita Tiwari.

برنامه مرتب سازی ماتریس در پایتون ۳

# Python3 implementation to sort 
# the given matrix 
  
SIZE = 10
  
# Function to sort the given matrix 
def sortMat(mat, n) : 
      
    # Temporary matrix of size n^2 
    temp = [0] * (n * n) 
    k = 0
  
    # Copy the elements of matrix   
    # one by one into temp[] 
    for i in range(0, n) : 
          
        for j in range(0, n) : 
              
            temp[k] = mat[i][j] 
            k += 1
  
    # sort temp[] 
    temp.sort() 
      
    # copy the elements of temp[]  
    # one by one in mat[][] 
    k = 0
      
    for i in range(0, n) : 
          
        for j in range(0, n) : 
            mat[i][j] = temp[k] 
            k += 1
  
  
# Function to print the given matrix 
def printMat(mat, n) : 
      
    for i in range(0, n) : 
          
        for j in range( 0, n ) : 
              
            print(mat[i][j] , end = " ") 
              
        print() 
      
      
# Driver program to test above 
mat = [ [ 5, 4, 7 ], 
        [ 1, 3, 8 ], 
        [ 2, 9, 6 ] ] 
n = 3
  
print( "Original Matrix:") 
printMat(mat, n) 
  
sortMat(mat, n) 
  
print("\nMatrix After Sorting:") 
printMat(mat, n) 
  
  
# This code is contributed by Nikita Tiwari.

برنامه مرتب سازی ماتریس در #C

// C# implementation to 
// sort the given matrix 
using System; 
  
class GFG { 
    static int SIZE = 10; 
  
    // function to sort the given matrix 
    static void sortMat(int[, ] mat, int n) 
    { 
        // temporary matrix of size n^2 
        int[] temp = new int[n * n]; 
        int k = 0; 
  
        // copy the elements of matrix 
        // one by one into temp[] 
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < n; j++) 
                temp[k++] = mat[i, j]; 
  
        // sort temp[] 
        Array.Sort(temp); 
  
        // copy the elements of temp[] 
        // one by one in mat[][] 
        k = 0; 
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < n; j++) 
            mat[i, j] = temp[k++]; 
    } 
  
    // function to print the given matrix 
    static void printMat(int[, ] mat, int n) 
    { 
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < n; j++) 
            Console.Write(mat[i, j] + " "); 
            Console.WriteLine(); 
        } 
    } 
  
    // Driver code 
    public static void Main() 
    { 
        int[, ] mat = { { 5, 4, 7 }, 
                        { 1, 3, 8 }, 
                        { 2, 9, 6 } }; 
        int n = 3; 
  
        Console.WriteLine("Original Matrix:"); 
        printMat(mat, n); 
  
        sortMat(mat, n); 
  
        Console.WriteLine("Matrix After Sorting:"); 
        printMat(mat, n); 
    } 
} 
  
// 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(n²log₂n است. پیچیدگی فضای کمکی این روش نیز از درجه (O(n² است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده

^^