Ma trận là một cấu trúc dữ liệu 2 chiều, gồm hàng và cột, dùng để lưu trữ các giá trị số hoặc dữ liệu khác. Trong lập trình, việc sắp xếp mảng 2 chiều c++ là một bài toán phổ biến. Bài viết này sẽ tập trung vào việc sắp xếp mảng 2 chiều tăng dần theo dòng, tăng dần theo cột bằng ngôn ngữ lập trình c++.
Bài trước:
tính tổng các phần tử trong mảng 2 chiều c++
1. Bài toán sắp xếp mảng 2 chiều
Bài 23 (TH-CSLT-06): Viết chương trình thực hiện:
- Nhập ma trận vuông n hàng, n cột các số nguyên (n<=50),
- Hiện ma trận đó ra màn hình
- Tính tích hàng k, hàng k nhập từ bàn phím
- Tìm hàng có tổng các phần tử nhỏ nhất
- Cho biết có bao nhiêu phần tử âm
- Sắp xếp các phần tử ma trận giảm dần theo từng cột và hiện ra màn hình ma trận mới
2. Các thuật toán sắp xếp mảng 2 chiều trong C++
2.1. Sắp xếp mảng 2 chiều tăng dần theo dòng
- Duyệt qua từng dòng.
- Sử dụng thuật toán sắp xếp nổi bọt (bubble sort) để sắp xếp các phần tử trong từng dòng.
Thuật toán:
- Lặp qua từng dòng
i. - Trong dòng i, so sánh từng phần tử
a[i][j]vớia[i][j+1]. - Nếu
a[i][j] > a[i][j+1], hoán đổi vị trí.
Code mẫu:
// Sắp xếp tăng dần theo dòng
void sapXepTangDanTheoDong(int n, int a[][255]) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1; j++) {
for (int k = 0; k < n - j - 1; k++) {
if (a[i][k] > a[i][k + 1]) {
swap(a[i][k], a[i][k + 1]);
}
}
}
}
}
2.2. Sắp xếp mảng 2 chiều tăng dần theo cột
Thuật toán:
- Duyệt từng cột (j từ 0 đến n-1).
- So sánh từng cặp phần tử liên tiếp
a[k][j]vàa[k+1][j]. - Nếu
a[k][j] > a[k+1][j], hoán đổi vị trí.
Code mẫu:
//Sap xep mang 2 chieu tang dan theo cot
void sapxepgiamdantheocot(int n, int a[][255]){
for(int j=0;j<n;j++){
for(int i=0;i<n;i++){
for(int k=0;k<n-i-1;k++){
if(a[k][j]>a[k+1][j]){
int temp = a[k][j];
a[k][j]=a[k+1][j];
a[k+1][j]=temp;
}
}
}
}
}
2.3.Sắp xếp mảng 2 chiều giảm dần theo cột
Để sắp xếp một mảng 2 chiều trong C++ theo thứ tự giảm dần trên từng cột, mình thường sử dụng thuật toán sắp xếp nổi bọt (bubble sort). Đây là một thuật toán đơn giản nhưng có độ phức tạp thời gian là O(n²), trong đó n là số lượng phần tử cần sắp xếp. Với các ma trận có kích thước lớn, thuật toán này có thể chạy chậm và kém hiệu quả.
Cách thực hiện sắp xếp các phần tử của cột trong ma trận 2 chiều kích thước n×n bằng thuật toán nổi bọt như sau:
- Vòng lặp thứ nhất j duyệt qua tất cả các cột của mảng 2 chiều
- Vòng lặp thứ 2 i để duyệt các tất cả các hàng trong mảng 2 chiều
- Vòng lặp thứ 3 có biến k để duyệt qua tất cả các phần tử của cột hiện tại j. So sánh phần tử thứ a[k][j] với phần tử tiếp theo a[k+1][j], nếu phần tử a[k][j] lớn hơn a[k+1][j] thì tiến hành hoán đổi với biến tạm temp.
- Kết thúc vòng lặp, thực hiện xuất mảng ra màn hình.
//f) Sắp xếp các phần tử ma trận giảm dần theo từng cột và hiện ra màn hình ma trận mới
void sapxepgiamdantheocot(int n, int a[][255]){
for(int j=0;j<n;j++){
for(int i=0;i<n;i++){
for(int k=0;k<n-i-1;k++){
if(a[k][j] < a[k+1][j]){
int temp = a[k][j];
a[k][j]=a[k+1][j];
a[k+1][j]=temp;
}
}
}
}
}
3. Code minh hoạ sắp xếp mảng 2 chiều c++
#include<iostream>
#include<iomanip>
using namespace std;
//a.Nhap mang
void nhapmang(int n, int a[][255]){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<"a["<<i<<"]["<<j<<"]= ";
cin>>a[i][j];
}
}
}
//b. Hien mang
void xuatmang(int n, int a[][255]){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<setw(5)<<a[i][j];
}
cout<<endl;
}
}
//c. Tính tích hàng k, hàng k nhập từ bàn phím.
void tinhtichhangk(int n, int a[][255]){
int k;
double fun=1;
cout<<"Nhap hang can tinh tich k: "; cin>>k;
for(int j=0;j<n;j++){
fun= fun*a[k][j];
}
cout<<" Tich hang "<<k<<" = "<<fun;
}
//d. Tim hang co tong cac phan tu nho nhat
void hangcotongnhonhat(int n, int a[][255]){
int min_sum=INT_MAX, sum=0, hang;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
sum += a[i][j];
}
if(sum<min_sum){
min_sum=sum;
hang=i;
}
sum=0;
}
cout<<"Hang co phan tu nho nhat la: "<<hang<<" voi tong = "<<min_sum;
}
//e) Cho biết có bao nhiêu phần tử âm
void demphantuam(int n, int a[][255]){
int dem=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]<0){
dem++;
}
}
}
cout<<"So phan tu am trong mang la: "<<dem;
}
//f) Sắp xếp các phần tử ma trận giảm dần theo từng cột và hiện ra màn hình ma trận mới
void sapxepgiamdantheocot(int n, int a[][255]){
for(int j=0;j<n;j++){
for(int i=0;i<n;i++){
for(int k=0;k<n-i-1;k++){
if(a[k][j]<a[k+1][j]){
int temp = a[k][j];
a[k][j]=a[k+1][j];
a[k+1][j]=temp;
}
}
}
}
}
int main(){
int n,a[255][255], chon;
cout<<"Nhap n: "; cin>>n;
do{
cout<<"1. Nhap mang"<<endl;
cout<<"2. Xuat mang"<<endl;
cout<<"3. Tinh tich hang k, hang k nhap vao tu ban phim"<<endl;
cout<<"4. Tim hang co tong cac phan tu nho nhat"<<endl;
cout<<"5. Cho biet co bao nhieu phan tu am"<<endl;
cout<<"6. Sap xep cac phan tu ma tran giam dan theo tung cot"<<endl;
cout<<"Lua chon: "; cin>>chon;
switch(chon){
case 1:{
nhapmang(n,a);
cout<<endl;
break;
}
case 2:{
xuatmang(n,a);
cout<<endl;
break;
}
case 3:{
tinhtichhangk(n,a);
cout<<endl;
break;
}
case 4:{
hangcotongnhonhat(n,a);
cout<<endl;
break;
}
case 5:{
demphantuam(n,a);
cout<<endl;
break;
}
case 6:{
sapxepgiamdantheocot(n,a);
xuatmang(n,a);
cout<<endl;
break;
}
default: exit(0);
}
}while(chon!=0);
}
4. Kết quả chạy chương trình
Trên đây là một đoạn mã đơn giản để sắp xếp ma trận giảm dần theo từng cột trong ngôn ngữ C++. Cảm ơn các bạn đã tham khảo trên ttnguyen.net
Tải full bài tập thực hành C/C++ có lời giải:
Bài tiếp theo:
