Bài 45: Cách sắp xếp dãy số để tăng dần hoặc giảm dần

Tại sao sắp xếp dãy số là bài toán quan trọng trong lập trình?

Sắp xếp dãy số theo thứ tự tăng dần hoặc giảm dần là một bài toán cơ bản không thể thiếu trong lập trình. Đây là bài toán sắp xếp mảng một chiều. Bài toán này cũng là một trong những bài tập điển hình trong phần kiến thức về mảng. Sắp xếp cũng là một kiến thức quan trọng thuộc cấu trúc dữ liệu và giải thuật. Trong bài viết này, chúng ta sẽ cùng nhau giải quyết bài toán sắp xếp dãy số theo thứ tự tăng dần và giảm dần.

1. Dãy số là gì?

Khi làm bài tập lập trình liên quan đến các từ khóa sau:

• Sắp xếp dãy số tự nhiên tăng dần/giảm dần
• Sắp xếp mảng số thực tăng dần/giảm dần
• Sắp xếp mảng một chiều các số tự nhiên tăng/giảm dần

Thì cả ba đề bài này đều là bài toán sắp xếp dữ liệu trên mảng một chiều. Khi nhắc đến "dãy số", bạn phải nghĩ ngay đến mảng một chiều. Dưới đây là một số lưu ý trước khi tiếp tục đọc:

• Bạn cần có kiến thức về mảng một chiều để hiểu bài viết này.
• Có nhiều thuật toán sắp xếp khác nhau, bạn có thể tham khảo thêm.
• Tổng hợp bài tập mảng một chiều có lời giải.

2. Sắp xếp dãy số giảm dần

Trong code dưới đây, chúng ta sẽ sử dụng thuật toán sắp xếp chọn - một thuật toán dễ hiểu và dễ cài đặt nhất. Dưới đây là hình minh họa cho ý tưởng sắp xếp:

Code sắp xếp mảng/ dãy số giảm dần với C/C++:

#include

int main(){
    int a[100];
    int n;
    printf("Nhập số lượng phần tử n = ");
    do{
        scanf("%d", &n);
        if(n <= 0){
            printf("Nhập lại n = ");
        }
    }while(n <= 0);

    for(int i = 0; i < n; i++){
        printf("Nhập a[%d] = ",i);
        scanf("%d", &a[i]);
    }

    // Sắp xếp dùng thuật toán sắp xếp chọn
    int tg;
    for(int i = 0; i < n - 1; i++){
        for(int j = i + 1; j < n; j++){
            if(a[i] < a[j]){
                // Hoán vị 2 số a[i] và a[j]
                tg = a[i];
                a[i] = a[j];
                a[j] = tg;
            }
        }
    }

    printf("Mảng đã sắp xếp là: ");
    for(int i = 0; i < n; i++){
        printf("%5d", a[i]);
    }
}

Chạy thử:

Nhập số lượng phần tử n = 5
Nhập a[0] = 1
Nhập a[1] = 3
Nhập a[2] = 2
Nhập a[3] = 4
Nhập a[4] = 5
Mảng đã sắp xếp là: 5 4 3 2 1

3. Sắp xếp dãy số tăng dần

Việc sắp xếp dãy số tăng dần chỉ khác sắp xếp giảm dần duy nhất ở bước kiểm tra điều kiện để hoán vị.

Code sắp xếp mảng/ dãy số tăng dần với C/C++:

#include

int main(){
    int a[100];
    int n;
    printf("Nhập số lượng phần tử n = ");
    do{
        scanf("%d", &n);
        if(n <= 0){
            printf("Nhập lại n = ");
        }
    }while(n <= 0);

    for(int i = 0; i < n; i++){
        printf("Nhập a[%d] = ",i);
        scanf("%d", &a[i]);
    }

    // Sắp xếp dùng thuật toán sắp xếp chọn
    int tg;
    for(int i = 0; i < n - 1; i++){
        for(int j = i + 1; j < n; j++){
            if(a[i] > a[j]){
                // Hoán vị 2 số a[i] và a[j]
                tg = a[i];
                a[i] = a[j];
                a[j] = tg;
            }
        }
    }

    printf("Mảng đã sắp xếp là: ");
    for(int i = 0; i < n; i++){
        printf("%5d", a[i]);
    }
}

Chạy thử:

Nhập số lượng phần tử n = 5
Nhập a[0] = 1
Nhập a[1] = 2
Nhập a[2] = 4
Nhập a[3] = 3
Nhập a[4] = 5
Mảng đã sắp xếp là: 1 2 3 4 5

4. Sắp xếp dãy số tăng/giảm dần với hàm

Việc sử dụng hàm sẽ giúp code của chúng ta trở nên rõ ràng, sạch sẽ và dễ quản lý, nâng cấp. Với bài toán này, chúng ta có thể viết 4 hàm riêng biệt sau:

• void NhapMang(int a[], int n)
• void XuatMang(int a[], int n)
• void TangDan(int a[], int n)
• void GiamDan(int a[], int n)

Code sắp xếp mảng/ dãy số tăng/giảm dần với hàm C/C++:

#include

void NhapMang(int a[], int n){
    for(int i = 0; i < n; i++){
        printf("Nhập a[%d] = ",i);
        scanf("%d", &a[i]);
    }
}

void XuatMang(int a[], int n){
    for(int i = 0; i < n; i++){
        printf("%5d", a[i]);
    }
}

void TangDan(int a[], int n){
    int tg;
    for(int i = 0; i < n - 1; i++){
        for(int j = i + 1; j < n; j++){
            if(a[i] > a[j]){
                // Hoán vị 2 số a[i] và a[j]
                tg = a[i];
                a[i] = a[j];
                a[j] = tg;
            }
        }
    }
}

void GiamDan(int a[], int n){
    int tg;
    for(int i = 0; i < n - 1; i++){
        for(int j = i + 1; j < n; j++){
            if(a[i] < a[j]){
                // Hoán vị 2 số a[i] và a[j]
                tg = a[i];
                a[i] = a[j];
                a[j] = tg;
            }
        }
    }
}

int main(){
    int a[100];
    int n;
    printf("Nhập số lượng phần tử n = ");
    do{
        scanf("%d", &n);
        if(n <= 0){
            printf("Nhập lại n = ");
        }
    }while(n <= 0);

    NhapMang(a, n);
    printf("Mảng vừa nhập là: ");
    XuatMang(a, n);

    // Sắp xếp tăng dần
    TangDan(a, n);
    printf("Mảng sau khi sắp xếp tăng dần là: ");
    XuatMang(a, n);

    // Sắp xếp giảm dần
    GiamDan(a, n);
    printf("Mảng sau khi sắp xếp giảm dần là: ");
    XuatMang(a, n);
}

Kết quả chạy chương trình:

Nhập số lượng phần tử n = 5
Nhập a[0] = 1
Nhập a[1] = 4
Nhập a[2] = 3
Nhập a[3] = 2
Nhập a[4] = 5
Mảng vừa nhập là: 1 4 3 2 5
Mảng sau khi sắp xếp tăng dần là: 1 2 3 4 5
Mảng sau khi sắp xếp giảm dần là: 5 4 3 2 1

Chú ý:

• Với số thực hoặc ký tự, bạn chỉ cần sửa kiểu dữ liệu của mảng, cách nhập và xuất. Phần thuật toán sắp xếp vẫn giữ nguyên.
• Đây là thuật toán sắp xếp đơn giản và dễ cài đặt nhất. Bạn có thể thử cài đặt bằng những thuật toán sắp xếp khác.

Với những kiến thức này, bạn đã sẵn sàng để sắp xếp dãy số theo ý muốn rồi đấy! Hy vọng bạn đã tìm thấy những thông tin hữu ích từ bài viết này. Chúc bạn thành công trong việc áp dụng kiến thức này vào lập trình thực tế!