1. Bài tập thuật toán sắp xếp chèn trực tiếp (Insertion 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 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 chèn trực tiếp như sau:
- Giả sử có một dãy a0 , a1 ,… ,an-1 trong đó i phần tử đầu tiên a0 , a1 ,… ,ai-1 đã có thứ tự.
- Tìm cách chèn phần tử ai vào vị trí thích hợp của đoạn đã được sắp để có dãy mới a0 , a1 ,… ,ai trở nên có thứ tự. Vị trí này chính là vị trí giữa hai phần tử ak-1 và ak thỏa mãn ak-1 < ai < ak (1≤k≤i).
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 Insertion 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 InsertionSort(int a[], int n) sử dụng thuật toán Insertion Sort để sắp xếp mảng tăng dần. Trong hàm ta khai báo biến int pos, i và int x dùng để lưu vị trí a[i] tránh bị ghi đè khi đổi chỗ các phần tử. Ta dùng vòng lặp for bắt đầu từ i=1 (bắt đầu từ 1 vì đoạn a[0] đã sắp xếp), 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 gán giá trị của x=a[i], pos=i-1 và dùng vòng lặp while với điều kiện (pos >= 0) && (a[pos] > x) để tìm vị trí để chèn giá trị x, sau đó ta gán a[pos+1] = a[pos] và giảm pos đi 1 mỗi lần lặp. Kết thúc lặp while ta gán a[pos+1] = x (chèn x vào dãy). Sau khi hết vòng lặp for 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 Insertion 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 InsertionSort(int a[], int n)//thuat toan sap xep Insertion Sort
{
int pos, i;
int x;//luu vi tri a[i] tranh bi ghi de khi doi cho phan tu
for(i=1 ; i<n ; i++)//doan a[0] da sap xep
{
x = a[i];
pos = i-1;
//tim vi tri chen x
while((pos >= 0) && (a[pos] > x))
{
//ket hop doi cho cac phan tu se dung sau x trong day moi
a[pos+1] = a[pos];
pos--;
}
a[pos+1] = x;//chen x vao day
}
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);
InsertionSort(a,n);
}
Ví dụ tôi nhập mảng có 5 phần tử: 9,1,4,2,0
Kết quả:
Nhap so phan tu:5 Nhap a[0]=9 Nhap a[1]=1 Nhap a[2]=4 Nhap a[3]=2 Nhap a[4]=0 Mang sau khi nhap la: 9 1 4 2 0 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 Insertion Sort trong C.
