1. Bài tập thuật toán sắp xếp Shaker Sort bằng ngôn ngữ lập trình C

Yêu cầu của bài toán là sắp xếp mảng số nguyên tăng dần bằng thuật toán sắp xếp Shaker Sort trong C.

Đối với bài tập này chúng ta sẽ sử dụng các kiến thức như sau: nhập và xuất dữ liệu cơ bàn trong ngôn ngữ lập trình C, cách sử dụng mảng trong ngôn ngữ lập trinh C, cách sử dụng vòng lặp for để duyệt các phần tử trong mảng, cách dùng thuật toán sắp xếp Shaker Sort trong C.

2. Lời giải

Để thực hiện bài toán này chúng ta cần có kiến thức cơ bản về ngôn ngữ lập trình C, nhập xuất dữ liệu cơ bàn trong ngôn ngữ lập trình C, cách sử dụng mảng trong ngôn ngữ lập trinh C, cách sử dụng vòng lặp for để duyệt các phần tử trong mảng và cách dùng thuật toán sắp xếp Shaker Sort trong C.

Ý tưởng của thuật toán Shaker Sort là bản phát triển của thuật toán nổi bọt (Bubble Sort) như sau:

  • Trong mỗi lần sắp xếp, duyệt mảng theo 2 lượt từ 2 phía khác nhau:
    • Lượt đi: đẩy phần tử lớn về cuối mảng.
    • Lượt về: đẩy phần tử nhỏ về đầu mảng.
  • Ghi nhận lại những đoạn đã sắp xếp nhằm tiết kiệm các phép so sánh thừa.

Các bước thực hiện yêu cầu của bài tập sắp xếp mảng số nguyên tăng đần bằng thuật toán sắp xếp Shaker Sort trong ngôn ngữ lập trình C như sau:

Bước 1: Ta khỏi tạo hàm Nhap(int a[],int n) dùng để nhập dữ liệu cho mảng. Trong hàm ta dùng vòng lặp for bắt đầu từ int i=0, kết thúc khi i<n và mỗi lần lặp i tăng lên 1. Trong vòng lặp ta nhập dữ liệu từ bàn phím cho từng phần tử a[i].

Bước 2: Ta khỏi tạo hàm Xuat(int a[],int n) dùng để hiển thị mảng ra màn hình. Trong hàm ta dùng vòng lặp for bắt đầu từ int i=0, kết thúc khi i<n và mỗi lần lặp i tăng lên 1. Trong vòng lặp ta hiển thị từng phần tử a[i] ra màn hình.

Bước 3: Ta khởi tạo hàm ShakerSort(int a[], int n) sử dụng thuật toán Shaker Sort để sắp xếp mảng tăng dần. Trong hàm ta khai báo biến int left=0, right = n-1 (là điểm bắt đầu và kết thúc của mảng) và biến int k dùng để ghi lại vị trí hoán đổi của các phần tử nhằm thu hẹp chuỗi (đoạn left -> right). Sau đó ta dùng vòng lặp while với điều kiện left<right (miễn là right còn lớn hơn left). Trong vòng while ta dùng vòng lặp for bắt đầu từ int i = left, kết thúc khi i<right và mỗi lần lặp i tăng lên 1 (đẩy phần tử lớn nhất về cuỗi mảng); trong vòng for i ta dùng if với điều kiện a[i] > a[i+1] nếu thỏa mãn ta đổi chỗ a[i] cho a[i+1] và gán k=i. Kết thúc lặp ta gán right = k (loại phần tử ở cuối mảng). Ta khởi tạo vòng lặp for bắt đầu từ int i=right, kết thúc khi i>left và mỗi lần lặp i giảm đi 1 (đẩy phần tử nhỏ nhất về đầu mảng); trong vòng for i ta dùng if với điều kiện a[i] < a[i-1] nếu thỏa mãn ta đổi chỗ a[i] cho a[i-1] và gán k=i. Kết thúc lặp ta gán left = k(loại phần tử ở đầu mảng). Kết thúc vòng while ta gọi hàm Xuat(a,n) để in mảng đã sắp xếp ra màn hình.

Bước 4: Trong hàm main ta khởi tạo mảng tĩnh số nguyên int a[100](có tối đa 100 phần tử), int n và nhận dữ liệu cho biến int n là số phần tử của mảng.

Bước 5: Gọi hàm Nhap(a,n), Xuat(a,n) và ShakerSort(a,n) để hiển thị mảng đã sắp xếp rồi chạy chương trình.

Chương trình giải bài tập sắp xếp mảng số nguyên tăng đần bằng thuật toán sắp xếp Shaker Sort trong ngôn ngữ lập trình C như sau:

#include <stdio.h>
void Nhap(int a[],int n){//ham nhap mang
    for(int i=0; i<n; i++){
        printf("\nNhap a[%d]=",i);
        scanf("%d",&a[i]);
    }
}
void Xuat(int a[],int n){//ham xuat mang
    for(int i=0; i<n; i++){
        printf("%d \t",a[i]);
    }
}
void ShakerSort(int a[], int n){//thuat toan Shaker Sort
    int left=0, right=n-1;// doan left -> right la doan can duoc sap xep
    int k;//ghi lai vi tri k xay ra hoan vi sau cung nham thu hep doan left -> right
    while(left<right){
        //day phan tu lon nhat ve cuoi mang
        for (int i=left; i<right; i++){
            if (a[i] > a[i+1]){
                int tg = a[i];
                a[i] = a[i+1];
                a[i+1] = tg;
                k = i;
            }
        }
        right = k;//loai phan tu da co thu tu o cuoi mang
        //day phan tu nho nhat ve dau mang
        for (int i = right; i > left; i--){
            if (a[i] < a[i - 1]){
                int tg = a[i];
                a[i] = a[i-1];
                a[i-1] = tg;
                k = i;
            }
        }
        left = k;//loai phan tu da co thu tu o dau mang
    }
    printf("\nMang sau khi sap xep la:\n");	
    Xuat(a,n);	
}
int main(){
    int a[100];
    int n;
    printf("Nhap so phan tu:");
    scanf("%d",&n);
    Nhap(a,n);
    printf("\nMang sau khi nhap la:\n");
    Xuat(a,n);
    ShakerSort(a,n);
}

Ví dụ tôi nhập mảng có 5 phần tử: 9, 3, 0, 4 , 1

Kết quả:

Nhap so phan tu:5

Nhap a[0]=9

Nhap a[1]=3

Nhap a[2]=0

Nhap a[3]=4

Nhap a[4]=1

Mang sau khi nhap la:
9       3       0       4       1
Mang sau khi sap xep la:
0       1       3       4       9

3. Tổng kết

Sau khi làm bài tập này các bạn cần phải hiểu và nắm được những kiến thức sau:

  • Cách nhập xuất cơ bản trong ngôn ngữ lập trình C.
  • Cách sử dụng hàm trong C.
  • Cách sử dụng vòng lặp để duyệt thông tin của từng phần tử trong C.
  • Cách sử dụng thuật toán sắp xếp Shaker Sort trong C.
  • Cách đổi chỗ phần tử qua biến trung gian trong C.