Giáo trình ngôn ngữ C

Gi¸o tr×nh tin häc c¬ së II - N
gôn ngữ
 C
69
#include  
#include  
void main(){ 
clrscr(); 
const int max = 10; 
int A[max], B[max], C[max]; 
int n,i; 
do{ 
printf("\nNhap so phan tu mang = "); 
scanf("%d",&n); 
}while(n<1 || n>max); //nhập số pt mảng 1<=n<=max 
printf("\nNhap mang A co %d phan tu \n",n); 
for(i=0; i{ 
printf("A[%d]= ",i); 
scanf("%d",&A[i]); 
} 
printf("\nNhap mang B co %d phan tu \n",n); 
for(i=0; i{ 
printf("B[%d]= ",i); 
scanf("%d",&A[i]); 
} 
// Tính C=A+B 
for(i=0; iC[i]= A[i]+B[i]; 
printf("\nCac phan tu mang ket qua C la \n"); 
for(i = 0; i < n; i++) 
printf("%d, ",C[i]); 
getch(); 
} 
(Ví dụ V.2 - Tính tổng 2 mảng) 
V.2.3 - Sắp xếp và tìm kiếm trên mảng một chiều
Trong thực tế chúng ta rất hay gặp yêu cầu phải sắp xếp một dãy các phần tử theo một 
trật tự nào đó, hoặc là tìm kiếm một phần tử có trong một dãy các phần tử hay không. Một 
cách thuận lợi nhất (nếu có thể) đó là biểu diễn các phần tử đó là một mảng các phần tử. 
¾
Sắp xếp mảng: Bài toán sắp xếp mảng nói chung được phát biểu như sau: Cho một 
mảng có n phần tử, và k là khoá của mỗi phần tử, các phần tử có thể so sánh với nhau 
theo khoá k, hãy sắp xếp mảng theo thứ tự tăng (hoặc giảm) của khoá k. 

Gi¸o tr×nh tin häc c¬ së II - N
gôn ngữ
 C
70
Khoá k chúng ta có thể hiểu là một thành phần nào đó của các phần tử như là tuổi của 
một người, hay điểm trung bình học tập của một sinh viên, hoặc là một tiêu chí nào đó áp 
dụng cho các phần tử của mảng.
Trong trường hợp đơn giản như các mảng số mà chúng ta sẽ nói trong ví dụ sau đây thì 
khoá k chính là giá trị của các phần tử.
Hiện nay có nhiều thuật toán để sắp xếp một mảng: thuật toán nối bọt, thuật toán đổi 
chỗ, thuật toán chọn, thuật toán chia đôi,.. trong giáo trình này chúng tôi giới thiệu ba 
thuật toán sắp xếp đơn giản để sắp một mảng A có n phần tử kiểu số nguyên. 
a. Sắp xếp bằng phương pháp nổi bọt 
Ý tưởng của phương pháp này là có n phần tử (“bọt nước”) đều có xu hướng nổi lên 
trên mặt nước, thì phần tử nào nhỏ hơn (‘nhẹ hơn’) sẽ được ưu tiên nổi lên trên. Tức là 
với mọi cặp phần tử kề nhau nếu phần tử sau (dưới) nhỏ hơn phần tử phía trước thì phần 
tử nhỏ hơn sẽ nổi lên trên, phần tử nặng hơn sẽ chìm xuống dưới. 
Sơ đồ thuật toán sắp xếp mảng A(n) như sau: 
(sắp xếp bằng phương pháp nổi bọt)
 
b. Sắp xếp bằng phương pháp đổi chỗ trực tiếp 
Ý tưởng của phương pháp này cũng rất đơn giản là: giả sử các phần tử đầu mảng A[0], 
A[1],.., A[i-1] đã được sắp đúng vị trí tức là đã có: 
A[0] <=A[1] <=,..

Gi¸o tr×nh tin häc c¬ së II - N
gôn ngữ
 C
71
Công việc tiếp theo là sắp các phần tử còn lại vào đúng vị trí của nó. Các bạn thấy vị trí 
thứ i là vị trí đầu tiên chưa được sắp, nếu được sắp thì A[i] phải có giá trị nhỏ nhất trong 
các phần tử còn lại đó {A[i],A[i+1],..,A[n-1]}, vậy chúng ta sẽ duyệt các phần tử mảng 
trong phần còn lại A[j] với j =i+1 tới n-1, nếu A[j] < A[i] thì chúng ta đổi chỗ A[i] với 
A[j]. Như vậy phần tử i đã được xếp đúng vị trí. 
Vậy chúng ta thực hiện lặp công việc trên với i từ 0 tới n-2 chúng ta sẽ có mảng được
sắp. 
(sắp xếp bằng phương pháp đổi chỗ trực tiếp)
c. Sắp xếp bằng phương pháp chọn 
Các bạn có nhận xét là trong phương pháp đổi chỗ trực tiếp để đặt được phần tử vào vị 
trí i có thể phải sử dụng (n-1) phép đổi chỗ. Trong khi đó chỉ có một phần tử sẽ đặt tại đó.
Phương pháp chọn cũng xuất phát từ ý tưởng như phương pháp đổi chỗ trực tiếp nhưng 
thay vì đổi chỗ A[i] với Ạ[j] trong mỗi bước duyệt (theo j) thì chúng ta xác định phần tử 
nhỏ nhất trong các phần tử A[i+1],..A[n-1] giả sử là A[k], sau đó dổi chỗA[k] và A[i]. 
Như vậy với mỗi vị trí i chương trình chỉ thực hiện đổi chỗ một lần, và người ta tính thời 
gian thực hiện trung bình của phương pháp này ít hơn thời gian trung bình của hai phương 
pháp trên. 
Các 
bạn có sơ đồ khối như sau 

Gi¸o tr×nh tin häc c¬ së II - N
gôn ngữ
 C
72
(
sắp xếp bằng phương pháp chọn) 
Ví dụ V.3: chương trình minh hoạ sắp xếp mảng bằng phương pháp nổi bọt
#include  
#include  
void main(){ 
const max=10; 
int n,a[max], i,j,tg; 
do{ 
printf("Nhap so n : "); 
scanf("%d", &n); 
}while(n<2); 
printf("\nNhap mang co %d phan tu \n",n); 
for(i=0;i{ printf("a[%d]= ",i); 
scanf("%d",&a[i]);
} 
for(i = 0; ifor(j =n-1; j>i;j--) 
if(a[j]{ tg=a[j]; a[j]=a[j-1]; a[j-1]=tg;} 
printf("Mang sau khi sap la \n"); 
for(i=0;iprintf("%d, ",a[i]); 
} 

Gi¸o tr×nh tin häc c¬ së II - N
gôn ngữ
 C
73
¾

tải về 2.34 Mb.

Chia sẻ với bạn bè của bạn: