Trong những bài trước, ta đã khai báo và sử dụng mảng với các phần tử nằm ở các vị trí ngẫu nhiên và được coi là chưa sắp xếp. Điều đó nghĩa là các phần tử chưa tuân theo một quy tắc nào đó và các phần tử đều nằm “lộn sộn” trong mảng. Đối với bài toán có yêu cầu sắp xếp phần tử trong mảng 1 chiều, ta chủ yếu sắp xếp mảng theo chiều tăng dần hoặc giảm dần.

1.Cách sắp xếp các phần tử trong mảng

Trong bài này, phương pháp được sử dụng để sắp xếp mảng 1 chiều theo phần tử tăng dần hay giảm dần đó là phương pháp Selection Sort (sắp xếp chọn).

Giả sử rằng mảng ban đầu của tôi gồm các phần tử là: 5,9,7,2,3,6,9,10 và tôi cần sắp xếp dãy trên hay mảng trên theo chiều các chữ số tăng dần.

Để thực hiện việc sắp xếp dãy trên theo chiều tăng dần, tôi sẽ cần thực hiện các bước lặp và thực hiện kiểm tra điều kiện.

Tôi chọn lần lượt các phần tử có trong mảng và chọn từ phần tử đầu tiên đến phần tử gần cuối của mảng trên để đem so sánh với các phần tử còn lại trong mảng , nếu phần tử đang được chọn lớn hơn phần tử bất kỳ nào nằm trong danh sách thì sẽ thực hiện đổi chỗ hay hoán vị vị trí cho hai phần tử này, ngược lại thì giữ nguyên vị trí. Xem hình minh họa dưới đây:

Nguồn Sắp xếp chọn – Wiki

2.Sắp xếp tăng dần các phần tử trong mảng

Chương trình sắp xếp tăng dần các phần tử trong mảng 1 chiều, với mảng ban đầu là int number[10] = {8,5,2,6,9,3,1,4,0,7};

#include <stdio.h>
int main(){
    //khai bao so luong phan tu
    int n = 10;
    //khai bao mang
    int number[n] = {8,5,2,6,9,3,1,4,0,7};
    //khai bao bien trung gian de hoan vi
    int trunggian;
    //hien thi mang ban dau
    printf("MANG BAN DAU\n");
    for(int i = 0; i < n; i++){
        printf("%d \n", number[i]);
    }
    //thuc hien thuat toan sap xep chon
    for(int i = 0; i < n - 1; i++){
        for(int j = i + 1; j < n; j ++){
            //neu tim thay phan tu be hon phan tu dang xet thi doi cho 2 phan tu do cho nhau
            if(number[i] > number[j]){
                //hoan vi 2 phan tu
                trunggian = number[i];
                number[i] = number[j];
                number[j] = trunggian;
            }
        }
    }
    
    //hien thi mang sau khi sap xep tang dan
    printf("\nMANG SAU KHI SAP XEP TANG DAN\n");
    for(int i = 0; i < n; i++){
        printf("%d \n", number[i]);
    }
}

Hàm sắp xếp các phần tử trong mảng theo chiều tăng dần:

#include <stdio.h>
void SapXepTang(int number[], int n){
    //khai bao bien trung gian de hoan vi
    int trunggian;
    //thuc hien thuat toan sap xep chon
    for(int i = 0; i < n - 1; i++){
        for(int j = i + 1; j < n; j ++){
            //neu tim thay phan tu be hon phan tu dang xet thi doi cho 2 phan tu do cho nhau
            if(number[i] > number[j]){
                //hoan vi 2 phan tu
                trunggian = number[i];
                number[i] = number[j];
                number[j] = trunggian;
            }
        }
    }
}
int main(){
    //khai bao so luong phan tu
    int n = 10;
    //khai bao mang
    int number[n] = {8,5,2,6,9,3,1,4,0,7};
    //hien thi mang ban dau
    printf("MANG BAN DAU\n");
    for(int i = 0; i < n; i++){
        printf("%d \n", number[i]);
    }
    //goi ham sap xep tang va truyen vao mang can sap xep va so luong phan tu
    SapXepTang(number,n);
    //hien thi mang sau khi sap xep tang dan
    printf("\nMANG SAU KHI SAP XEP TANG DAN\n");
    for(int i = 0; i < n; i++){
        printf("%d \n", number[i]);
    }
}

3.Sắp xếp giảm dần các phần tử trong mảng

Đối với việc sắp xếp mảng theo chiều tăng dần, ta cần kiểm tra điều kiện trong vòng lặp đó là if(number[i] > number[j]) thì ta thực hiện hoán vị 2 phần tử đó. Tuy nhiên đối với việc sắp xếp mảng theo chiều giảm dần ta sẽ đặt điều kiện ngược lại đó là: if (number[i] < number[j])

#include <stdio.h>
int main(){
    //khai bao so luong phan tu
    int n = 10;
    //khai bao mang
    int number[n] = {8,5,2,6,9,3,1,4,0,7};
    //khai bao bien trung gian de hoan vi
    int trunggian;
    //hien thi mang ban dau
    printf("MANG BAN DAU\n");
    for(int i = 0; i < n; i++){
        printf("%d \n", number[i]);
    }
    //thuc hien thuat toan sap xep chon
    for(int i = 0; i < n - 1; i++){
        for(int j = i + 1; j < n; j ++){
            //neu tim thay phan tu lon hon phan tu dang xet thi doi cho 2 phan tu do cho nhau
            if(number[i] < number[j]){
                //hoan vi 2 phan tu
                trunggian = number[i];
                number[i] = number[j];
                number[j] = trunggian;
            }
        }
    }
    
    //hien thi mang sau khi sap xep giam dan
    printf("MANG SAU KHI SAP XEP GIAM DAN\n");
    for(int i = 0; i < n; i++){
        printf("%d \n", number[i]);
    }
    
}

Hàm sắp xếp phần tử mảng giảm dần cũng được thay thế if(number[i] > number[j]) bằng if(number[i] < number[j])

#include <stdio.h>
void SapXepGiam(int number[], int n){
    //khai bao bien trung gian de hoan vi
    int trunggian;
    //thuc hien thuat toan sap xep chon
    for(int i = 0; i < n - 1; i++){
        for(int j = i + 1; j < n; j ++){
            //neu tim thay phan tu lon hon phan tu dang xet thi doi cho 2 phan tu do cho nhau
            if(number[i] < number[j]){
                //hoan vi 2 phan tu
                trunggian = number[i];
                number[i] = number[j];
                number[j] = trunggian;
            }
        }
    }
}
int main(){
    //khai bao so luong phan tu
    int n = 10;
    //khai bao mang
    int number[n] = {8,5,2,6,9,3,1,4,0,7};
    //hien thi mang ban dau
    printf("MANG BAN DAU\n");
    for(int i = 0; i < n; i++){
        printf("%d \n", number[i]);
    }
    //goi ham sap xep giam va truyen vao mang can sap xep va so luong phan tu
    SapXepGiam(number,n);
    //hien thi mang sau khi sap xep giam dan
    printf("MANG SAU KHI SAP XEP GIAM DAN\n");
    for(int i = 0; i < n; i++){
        printf("%d \n", number[i]);
    }
    
}

4.Nhập xuất và sắp xếp phần tử trong mảng

Ở 2 chương trình sắp xếp tăng và sắp xếp giảm dần ở phần trên, ta đang sắp xếp cho mảng cố định. Tuy nhiên ta có thể kết hợp nhập xuất rồi thực hiện việc sắp xếp.

#include <stdio.h>
void Nhap(int number[], int n){
    for(int i = 0; i < n ; i++){
        printf("NHAP A[%d]: ",i);
        scanf("%d",&number[i]);
    }
}

void Xuat(int number[],int n){
    for(int i = 0; i < n ; i++){
        printf("%d \n",number[i]);
    }
}
void SapXepTang(int number[], int n){
    //khai bao bien trung gian de hoan vi
    int trunggian;
    //thuc hien thuat toan sap xep chon
    for(int i = 0; i < n - 1; i++){
        for(int j = i + 1; j < n; j ++){
            //neu tim thay phan tu be hon phan tu dang xet thi doi cho 2 phan tu do cho nhau
            if(number[i] > number[j]){
                //hoan vi 2 phan tu
                trunggian = number[i];
                number[i] = number[j];
                number[j] = trunggian;
            }
        }
    }
}
void SapXepGiam(int number[], int n){
    //khai bao bien trung gian de hoan vi
    int trunggian;
    //thuc hien thuat toan sap xep chon
    for(int i = 0; i < n - 1; i++){
        for(int j = i + 1; j < n; j ++){
            //neu tim thay phan tu lon hon phan tu dang xet thi doi cho 2 phan tu do cho nhau
            if(number[i] < number[j]){
                //hoan vi 2 phan tu
                trunggian = number[i];
                number[i] = number[j];
                number[j] = trunggian;
            }
        }
    }
}
int main(){
    //khai bao so luong phan tu
    int n;
    //nhap vao n
    printf("NHAP VAO N: ");
    scanf("%d",&n);
    //khai bao mang n phan tu
    int number[n];
    //goi ham nhap va xuat phan tu
    Nhap(number,n);
    printf("MANG SAU KHI NHAP\n");
    Xuat(number,n);
    //goi ham sap xep tang va hien thi mang sau khi sap xep tang
    SapXepTang(number,n);
    printf("MANG SAU KHI DUOC SAP XEP TANG DAN\n");
    Xuat(number,n);
    //goi ham sap xep giam va hien thi mang sau khi sap xep giam
    SapXepGiam(number,n);
    printf("MANG SAU KHI DUOC SAP XEP GIAM DAN\n");
    Xuat(number,n);
}