[C++]Sắp xếp mảng 2 chiều giảm dần theo từng cột

Ma trận là một cấu trúc dữ liệu hai chiều gồm hàng và cột, có thể chứa các giá trị số hoặc dữ liệu khác. Khi muốn giải quyết bài toán sắp xếp mảng 2 chiều c++  giảm dần theo từng cột, ta có thể  sử dụng nhiều cách sắp xếp khác nhau. Trong bài viết này, chúng ta sẽ tìm hiểu về cách sắp xếp các phần tử trong ma trận giảm dần theo từng cột ngôn ngữ lập trình c++ đơn giản nhất.

Bài trước: Bài 22: thuật toán cờ caro c++ mảng 2 chiều

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:
a) Nhập ma trận vuông n hàng, n cột các số nguyên (n<=50),
b) Hiện ma trận đó ra màn hình
c) Tính tích hàng k, hàng k nhập từ bàn phím
d) Tìm hàng có tổng các phần tử nhỏ nhất
e) Cho biết có bao nhiêu phần tử âm
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

2. Thuật toán sắp xếp mảng 2 chiều c++

2.1 Tính tích hàng k

  • Khởi tạo biến fun=1, Nhâp k từ bàn phím
  • Duyệt mảng, gán biến fun = fun* a[k][j].

2.2 Tìm hàng có tổng các phần tử nhỏ nhất

  • Khởi tạo biến min_sum = INT_MAX, sum=0, hang=0;
  • Duyệt mảng, tính tổng của từng hàng, so sánh tổng của từng hàng với min_sum. Nếu min_sum>sum thì gán lại min_sum, lưu vị trí hàng.
  • Gán lại sum=0, và tính tổng, so sánh hàng tiếp theo.

2.3 Sắp xếp các phần tử ma trận giảm dần theo từng cột

Để sắp xếp mảng 2 chiều c++ giảm dần theo từng cột thường thì mình sẽ sử dụng thuật toán nổi bọt bubble sort. Đây là thuật toán sắp xếp đơn giản nhất tuy nhiên có độ phức tạp thời gian là O(n^2), với n là số lượng phần tử cần sắp xếp. Trong trường hợp ma trận rất lớn, thuật toán này có thể trở nên rất chậm và không hiệu quả.

Sử dụng thuật toán sắp xếp nổi bọt để sắp xếp các phần tử của cột ma trận 2 chiều kích thước nxn:

  • 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.

3. Code 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ả

Sắp xếp các phần tử ma trận giảm dần theo từng cột

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: Bài 24: [C++] Mảng răng cưa 2 chiều: Cấp phát, khởi tạo và in mảng

Nguyễn Tiến Trường

Mình viết về những điều nhỏ nhặt trong cuộc sống, Viết về câu chuyện những ngày không có em