1. Bài tập thuật toán sắp xếp chọn trực tiếp (Selection 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 chọn trực tiếp (Selection 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 chọn trực tiếp 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 chọn trực tiếp trong C.

Ý tưởng của thuật toán sắp xếp chọn trực tiếp (Selection Sort) như sau:

  • Chọn phần tử nhỏ nhất (hoặc lớn nhất) trong N phần tử trong dãy hiện hành ban đầu.
  • Đưa phần tử này về vị trí đầu dãy hiện hành.
  • Xem dãy hiện hành chỉ còn N-1 phần tử của dãy hiện hành ban đầu.
    • Bắt đầu từ vị trí thứ 2.
    • Lặp lại quá trình trên cho dãy hiện hành… đến khi dãy hiện hành chỉ còn 1 phần tử.

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 chọn trực tiếp (Selection 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 SelectionSort(int a[], int n) sử dụng thuật toán đổi chọn trực tiếp để sắp xếp mảng tăng dần. 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-1, mỗi lần lặp i tăng lên 1. Trong vòng lặp for i ta khai báo biến int min = i (vị trí bắt đầu hiện tại là vị trí min) và vòng lặp for bắt đầu từ int j=i+1, kết thúc khi j<n, mỗi lần lặp j tăng lên 1.Trong vòng lặp for j ta dùng if với điều kiện a[j]<a[min] (nếu phan tử ở vị trí min lớn hơn ở vị trí j) thì ta gán min = j (cập nhật lại vị trí min). Kết thúc vòng lặp for j ta đổi chỗ a[i] với a[min] qua biến int tg. Kết thúc vòng for i ta gọi hàm Xuat(a,n) để hiển thị 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à SelectionSort(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 chọn trực tiếp (Selection 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 SelectionSort(int a[], int n){//thuat toan chon truc tiep
    for(int i=0; i<n-1; i++)
    {
        int min = i;//thiet lap phan tu hien tai la vi tri min
        for (int j = i+1; j<n; j++){
            if (a[j]<a[min]){//kiem tra phan tu tiep theo co nho hon vi tri min khong neu co doi min 
                min = j;
            }
        }
        // doi cho cac phan tu trong mang
        int tg = a[i];
        a[i] = a[min];
        a[min] = tg;
    }
    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);
    SelectionSort(a,n);
}

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

Kết quả:

Nhap so phan tu:5

Nhap a[0]=9

Nhap a[1]=1

Nhap a[2]=0

Nhap a[3]=4

Nhap a[4]=2

Mang sau khi nhap la:
9       1       0       4       2
Mang sau khi sap xep la:
0       1       2       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 chọn trực tiếp (Selection Sort) trong C.
  • Cách đổi chỗ phần tử sử dụng biến trung gian trong C.