Sắp xếp mảng 2 chiều

Bài toán sắp xếp là một trong các bài toán cơ bản khi làm việc với mảng. Sau đây là các hướng dẫn làm các dạng sắp xếp cơ bản trong mảng 2 chiều

Để sắp xếp trong mảng 2 chiều thì người ta thường làm theo các trình tự sau đây :

• Đọc mảng 2 chiều và lưu vào mảng 1 chiều
• Sắp xếp mảng 1 chiều
• Tăng biến chạy hợp lý để gán mảng 1 chiều ngược vào mảng 2 chiều

Hàm đọc mảng 2 chiều và lưu vào mảng 1 chiều

void ChuyenMang(int A[][100], int m, int n, int B[], int &p)
{
  p = m*n;  //p là số phần tử của mảng B
  for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
      B[i*n + j] = A[i][j];
}

Sắp xếp mảng 1 chiều

void SapXep1Chieu(int A[], int n)
{
  for (int i = 0; i < n - 1; i++)
    for (int j = i + 1; j < n; j++)
      if (A[i] > A[j])
      {
        int t = A[i];
        A[i] = A[j];
        A[j] = t;
      }
}

Sắp xếp mảng 2 chiều trừ trái qua phải, từ trên xuống dưới

void SapXepThuong(int A[][100], int m, int n)
{
  int B[100];
  int p;
  ChuyenMang(A,m,n,B,p);
  SapXep1Chieu(B,p);
  for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
      A[i][j] = B[i*n+j];
}

Sắp xếp theo ZicZac

void SapXepZicZac(int A[][100], int m, int n)
{
  int B[100];
  int p;
  ChuyenMang(A,m,n,B,p);
  SapXep1Chieu(B,p);
  int vt = 0;
  int i, j;
  for (i = 0; i < m; i++)
  {
    if (i%2 == 0)
      for (j = 0; j < n; j++)
      {
        A[i][j] = B[vt];
        vt++;
      }
    else
      for (j = n - 1; j >= 0; j--)
      {
        A[i][j] = B[vt];
        vt++;
      }
  }
}

Sắp xếp theo dạng Xoắn Ốc

void SapXepXoanOc(int A[][100], int m, int n)
{
  int B[100];
  int p;
  ChuyenMang(A,m,n,B,p);
  SapXep1Chieu(B,p);
  int tren = 0, duoi = m - 1, trai = 0, phai = n - 1;
  int i, vt = 0;
  do 
  {
    for (i = trai; i <= phai && vt < p; i++)
      A[tren][i] = B[vt++];
    tren++;
    for (i = tren; i <= duoi && vt < p; i++)
      A[i][phai] = B[vt++];
    phai--;
    for (i = phai; i >= trai && vt < p; i--)
      A[duoi][i] = B[vt++];
    duoi--;
    for (i = duoi; i >= tren && vt < p; i--)
      A[i][trai] = B[vt++];
    trai++;
  } while (tren <= duoi && trai <= phai);
}

Sắp xếp theo dạng Ziczac xéo

void SapXepZicZacXeo(int A[][100], int m, int n)
{
  int B[100];
  int p;
  ChuyenMang(A,m,n,B,p);
  SapXep1Chieu(B,p);
  int vt = 0;
  int trai, phai;
  trai = 1;
  phai = 1;
  int i = 0, j = 0;
  A[i][j] = B[vt++];
  do 
  {
    if (j == n - 1)
      i++;
    else
      j++;
    A[i][j] = B[vt++];
    printf("A[%d][%d] = %d\n",i,j,A[i][j]);
    while (i < m - 1 && j > 0) 
    {
      i++;
      j--;
      A[i][j] = B[vt++];
      printf("A[%d][%d] = %d\n",i,j,A[i][j]);
    }
    if (i == m - 1)
      j++;
    else
      i++;
    A[i][j] = B[vt++];
    printf("A[%d][%d] = %d\n",i,j,A[i][j]);
    while (i > 0 && j < n - 1)
    {
      i--;
      j++;
      A[i][j] = B[vt++];
      printf("A[%d][%d] = %d\n",i,j,A[i][j]);
    }

  } while (i < m - 1 || j < n - 1);
}