1. Bài tập thuật toán sắp xếp Quick 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 Quick 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 Quick 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 Quick Sort trong C.
Ý tưởng của thuật toán Quick Sort như sau:
- Giải thuật QuickSort sắp xếp dãy a1 , a2 …, an dựa trên việc phân hoạch dãy ban đầu thành 3 phần :
- Phần 1:Gồm các phần tử có giá trị bé hơn x
- Phần 2: Gồm các phần tử có giá trị bằng x
- Phần 3: Gồm các phần tử có giá trị lớn hơn x
với x là giá trị của một phần tử tùy ý trong dãy ban đầu.
- Sau khi thực hiện phân hoạch, dãy ban đầu được phân thành
3 đoạn:- 1. ak <= x , với k = 0 .. j
- 2. ak = x , với k = j+1 .. i-1
- 3. ak >= x , với k = i..n-1
- Đoạn thứ 2 đã có thứ tự.
- Nếu các đoạn 1 và 3 chỉ có 1 phần tử : đã có thứ tự ->khi đó dãy con ban đầu đã được sắp.
- Nếu các đoạn 1 và 3 có nhiều hơn 1 phần tử thì dãy ban đầu chỉ có thứ tự khi các đoạn 1, 3 được sắp.
- Để sắp xếp các đoạn 1 và 3, ta lần lượt tiến hành việc phân hoạch từng dãy con theo cùng phương pháp phân hoạch dãy ban đầu vừa trình bày …
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 Quick 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 QuickSort(int a[], int left, int right) (left là vị trí bắt đầu mảng right là vị trí kết thúc mảng)sử dụng thuật toán Quick Sort để sắp xếp mảng tăng dần. Trong hàm ta khai báo int x = a[(left+right)/2] , int i=left và j = right để phân hoawcjh dãy thành 3 phần. Ta dùng vòng lặp while trong khi i<=j, ta tiếp tục dùng while trong khi a[i]<x thì ta tăng i lên 1, dùng while trong khi a[j]>x thì ta giảm j đi 1. Ta dùng if với điều kiện nếu i<=j thì ta đổi chỗ a[i] vơi a[j] qua biến int tg cùng với đó tăng i lên 1 và giảm j đi 1. Kết thúc lặp ta dùng if với điều kiện left<j thì ta gọi đệ quy QuickSort(a,left,j) (gọi đệ quy qua dãy bên trái). Dùng if với điều kiện i<right thì ta gọi đệ quy QuickSort(a,i,right) (gọi đệ quy qua dãy bên phải).
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) cùng với QuickSort(a,0,n-1) và gọi lại hàm Xuat(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 Quick 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 QuickSort(int a[], int left, int right){
//phan hoach day can sap thanh 3 phan
int x = a[(left+right)/2];
int i=left, j=right;
while (i <= j){
while (a[i]<x){
i++;
}
while (a[j]>x){
j--;
}
if (i<=j){
int tg = a[i];
a[i]=a[j];
a[j]=tg;
i++;
j--;
}
}
if (left<j)//de qui quick sort day ben trai
QuickSort(a,left,j);
if (i<right)//de quy quick sort day ben trai
QuickSort(a,i,right);
}
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);
QuickSort(a,0,n-1);
printf("\nMang sau khi sap xep la:\n");
Xuat(a,n);
}
Ví dụ tôi nhập chuỗi 5 phần tử: 1,4,0,3,2
Kết quả:
Nhap so phan tu:5 Nhap a[0]=1 Nhap a[1]=4 Nhap a[2]=0 Nhap a[3]=3 Nhap a[4]=2 Mang sau khi nhap la: 1 4 0 3 2 Mang sau khi sap xep la: 0 1 2 3 4
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 Quick Sort trong C.
- Cách đổi chỗ các phần tử qua biến trung gian trong C.
