Bài 45. Sắp xếp dãy số giảm dần, tăng dần

Trong lập trình, việc 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 đơn giản và cơ bản. Đây là bài toán sắp xếp một mảng một chiều theo thứ tự tăng dần hoặc giảm dần. Bài toán này là trọng tâm của kiến thức về mảng một chiều và thuật toán trong cấu trúc dữ liệu và giải thuật.

1. Dãy số hay là mảng?

Khi làm bài tập lập trình, khi bạn gặp các cụm từ như:

Bạn đang xem: Bài 45. Sắp xếp dãy số giảm dần, tăng dần

• 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

Xem thêm : Nhóm máu hệ ABO

Cả ba đề bài này đều liên quan đến việc sắp xếp dữ liệu trên mảng một chiều. Khi nhắc đến “dãy số”, chúng ta 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ài viết này:

• 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 mã code dưới đây, chúng ta sử dụng thuật toán sắp xếp chọn để giải quyết bài toán này. Thuật toán sắp xếp chọn là thuật toán dễ hiểu và dễ cài đặt nhất.

#include 

void sapXepGiamDan(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int max = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] > a[max]) {
                max = j;
            }
        }
        std::swap(a[i], a[max]);
    }
}

int main() {
    int n;
    std::cout << "Nhập số phần tử của mảng: ";
    std::cin >> n;
    int a[n];
    std::cout << "Nhập các phần tử của mảng: ";
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    std::cout << "Mảng sau khi sắp xếp giảm dần là: ";
    sapXepGiamDan(a, n);
    for (int i = 0; i < n; i++) {
        std::cout << a[i] << " ";
    }
    return 0;
}

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

Xem thêm : Tổng Hợp Bài Tập Incoterms 2010 Và Incoterms 2020 Có Đáp Á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ị.

#include 

void sapXepTangDan(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }
        std::swap(a[i], a[min]);
    }
}

int main() {
    int n;
    std::cout << "Nhập số phần tử của mảng: ";
    std::cin >> n;
    int a[n];
    std::cout << "Nhập các phần tử của mảng: ";
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    std::cout << "Mảng sau khi sắp xếp tăng dần là: ";
    sapXepTangDan(a, n);
    for (int i = 0; i < n; i++) {
        std::cout << a[i] << " ";
    }
    return 0;
}

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 mã code trở nên rõ ràng, sạch sẽ và dễ quản lý, nâng cấp. Chúng ta có thể viết 4 hàm riêng biệt sau:

#include 

void nhapMang(int a[], int n) {
    std::cout << "Nhập các phần tử của mảng: ";
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
}

void xuatMang(int a[], int n) {
    std::cout << "Mảng: ";
    for (int i = 0; i < n; i++) {
        std::cout << a[i] << " ";
    }
    std::cout << std::endl;
}

void sapXepTang(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }
        std::swap(a[i], a[min]);
    }
}

void sapXepGiam(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int max = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] > a[max]) {
                max = j;
            }
        }
        std::swap(a[i], a[max]);
    }
}

int main() {
    int n;
    std::cout << "Nhập số phần tử của mảng: ";
    std::cin >> n;
    int a[n];
    nhapMang(a, n);
    xuatMang(a, n);
    sapXepTang(a, n);
    std::cout << "Mảng sau khi sắp xếp tăng dần là: ";
    xuatMang(a, n);
    sapXepGiam(a, n);
    std::cout << "Mảng sau khi sắp xếp giảm dần là: ";
    xuatMang(a, n);
    return 0;
}

Chú ý:

• Với số thực hoặc ký tự, bạn có thể thực hiện tương tự. Chỉ cần sửa kiểu dữ liệu của mảng, cách nhập và xuất dữ liệu. 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.

Nguồn: https://ispacedanang.edu.vn
Danh mục: Học tập