Home Lập trình Học C/C++ Bài 45. Sắp xếp dãy số giảm dần, tăng dần

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

Bài 45. Sắp xếp dãy số giảm dần, tăng dần
Minh họa thuật toán selection sort

Sắp xếp dãy số theo thứ tự tăng dần hay giảm dần là 1 bài toán sắp xếp đơn giản và cơ bản nhất đối với bất cứ ai học lập trình. Nói theo cách khác, bài toán này chính là bài toán sắp xếp mảng 1 chiều tăng dần/giảm dần. Bài toán sắp xếp dãy số là bài tập điển hình trong phần kiến thức về mảng 1 chiều. Sắp xếp cũng là một kiến thức quan trọng thuộc phần giải thuật trong cấu trúc dữ liệu & giải thuật. Trong bài viết này, Lập trình không khó sẽ cùng các bạn giải quyết bài toán sắp xếp mảng 1 chiều tăng dần và giảm dần.

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

Khi bạn làm bài tập lập trình mà có các cụm 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 1 chiều các số tự nhiên tăng/giảm dần

Thì cả 3 đề bài này đều là bài toán sắp xếp dữ liệu trên mảng 1 chiều. Khi nhắc tới “dãy số” thì bạn phải nghĩ ngay tới mảng 1 chiều. Dưới đây là 1 số lưu ý tham khảo 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 1 chiều để có thể hiểu bài viết này, xem tại: Mảng 1 chiều
  • Có rất nhiều thuật toán sắp xếp khác nhau, tham khảo thêm tại: thuật toán sắp xếp
  • Tổng hợp bài tập mảng 1 chiều có lời giải: [eafl id=”3911″ name=”” text=”Bài tập mảng 1 chiều có lời giải”]

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

Trong code mà mình cung cấp dưới đây thì mình sẽ dùng thuật toán sắp xếp chọn – một thuật toán sắp xếp dễ hiểu và dễ cài đặt nhất.

Xem hình dưới đây để hiểu ý tưởng sắp xếp, xem chi tiết tại bài thuật toán sắp xếp chọn

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

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

#include <stdio.h>

int main(){
    int a[100];
    int n;
    printf("\nNhap so luong phan tu n = ");
    do{
        scanf("%d", &n);
        if(n <= 0){
            printf("\nNhap lai n = ");
        }
    }while(n <= 0);
    
    for(int i = 0; i < n; i++){
        printf("\nNhap a[%d] = ",i);
        scanf("%d", &a[i]);
    }
    
    // Sap xep dung thuat toan sap xep chon
    int tg;
    for(int i = 0; i < n - 1; i++){
        for(int j = i + 1; j < n; j++){
            if(a[i] < a[j]){
                // Hoan vi 2 so a[i] va a[j]
                tg = a[i];
                a[i] = a[j];
                a[j] = tg;        
            }
        }
    }
    
    
    printf("\nMang da sap xep la: ");
    for(int i = 0; i < n; i++){
        printf("%5d", a[i]);
    }
    
    
}

Chạy thử:

Nhap so luong phan tu n = 5

Nhap a[0] = 1

Nhap a[1] = 3

Nhap a[2] = 2

Nhap a[3] = 4

Nhap a[4] = 5

Mang da sap xep la:     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ị.

#include <stdio.h>

int main(){
    int a[100];
    int n;
    printf("\nNhap so luong phan tu n = ");
    do{
        scanf("%d", &n);
        if(n <= 0){
            printf("\nNhap lai n = ");
        }
    }while(n <= 0);
    
    for(int i = 0; i < n; i++){
        printf("\nNhap a[%d] = ",i);
        scanf("%d", &a[i]);
    }
    
    // Sap xep dung thuat toan sap xep chon
    int tg;
    for(int i = 0; i < n - 1; i++){
        for(int j = i + 1; j < n; j++){
            if(a[i] > a[j]){
                // Hoan vi 2 so a[i] va a[j]
                tg = a[i];
                a[i] = a[j];
                a[j] = tg;        
            }
        }
    }
    
    
    printf("\nMang da sap xep la: ");
    for(int i = 0; i < n; i++){
        printf("%5d", a[i]);
    }
    
    
}

Kết quả chạy thử:

Nhap a[0] = 1

Nhap a[1] = 2

Nhap a[2] = 4

Nhap a[3] = 3

Nhap a[4] = 5

Mang da sap xep la:     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 dùng hàm sẽ giúp code của chúng ta rõ ràng, sạch sẽ và cũng 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)
#include <stdio.h>

void NhapMang(int a[], int n){
    for(int i = 0; i < n; i++){
        printf("\nNhap 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]){
                // Hoan vi 2 so a[i] va 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]){
                // Hoan vi 2 so a[i] va a[j]
                tg = a[i];
                a[i] = a[j];
                a[j] = tg;        
            }
        }
    }
}

int main(){
    int a[100];
    int n;
    printf("\nNhap so luong phan tu n = ");
    do{
        scanf("%d", &n);
        if(n <= 0){
            printf("\nNhap lai n = ");
        }
    }while(n <= 0);
    
    NhapMang(a, n);
    
    printf("\nMang vua nhap la: ");
    XuatMang(a, n);
    
    // Sap xep tang dan:
    TangDan(a, n);
    printf("\nMang sap xep tang dan la: ");
    XuatMang(a, n);
    
    // Sap xep giam dan:
    GiamDan(a, n);
    printf("\nMang sap xep giam dan la: ");
    XuatMang(a, n);
    
}

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

Nhap so luong phan tu n = 5

Nhap a[0] = 1

Nhap a[1] = 4

Nhap a[2] = 3

Nhap a[3] = 2

Nhap a[4] = 5

Mang vua nhap la:     1    4    3    2    5
Mang sap xep tang dan la:     1    2    3    4    5
Mang sap xep giam dan la:     5    4    3    2    1

Chú ý:

  • Với số thực hay kiểu ký tự(char) bạn cũng làm tương tự. Chỉ cần sửa kiểu dữ liệu của mảng, cách nhập, xuất. Còn 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 nên thử cài đặt bằng những thuật toán sắp xếp khác.

Theo dõi lập trình không khó tại:

26 COMMENTS

  1. Với phần code cài đặt bằng hàm, các bạn nên viết riêng 1 hàm swap để code được rõ ràng hơn: “mỗi hàm chỉ thực hiện một nhiệm vụ”

  2. Cảm ơn anh , mong anh ra thêm những bài toán về lập trình c++ kết hợp lời giải như thế này nữa để cho bọn em có động lực học lập trình và củng cố kiến thức của anh 😀 hy vọng có nhiều bài viết về AI trong các series tiếp theo ạ

  3. code sạch, giải thích rất rõ ràng và dễ hiểu ạ, chúc anh sức khoẻ để có thể ra nhiều những bài viết hay ạ!

  4. for(int i = 0; i < n – 1; i++){
    for(int j = i + 1; j < n; j++)
    Vì sao vòng lặp của i điều kiện là i<n-1 mà không phải là i<n, mong bạn giải thích dùm mình

    • À có thì cũng không sai nhưng thừa,
      Bởi vì chúng ta cần so sánh hai phần tử mà. Trường hợp i == n-1 thì là phần tử cuối rồi nên chẳng còn phần tử nào sau nó để so sánh cả.

  5. for(int i = 0; i < n – 1; i++)
    {
    for(int j = i + 1; j < n; j++)
    }
    Mình chưa hiểu cụ thể thì nó chạy các bước như thế nào, chủ thớt có thể nói rõ hơn không ?
    Có phải a[j] chạy trước, sau đó đến a[i] và lần lượt so sánh từng số thuộc a[i] với tất cả các số thuộc a[j] ?
    Mình mới học nên chưa rõ, hy vọng được giải đáp kỹ, cám ơn.

    • Vấn đề của em là em chưa hiểu cách hoạt động của vòng lặp for nhé. Vòng lặp for sẽ lặp lại công việc trong thân của nó. Như vậy, nếu có 2 vòng lặp for lồng nhau thì vòng lặp ở trong chính là cái thằng bị lặp lại của vòng lặp ngoài.

      Ví dụ với vòng lặp của em ở trên:
      – Khi i = 0, vòng lặp trong sẽ chạy j từ 1 đến n -1
      – Khi i = 1, vòng lặp trong sẽ chạy j từ 2 đến n -1
      – …

  6. Viết hàm checkAss, kích thước của mảng là N. hàm trả về 1 nếu là hàm tăng dần, -1 nếu không phải… làm kiểu gì ạ….

  7. “tìm hiểu thuật toán đường đi ngắn nhất C”
    bạn ơi cho mình xin link bài này với

    • Cái này ad chưa có tìm hiểu nên bạn search google nhé.

    • Vì vòng lặp chỉ cần đến i < n-1 (tức là đến số áp chót) do số cuối cùng chỉ có 1 mk ko cần phải so sánh và hoán vị nữa. Nếu bạn để i < n, máy tính cũng chỉ thực hiện thêm 1 bước lặp với số cuối nữa thôi nên không ảnh hưởng đến kết quả bài toán.

  8. Hình minh họa là của sắp xếp chọn nhưng code lại của nổi bọt kìa a. A sửa lại ạ

  9. tại sao lại là j=i+1 mà không phải là j=1 vậy ạ, lúc e thử j=1 thì nó sẽ chỉ sắp xếp số đầu tiên

    • Theo mình nghĩ nếu bạn để j=1 thì kết quả sẽ chạy sai ở lần lặp thứ 3(i=2). Vì ý tưởng của thuật toán là chia mảng thành 2 mảng con. Phần tử nhỏ nhất ở mảng con chưa được sắp xếp sẽ được di chuyển về đoạn đã sắp xếp. Nên lúc nào j cũng phải chạy sau i

    • Nếu điều kiện là i < n – 1, giả sử cho n = 3, thì séx chỉ có 2 vòng lặp thôi chứ? Mình vẫn đang hơi rối đoạn này,

LEAVE A REPLY

Please enter your comment!
Please enter your name here